DouKaku?

class QuadraticArray < Array
  def col_size
    return self[0].length
  end
  def row_size
    return self.length
  end
  def each_elem(&fn)
    0.upto(row_size-1) do |i|
      0.upto(col_size-1) do |j|
        fn.call(i,j)
      end
    end
  end
end

class Mino < QuadraticArray
  def rot()
    res = Mino.new(col_size){Array.new(row_size, 0)}
    each_elem {|i, j| res[j][row_size - i - 1] = self[i][j] }
    return res
  end
end

I = Mino[[1,1,1,1]]
O = Mino[[1,1],[1,1]]
L = Mino[[1,1,1],[1,0,0]]
T = Mino[[1,1,1],[0,1,0]]
Z = Mino[[1,1,0],[0,1,1]]

def mirrors(*minos)
  minos.clone.each {|mino| minos << mino.reverse }
  return minos
end

def rotations(mino)
  minos = [mino]
  3.times do minos << minos[-1].rot end
  return minos
end

BasicMinos = Hash[]
BasicMinos[I] = [I, I.rot]
BasicMinos[O] = [O]
BasicMinos[T] = rotations(T)
BasicMinos[L] = mirrors(*rotations(L)) 
BasicMinos[Z] = mirrors(Z, Z.rot)

class Plate < QuadraticArray
  def clone
    Plate.new(map {|e| e.clone})
  end
  def isAbleToArrayMinos(minos)
    mino = minos.pop
    each_elem do |y, x| BasicMinos[mino].each do |m|
        plate = self.clone
        if plate.isAbleToPutMino(m, y, x) then
          if minos.length == 0 then 
            return true if plate.isCompleted
          elsif plate.isAbleToArrayMinos(minos.clone) then
            return true 
          end
        end
    end end
    return false
  end
  def isAbleToPutMino(mino, i, j)
    if (mino.row_size + i > row_size) then return false
    elsif (mino.col_size + j > col_size) then return false end
    mino.each_elem do |y, x|
      return false if ((self[i+y][j+x] += mino[y][x]) == 2)
    end
    return true
  end
  def isCompleted
    each_elem {|i, j| if not (self[i][j] == 1) then return false end}
    return true
  end
end

EmptyPlate = Plate.new(4){Array.new(4,0)}

p EmptyPlate.isAbleToArrayMinos([I,I,I,I])
p EmptyPlate.isAbleToArrayMinos([O,O,O,O])
p EmptyPlate.isAbleToArrayMinos([I,O,O,T])
p EmptyPlate.isAbleToArrayMinos([L,Z,L,Z])
p EmptyPlate.isAbleToArrayMinos([I,Z,Z,Z])

(use util.match)
(use gauche.array)
(use srfi-1)
(use srfi-42)

(define height 4)
(define width 4)

(define mino-images
  '(("****")

    ("**"
     "**")

    ("***"
     " * ")

    ("***"
     "*  ")

    ("** "
     " **")))


;; string list -> point list
(define (mino-image->points mino-image)
  (append-map (lambda (row s)
                (filter-map (lambda (col)
                              ;; asterisk -> (row . col)
                              (match (string-ref s col)
                                [#\*    (cons row col)]
                                [#\space #f]))
                            (iota (string-length s) 0)))
              (iota (length mino-image) 0)
              mino-image))

(define (rotate mino) (map (match-lambda [(row . col) (cons col (- row))]) mino))
(define (flip mino) (map (match-lambda [(row . col) (cons col row)]) mino))

;; rotate, flip and delete duplicates
(define (mino-patterns mino)
  (define (rotate-n mino n)
    (let f ([i 0] [m mino] [l '()])
      (if (< i n) (f (+ i 1) (rotate m) (cons m l)) l)))
  (delete-duplicates (append (rotate-n mino 4) (rotate-n (flip mino) 4))))

;;; Table

(define (make-tbl row col) (make-array (shape 0 row 0 col) #f))
(define tbl-ref array-ref)
(define tbl-set  (cut array-set! <> <> <> #t))
(define tbl-unset  (cut array-set! <> <> <> #f))

(define (tbl-encode tbl)
  (fold (lambda (c n) (match c [#t (+ (* 2 n) 1)] [#f (* 2 n)]))
        0
        (array->list tbl)))

(define (tbl-put tbl mino row col)
  (define (valid? tbl mino row col)
    (every (match-lambda [(d-row . d-col)
                          (let ([r (+ row d-row)] [c (+ col d-col)])
                            (and (>= r 0) (< r height)
                                 (>= c 0) (< c width)
                                 (not (tbl-ref tbl r c))))])
           mino))
  (and (valid? tbl mino row col)
      (let ()
        (for-each (match-lambda [(d-row . d-col)
                                 (tbl-set tbl (+ row d-row) (+ col d-col))])
                  mino)
        #t)))
(define (tbl-unput-mino tbl mino row col)
  (for-each (match-lambda [(d-row . d-col)
                           (tbl-unset tbl (+ row d-row) (+ col d-col))])
            mino))

;; for debug
(define (tbl-dump tbl)
  (format #t "--~%")
  (do-ec (: row 0 height)
         (begin
           (do-ec (: col 0 width)
                  (format #t "~a" (if (tbl-ref tbl row col) #\* #\space)))
           (format #t "~%"))))

(define (dfs ht tbl mino-list)
  (or (null? mino-list)
      (let* ([e (tbl-encode tbl)])
        (and (not (hash-table-get ht e #f))
            (let ()
              (hash-table-put! ht e #t)
              (and (not (null? mino-list))
                   (any?-ec (:list m (mino-patterns (car mino-list)))
                            (: row 0 height) (: col 0 width)
                            (if (tbl-put tbl m row col)
                                (let1 r (dfs ht tbl (cdr mino-list))
                                  (tbl-unput-mino tbl m row col)
                                  r)
                                #f))))))))

(define all-mino-list (map mino-image->points mino-images))

(define (can-put-minos? ids)
  (format #t "~a : ~a~%"
          ids
          (if (dfs (make-hash-table) (make-tbl height width)
                   (map (lambda (id) (ref all-mino-list (- id 1))) ids))
              "ok"
              "ng")))

(define (main args)
  (can-put-minos? '(1 1 1 1))
  (can-put-minos? '(2 2 2 2))
  (can-put-minos? '(3 3 3 3))
  (can-put-minos? '(4 4 4 4))
  (can-put-minos? '(5 5 5 5))
  (can-put-minos? '(1 2 2 3))
  (can-put-minos? '(1 4 4 5))
  0) ; exit code

#coding:utf-8

import copy


class packField:
    @staticmethod
    def strToBitpattern(patternString):
        n = 0
        for s in patternString:
            if s == 'x':
                n |= 1
                n <<= 1
            elif s == '_':
                n <<= 1
            else:
                pass

        while n & 1 == 0:
            n >>= 1
        return n

    def __init__ (self):
        self.field = packField.strToBitpattern(
                '''
                xxxxxx
                x____x
                x____x
                x____x
                x____x
                xxxxxx
                ''')

        self.block = {}
        self.block['I'] = []
        self.block['O'] = []
        self.block['T'] = []
        self.block['L'] = []
        self.block['Z'] = []

        self.block['I'].append(
            packField.strToBitpattern(
            '''xxxx'''
            )
        )
        self.block['I'].append(
            packField.strToBitpattern(
                '''
                x_____
                x_____
                x_____
                x_____
                ''')
        )
        self.block['O'].append(
            packField.strToBitpattern(
                '''
                xx____
                xx____
                ''')
        )

        self.block['T'].append(
            packField.strToBitpattern(
                '''
                _x____
                xxx___
                ''')
        )
        self.block['T'].append(
            packField.strToBitpattern(
                '''
                xxx___
                _x____
                ''')
        )
        self.block['T'].append(
            packField.strToBitpattern(
                '''
                x_____
                xx____
                x_____
                ''')
        )
        self.block['T'].append(
            packField.strToBitpattern(
                '''
                _x____
                xx____
                _x____
                ''')
        )

        self.block['L'].append(
            packField.strToBitpattern(
                '''
                x_____
                x_____
                xx____
                ''')
        )

        self.block['L'].append(
            packField.strToBitpattern(
                '''
                _x____
                _x____
                xx____
                ''')
        )
        self.block['L'].append(
            packField.strToBitpattern(
                '''
                xx____
                _x____
                _x____
                ''')
        )
        self.block['L'].append(
            packField.strToBitpattern(
                '''
                xx____
                x_____
                x_____
                ''')
        )
        self.block['L'].append(
            packField.strToBitpattern(
                '''
                xxx___
                x_____
                ''')
        )
        self.block['L'].append(
            packField.strToBitpattern(
                '''
                xxx___
                __x___
                ''')
        )
        self.block['L'].append(
            packField.strToBitpattern(
                '''
                x_____
                xxx___
                ''')
        )
        self.block['L'].append(
            packField.strToBitpattern(
                '''
                __x___
                xxx___
                ''')

        )
        self.block['Z'].append(
            packField.strToBitpattern(
                '''
                xx____
                _xx___
                ''')
        )
        self.block['Z'].append(
            packField.strToBitpattern(
                '''
                _xx___
                xx____
                ''')
        )
        self.block['Z'].append(
            packField.strToBitpattern(
                '''
                x_____
                xx____
                _x____
                ''')
        )
        self.block['Z'].append(
            packField.strToBitpattern(
                '''
                _x____
                xx____
                x_____
                ''')
        )

        print self.field
        print self.block

    def solve(self, blocks, field = None):
        if blocks == []:
            return True

        if field == None:
            field = self.field

        for pattern in self.block[blocks[0]]:
            while pattern < field:
                if field & pattern == 0:
                    field ^= pattern
                    result = self.solve(blocks[1:], field)
                    if result == True:
                        return True
                    field ^= pattern
                pattern <<= 1
        return False




if __name__ == "__main__":
    p = packField()
    print 'IIII', p.solve(['I','I','I','I',])
    print 'OOOO', p.solve(['O','O','O','O',])
    print 'IOOT', p.solve(['I','O','O','T',])
    print 'LZLZ', p.solve(['L','Z','L','Z',])
    print 'IZZZ', p.solve(['I','Z','Z','Z',])

import Data.List
import Data.Maybe(isJust, mapMaybe)
import Data.Tree(unfoldTree, levels)

initialState = replicate 16 0 -- 空箱
b1 = [[1, 1, 1, 1]]
b2 = [[1, 1], [1, 1]]
b3 = [[1, 1, 1], [0, 1, 0]]
b4 = [[1, 1, 1], [1, 0, 0]]
b5 = [[1, 1, 0], [0, 1, 1]]

packBox [] = []
packBox b  = [take 4 b] ++ (packBox $ drop 4 b)
unpackBox b = concat b

rotate b d = case (d `mod` 360 + 360) `mod` 360 of
  0 -> b
  90 -> reverse $ transpose b
  180 -> flip rotate  90 $ rotate b 90
  270 -> flip rotate 180 $ rotate b 90

normalize b = unfoldr f (0, b) --箱の大きさに正規化
  where f (4, _     ) = Nothing
        f (i, (x:xs)) = Just (take 4 $ x ++ (repeat 0), (i + 1, xs))
        f (i, _     ) = Just ([0, 0, 0, 0], (i + 1, []))

horizontalPatterns b = if any (/= 0) $ b' !! 3 then [b]
                       else b : (horizontalPatterns $ transpose $ [last b'] ++ (take 3 b'))
  where b' = transpose b

verticalPatterns   b = if any (/= 0) $ b !! 3 then [b]
                       else b : (verticalPatterns $ [last b] ++ (take 3 b))

-- 指定されたブロックの全ての配置パターンを生成
generatePatterns b = concatMap verticalPatterns $ concatMap horizontalPatterns ps
  where ps = nub
             $ (normalize $ reverse b) : (normalize $ reverse $ rotate b 90) -- 反転パターン
             : (map (\d -> normalize $ rotate b d) [0, 90, 180, 270])        -- 回転パターン

listOfPatterns = map ((map unpackBox) . generatePatterns) [b1, b2, b3, b4, b5]

listOfBlocks ps = sort $ f ps listOfPatterns
  where f []       _           = ""
        f _        []          = ""
        f pps'@(p':ps') (x:xs) = case find (== p') x of
                              Just i -> (show (length listOfPatterns - length xs)) ++ (f ps' listOfPatterns)
                              otherwise -> f pps' xs

solutions = sortBy (\a b -> compare (fst a) (fst b)) $ map (\x -> (listOfBlocks x, x))
            $ nub $ map (sort . snd) $ flip (!!) 4 $ levels $ unfoldTree f (initialState, [])
  where f x@(b, ps) = (x, mapMaybe g $ concat listOfPatterns)
          where g p = if any (1 <) b' then Nothing else Just (b', p : ps)
                  where b' = zipWith (+) b p

solve s = let s' = sort s in
            if isJust $ find (\x -> s' == (fst x)) solutions then True else False

main = do mapM_ f solutions
          putStrLn $ "Number of solutions: " ++ (show $ length solutions)
          putStrLn ""
          putStr "Can put {1,1,2,2}? : "
          print $ solve "1122"
          putStr "Can put {2,3,4,5}? : "
          print $ solve "2345"
          putStr "Can put {4,4,5,5}? : "
          print $ solve "4455"
  where f x = do putStrLn $ "<" ++ (fst x) ++ ">"
                 mapM_ g $ map packBox $ snd x
          where g x' = do mapM_ print x'
                          putStrLn ""

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace hakodume
{
    class Program
    {
        static void Main(string[] args)
        {
            var a1 = new Mino(new int[,]{
                            {1,1,1,1}
                        }, 1);
            var a2 = new Mino(new int[,]{
                            {1},
                            {1},
                            {1},
                            {1}
                        }, 1);

            var b = new Mino(new int[,]{
                            {2,2},
                            {2,2}
                       }, 2);

            var c1 = new Mino(new int[,]{
                            {3,3,3},
                            {0,3,0}
                        },3);
            var c2 = new Mino(new int[,]{
                            {3,0},
                            {3,3},
                            {3,0}
                        },3);
            var c3 = new Mino(new int[,]{
                            {0,3},
                            {3,3},
                            {0,3}
                        },3);
            var c4 = new Mino(new int[,]{
                            {0,3,0},
                            {3,3,3}
                        },3);
            var d1 = new Mino(new int[,]{
                            {4,4,4},
                            {4,0,0}
                        },4);
            var d2 = new Mino(new int[,]{
                            {4,4},
                            {0,4},
                            {0,4}
                        },4);
            var d3 = new Mino(new int[,]{
                            {0,0,4},
                            {4,4,4}
                        },4);
            var d4 = new Mino(new int[,]{
                            {4,0},
                            {4,0},
                            {4,4}
                        },4);
            var e1 = new Mino(new int[,]{
                            {5,5,0},
                            {0,5,5}
                        },5);
            var e2 = new Mino(new int[,]{
                            {0,5},
                            {5,5},
                            {5,0}
                        },5);

            var minos = new List<Mino> { a1, a2, b, c1, c2, c3, c4, d1, d2, d3, d4, e1, e2 };

            Box box = new Box(minos);

            box.Solve(1);
            box.DisplayAll();
        }

        class Mino
        {
            private int[,] mino;

            public Mino( int[,] mino, int pattern )
            {
                this.mino = mino;
                this.Pattern = pattern;
            }

            public int RowLength { get { return mino.GetLength(0); } }
            public int ColomnLength { get { return mino.GetLength(1); } }
            public int Pattern { get; private set; }
            public int GetValue(int row, int col)
            {
                return mino[row, col];
            }
        }

        class Box
        {
            private int[,] box = {
                           {0,0,0,0},
                           {0,0,0,0},
                           {0,0,0,0},
                           {0,0,0,0}
                       };
            private int RowLength { get { return box.GetLength(0); } }
            private int ColomnLength { get { return box.GetLength(1); } }
            private int GetValue(int row, int col)
            {
                return box[row, col];
            }
            private void SetValue(int row, int col, int value)
            {
                box[row, col] = value;
            }

            private List<Mino> minos;

            public Box(List<Mino> minos)
            {
                this.minos = minos;
            }

            private List<int[,]> boxes = new List<int[,]>();
            private int[] pattern = new int[4];
            private List<int[]> patterns = new List<int[]>();

            public void DisplayAll()
            {
                foreach (var b in boxes)
                {
                    for (int i = 0; i < RowLength; ++i)
                    {
                        for (int j = 0; j < ColomnLength; ++j)
                        {
                            Console.Write("{0}", b[i, j]);
                        }
                        Console.WriteLine();
                    }
                    Console.WriteLine();
                }

                foreach (var p in patterns)
                {
                    foreach (var i in p)
                    {
                        Console.Write(i);
                    }
                    Console.WriteLine();
                }

                Console.WriteLine("組み合わせ積み木のパターン数：{0}", patterns.Count);
                Console.WriteLine("重複のない詰め方の数：{0}", boxes.Count);
            }
            
            private void Record()
            {
                var pattern_sorted = pattern.Clone() as int[];
                Array.Sort<int>(pattern_sorted);

                if (!ExistPatternMino(pattern_sorted))
                {
                    patterns.Add(pattern_sorted);
                }

                if (!ExistPatternBox(box))
                {
                    boxes.Add(box.Clone() as int[,]);
                }
            }

            private bool ExistPatternMino(int[] pattern)
            {
                return patterns.Any( p => EqualArray( p, pattern ) );
            }

            private bool ExistPatternBox(int[,] box)
            {
                return boxes.Any(r => EqualBox(r, box)) ||
                    boxes.Any(r => EqualBox(r, Rotate(box, Rotation._90 ))) ||
                    boxes.Any(r => EqualBox(r, Rotate(box, Rotation._180 ))) ||
                    boxes.Any(r => EqualBox(r, Rotate(box, Rotation._270 ))) ||
                    boxes.Any(r => EqualBox(r, Rotate(box, Rotation._y ))) ||
                    boxes.Any(r => EqualBox(r, Rotate(box, Rotation._90y ))) ||
                    boxes.Any(r => EqualBox(r, Rotate(box, Rotation._180y ))) ||
                    boxes.Any(r => EqualBox(r, Rotate(box, Rotation._270y )));
            }

            private int[,] Rotate(int[,] box_s, Rotation rotation)
            {
                int[,] box_d = {
                           {0,0,0,0},
                           {0,0,0,0},
                           {0,0,0,0},
                           {0,0,0,0}
                       };
                
                switch (rotation)
                {
                    case Rotation._90:
                        for (int i = 0; i < 4; i++)
                        {
                            for (int j = 0; j < 4; j++)
                            {
                                box_d[3 - j, i] = box_s[i, j];
                            }
                        }
                        break;
                    case Rotation._180:
                        for (int i = 0; i < 4; i++)
                        {
                            for (int j = 0; j < 4; j++)
                            {
                                box_d[3 - i, 3 - j] = box_s[i, j];
                            }
                        }
                        break;
                    case Rotation._270:
                        for (int i = 0; i < 4; i++)
                        {
                            for (int j = 0; j < 4; j++)
                            {
                                box_d[j, 3 - i] = box_s[i, j];
                            }
                        }
                        break;
                    case Rotation._y:
                        for (int i = 0; i < 4; i++)
                        {
                            for (int j = 0; j < 4; j++)
                            {
                                box_d[3 - i, j] = box_s[i, j];
                            }
                        }
                        break;
                    case Rotation._90y:
                        for (int i = 0; i < 4; i++)
                        {
                            for (int j = 0; j < 4; j++)
                            {
                                box_d[j, i] = box_s[i, j];
                            }
                        }
                        break;
                    case Rotation._180y:
                        for (int i = 0; i < 4; i++)
                        {
                            for (int j = 0; j < 4; j++)
                            {
                                box_d[i, 3 - j] = box_s[i, j];
                            }
                        }
                        break;
                    case Rotation._270y:
                        for (int i = 0; i < 4; i++)
                        {
                            for (int j = 0; j < 4; j++)
                            {
                                box_d[3 - j, 3 - i] = box_s[i, j];
                            }
                        }
                        break;
                }

                return box_d;
            }

            private enum Rotation
            {
                _90,
                _180,
                _270,
                _y,
                _90y,
                _180y,
                _270y
            }

            private bool EqualBox(int[,] lhs, int[,] rhs)
            {
                return Enumerable.Range(0, lhs.GetLength(0)).All(i =>
                    Enumerable.Range(0, lhs.GetLength(1)).All(j =>
                        lhs[i, j] == rhs[i, j]
                    ));
            }

            private bool EqualArray(int[] lhs, int[] rhs)
            {
                return Enumerable.Range(0, lhs.Length).All(i => lhs[i] == rhs[i]);
            }

            private bool CanPut(int row, int col, Mino mino)
            {
                if (row + mino.RowLength > RowLength ||    col + mino.ColomnLength > ColomnLength)
                {
                    return false;
                }

                return Enumerable.Range(0, mino.RowLength).Any(i =>
                    Enumerable.Range(0, mino.ColomnLength).Any(j =>
                        GetValue(row + i, col + j) != 0 && mino.GetValue(i, j) != 0)) ? false : true;
            }

            private void Put(int row, int col, Mino mino, int n)
            {
                for (int i = 0; i < mino.RowLength; i++)
                {
                    for (int j = 0; j < mino.ColomnLength; j++)
                    {
                        if (mino.GetValue(i, j) != 0)
                        {
                            SetValue(row+i, col+j, mino.GetValue(i, j));
                        }
                    }
                }
                pattern[n - 1] = mino.Pattern;
            }

            private void Remove(int row, int col, Mino mino)
            {
                for (int i = 0; i < mino.RowLength; i++)
                {
                    for (int j = 0; j < mino.ColomnLength; j++)
                    {
                        if (mino.GetValue(i, j) != 0)
                        {
                            SetValue(row+i, col+j, 0);
                        }
                    }
                }
            }

            public void Solve(int n)
            {
                for (int row = 0; row < RowLength; row++)
                {
                    if (CheckFilledRow(row))
                    {
                        continue;
                    }

                    for (int col = 0; col < ColomnLength; col++)
                    {
                        if (CheckFilledColomn(col))
                        {
                            continue;
                        }

                        foreach (var mino in minos)
                        {
                            if (CanPut(row, col, mino))
                            {
                                Put(row, col, mino, n);

                                if (n != 4)
                                {
                                    Solve(n + 1);
                                }
                                else
                                {
                                    Record();
                                }
                                Remove(row, col, mino);
                            }
                        }

                        if (GetValue(row, col) == 0)
                        {
                            return;
                        }
                    }
                }
            }

            private bool CheckFilledRow(int row)
            {
                return Enumerable.Range(0, ColomnLength).All(col => GetValue(row, col) != 0);
            }
            private bool CheckFilledColomn(int col)
            {
                return Enumerable.Range(0, RowLength).All(row => GetValue(row, col) != 0);
            }
        }
    }
}

| blocks extent rec results |

blocks := {
  Form extent: 4@1 fromArray: #(2r1111e28) offset: nil.
  Form extent: 2@2 fromArray: #(2r11e30 2r11e30) offset: nil.
  Form extent: 3@2 fromArray: #(2r111e29 2r010e29) offset: nil.
  Form extent: 3@2 fromArray: #(2r111e29 2r100e29) offset: nil.
  Form extent: 3@2 fromArray: #(2r110e29 2r011e29) offset: nil}.
extent := 4@4.

blocks := blocks collect: [:ori |
  | specs |
  specs := Set new.
  #(0 90 180 270) do: [:angle |
    | rot |
    rot := (ori rotateBy: angle) trimBordersOfColor: Color white.
    specs add: {rot extent. rot bits}.
    rot := rot flipBy: #horizontal centerAt: 0@0.
    specs add: {rot extent. rot bits}].
    specs collect: [:spec | Form extent: spec first depth: 1 bits: spec second]].

results := Set new.
(1 to: 5) asDigitsToPower: 4 do: [:comb |
  comb isSorted ifTrue: [
    | box |
    comb printString displayAt: 0@0.
    box := Form extent: extent.
    rec := nil.
    rec := [:prevBox :rest |
      | trials currBox |
      rest ifEmpty: [results add: comb copy] ifNotEmpty: [
        trials := blocks at: rest first.
        trials do: [:currBlk |
        (0 to: 4 - currBlk width) do: [:xx | (0 to: 4 - currBlk height) do: [:yy | 
          currBlk displayOn: (currBox := prevBox deepCopy) at: xx@yy rule: Form paint.
          currBox primCountBits = (4 * (5 - rest size)) ifTrue: [
            rec copy fixTemps value: currBox value: rest allButFirst]]]]]].
    rec copy fixTemps value: box value: comb]].
^results asArray sort: [:a :b | (b - a detect: [:delta | delta abs > 0] ifNone: [0]) >= 0]

"=> #(
  #(1 1 1 1)
  #(1 1 2 2)
  #(1 1 4 4)
  #(1 2 4 4)
  #(1 3 3 4)
  #(1 4 4 5)
  #(2 2 2 2)
  #(2 2 4 4)
  #(3 3 3 3)
  #(3 3 4 5)
  #(4 4 4 4)
  #(4 4 5 5))

let pieces = [|
        ((1,0),[|(0,0);(1,0);(2,0);(3,0)|]);((1,1),[|(0,0);(0,1);(0,2);(0,3)|]);
        ((2,0),[|(0,0);(1,0);(0,1);(1,1)|]);
        ((3,0),[|(0,0);(1,0);(2,0);(1,1)|]);((3,1),[|(0,0);(0,1);(1,1);(0,2)|]);                       
        ((3,2),[|(0,0);(-1,1);(0,1);(1,1)|]);((3,3),[|(0,0);(-1,1);(0,1);(0,2)|]);                       
        ((4,0),[|(0,0);(1,0);(2,0);(0,1)|]);((4,1),[|(0,0);(1,0);(1,1);(1,2)|]);                       
        ((4,2),[|(0,0);(0,1);(0,2);(1,2)|]);((4,3),[|(0,0);(-2,1);(-1,1);(0,1)|]);
        ((4,4),[|(0,0);(1,0);(2,0);(2,1)|]);((4,5),[|(0,0);(1,0);(0,1);(0,2)|]);                       
        ((4,6),[|(0,0);(0,1);(1,1);(2,1)|]);((4,7),[|(0,0);(0,1);(-1,2);(0,2)|]);
        ((5,0),[|(0,0);(1,0);(1,1);(2,1)|]);((5,1),[|(0,0);(-1,1);(0,1);(-1,2)|]);                       
//5の逆転     ((5,2),[|(0,0);(0,1);(1,1);(1,2)|]);((5,3),[|(0,0);(1,0);(-1,1);(0,1)|])
             |]
let Mdim = 4 
let isPutable p (x,y) (arr:int[,])=
    let isThatPositionPutable (x1,y1) = 
        0 <= x+x1 && 0 <= y+y1 && 
        x+x1<Mdim && y+y1<Mdim && arr.[y+y1,x+x1] = 0
    let (_,rPositions) = p     
    Array.forall isThatPositionPutable rPositions    

let put p (x,y) (arr:int[,]) =
    let putOneLocation pID  (x1,y1) = arr.[y+y1,x+x1] <- pID
    let ((pId,_),rPositions) = p
    Array.map (putOneLocation pId) rPositions

let remove p (x,y) (arr:int[,]) =
   let removeOneLocation (x1,y1) = arr.[y+y1,x+x1] <- 0
   let (_,rPositions) = p     
   Array.map removeOneLocation rPositions

let findNextPutLoc (arr:int[,]) =
    let mutable isFirst = true
    let  result = ref None
    for y in 0 .. Mdim-1 do
       for x in 0 .. Mdim-1 do
            if arr.[y,x] = 0 && isFirst then
                result := Some((x,y))
                isFirst <- false
    !result
 
let check in_arr =
    let sucHisLst = ref []  
    let rec search hist  (arr:int[,]) =
        if findNextPutLoc arr = None then //成功!全部置けた
            sucHisLst := hist:: !sucHisLst
        else
            let (x,y) = (findNextPutLoc arr).Value
            for p in pieces do
                if isPutable p (x,y) arr then
                    put p (x,y) arr |> ignore
                    search (((x,y),p)::hist) arr
                    remove p (x,y) arr |> ignore
    search [] in_arr                       
    sucHisLst
 
let initArr = Array2D.create Mdim Mdim 0 //0は何も置かれていない状態 
let solutions = !(check initArr)

printfn "\n置き方の総数...%d\n" solutions.Length

///ここから「箱につめることができる積み木の組み合わせの総数」の処理

let extractKindlistAndSort eles  =
    let t = List.map (fun ((x,y),((k,_),_)) -> k) eles
    List.sort t

let combSet = solutions 
              |> List.map extractKindlistAndSort 
              |> Set.ofList
Set.iter (fun x -> printfn "%A" x ) combSet
printfn "\n組み合わせの総数...%d\n" combSet.Count

///ここから「上記総数を、異なる詰め方の個数別にカウント
//　（箱の回転・裏返しで一致するものは同一視します）」の処理

//縦横2*Mdimの配列を準備して境界線を引きながら、もう一度積み木を置いていく。
//それから、回転裏返しで一致するものを除きながら、解のリストを作る。

let Connected = -1
let Discreet = -2

let put2 p (x,y) (arr:int[,]) =
    let putOneLocation pID  (x1,y1) = arr.[2*y+2*y1,2*x+2*x1] <- pID
    let ((pId,_),rPositions) = p
    Array.map (putOneLocation pId) rPositions

let upDateConnection (arr:int[,]) =
    for c in 0 .. Mdim - 1 do
        for r in 0 .. Mdim - 2 do
            if arr.[2*r,2*c] <> 0 && arr.[2*r,2*c]=arr.[2*r + 2,2*c] && arr.[2*r+1,2*c] = 0
                then arr.[2*r+1,2*c] <- Connected 
            if arr.[2*r,2*c] <> arr.[2*r + 2,2*c] && arr.[2*r+1,2*c] = 0
                then arr.[2*r+1,2*c] <- Discreet 
    for c in 0 .. Mdim - 2 do
        for r in 0 .. Mdim - 1 do
            if arr.[2*r,2*c] <> 0 && arr.[2*r,2*c]=arr.[2*r,2*c+2] && arr.[2*r,2*c+1] = 0
                then arr.[2*r,2*c+1] <- Connected 
            if arr.[2*r,2*c] <> arr.[2*r,2*c+2] && arr.[2*r,2*c+1] = 0
                then arr.[2*r,2*c+1] <- Discreet 
             
let rotateArr (arr:int[,]) =
    let tempArr = Array2D.create (2*Mdim-1) (2*Mdim-1) 0
    for c in 0 .. 2*Mdim - 2 do
        for r in 0 .. 2*Mdim - 2 do
            tempArr.[r,(2*Mdim-1) - c - 1 ] <- arr.[c,r]
    tempArr

let reverseArr (arr:int[,]) =
    let tempArr = Array2D.create (2*Mdim-1) (2*Mdim-1) 0
    for c in 0 .. 2*Mdim - 2 do
        for r in 0 .. 2*Mdim - 2 do
            tempArr.[r,c] <- arr.[c,r]
    tempArr

let makeUpPA ele =
    let tempArr = Array2D.create (2*Mdim-1) (2*Mdim-1) 0
    let t = List.fold (fun s ((x,y),((k,id),a)) ->
                            put2 ((k,id),a)(x,y) tempArr |>ignore;
                            upDateConnection tempArr|> ignore ;
                            k :: s) [] ele
    ((List.sort t),tempArr)

let isEqueWRR oriP uP oriArr arr = //回転反転すると等しくなる 
    let rec isEqueWRRSub arr1 arr2 count =
        if count = 4 then 
            false
        else
          if oriArr = arr1 || oriArr = arr2 then
            true
          else
            isEqueWRRSub (rotateArr arr1) (rotateArr arr2) (count + 1)
    if oriP <> uP then
        false
    else
        isEqueWRRSub arr (reverseArr arr) 0
              
let makeUpSolutions2 sols =
    let isInclude ele lst =
        let (usedPiece,arr0) = ele
        List.exists(fun (u,arr) ->isEqueWRR usedPiece u arr0 arr) lst

    let rec musSub lst res =
        match lst with
        |[]
            ->res
        |hd::tl 
            ->let t = makeUpPA hd
              if (isInclude t res)  then
                musSub tl res
              else
                musSub tl (t::res)
    musSub sols []


let solutions2 = (makeUpSolutions2 solutions)

printf "異なる詰め方の個数...%d"  solutions2.Length

///ここまでで答え終わり
//ここから見やすく答えを表示

let dispEach (kLst, (arr : int [,])) =
    printfn "\n\n%A" kLst
    for r in 0 .. 2*Mdim - 2 do
        printfn ""
        for c in 0 .. 2*Mdim - 2 do
          let st =  
                match arr.[r,c] with
                |i  when i = 0 || i = Connected -> " "
                |i  when i = Discreet && (c % 2 = 1 && r % 2 = 0) -> "|"
                |i  when i = Discreet && (c % 2 = 0 && r % 2 = 1) -> "-"
                |i   -> i.ToString()
          printf "%s" st     
    printfn ""

List.iter (fun ele -> dispEach ele) (List.sort solutions2)