/* Some Polyomino puzzles in Picat. Some of the Polyomino puzzls from From Adrian Groza "Modelling Puzzles in First Order Logic" Puzzles: - Puzzle 122. A simple polyomino - Puzzle 123. Rotating polyomino - Puzzle 124. Ten-Yen - Puzzle 125. Rotating Ten-Yen - Puzzle 126. A 4 x 5 rectangle - Puzzle 127. The 12 pentominoes - Puzzle 128. Importing six pentominoes - Puzzle 129. Importing other six pentominoes - Puzzle 130. Twelve pentominoes on a chessboard - Puzzle 131. Five tetrominoes on a strange shape This is a general model for solving polyomino puzzles using a "pure CP" approach (in contrast to polyominos.pi) The solution of a puzzle is as follows 4 3 1 2 3 1 2 2 1 where the numbers represents the piece id. I.e. here are 4 pieces (1..4). Note: This is (still) not as fast as I had hoped. The function for generating symmetries uses the module rectangle_symmetries, See http://hakank.org/picat/rectangle_symmetries.pi. Note: For a faster version of solving pentominoes, see Neng-Fa's solution: https://github.com/nfzhou/Picat/blob/master/pentominoes.pi This program was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import rectangle_symmetries. % http://hakank.org/picat/rectangle_symmetries.pi import util. % import cp. import sat. % Tends to be faster than cp % import mip. % import smt. main => go. % % Show all solutions for the simplest puzzles. % go ?=> nolog, Print = false, member(Puzzle,[a_simple_polyomino, rotating_polyominos, ten_yen, rotating_ten_yen, four_by_five_rectangle ]), println(puzzle=Puzzle), data(Puzzle,Pieces,Rows,Cols), polyomino(Pieces,Rows,Cols,Print), fail, nl. go => true. % SAT: 0.096s % CP: 0.06s % % polyominos.pi % SAT: 0.07s % CP: 0.052s % go2 ?=> nolog, data(a_simple_polyomino,Pieces,Rows,Cols), polyomino(Pieces,Rows,Cols,false), fail, nl. go2 => true. % Printing all the variants % Same time as go2/0 go2_print ?=> nolog, Print = true, data(a_simple_polyomino,Pieces,Rows,Cols), polyomino(Pieces,Rows,Cols,Print), fail, nl. go2_print => true. % % SAT: 0.65s % CP: 0.08s % % polyominos.pi % SAT: 0.095s % CP: 0.073s % go3 ?=> nolog, data(rotating_polyominos,Pieces,Rows,Cols), polyomino(Pieces,Rows,Cols), fail, nl. go3 => true. % % SAT: 9.514s % CP: 0.338s % % polyominos.pi % SAT: 0.49s % CP: 1.1s % go4 ?=> nolog, data(ten_yen,Pieces,Rows,Cols), polyomino(Pieces,Rows,Cols), fail, nl. go4 => true. % % SAT: 23.934s % CP: ? % % polyominos.pi % SAT: 3.02s % CP: 13.8s % go5 ?=> nolog, data(rotating_ten_yen,Pieces,Rows,Cols), polyomino(Pieces,Rows,Cols), fail, nl. go5 => true. % % SAT: 0.985s % CP: 0.08s % % polyominos.pi % SAT: 0.912s % CP: 0.236s % go6 ?=> nolog, data(four_by_five_rectangle,Pieces,Rows,Cols), polyomino(Pieces,Rows,Cols), fail, nl. go6 => true. % % Showing all (8) solutions of the_twelve_pentominoes % SAT: 2h41min20.95s % % polyominos.pi % SAT: ??? % CP: ??? % go7 ?=> nolog, data(the_twelve_pentominoes,Pieces,Rows,Cols), polyomino(Pieces,Rows,Cols), flush(stdout), fail, nl. go7 => true. % % Time to (first) solution % SAT: 5min:40.14s % CP: ??? % % polyominos.pi % SAT: ??? % CP: ??? % go7_first_sol ?=> nolog, data(the_twelve_pentominoes,Pieces,Rows,Cols), polyomino(Pieces,Rows,Cols), % fail, nl. go7_first_sol => true. % % SAT: 31.3s % CP: 0.36s % % polyominos.pi % SAT: 115.3s % CP: 532.3s % go8 ?=> nolog, data(importing_six_pentominoes,Pieces,Rows,Cols), polyomino(Pieces,Rows,Cols), fail, nl. go8 => true. go8b ?=> nolog, data(importing_six_pentominoes_shape,Pieces,Shape), polyomino_shape(Pieces,Shape), fail, nl. go8b => true. % % SAT: 38.444s % CP: much slower % % polyominos.pi % SAT: 185.8s % CP: ??? % go9 ?=> nolog, data(importing_other_six_pentominoes,Pieces,Rows,Cols), polyomino(Pieces,Rows,Cols), fail, nl. go9 => true. % % Filling a non rectangular shape % % SAT: 5.2s % CP: 16min48.63s % % polyominos.pi % SAT: 2.3s % CP: 8.830s % go10 ?=> nolog, data(five_tetrominoes_on_a_strange_shape,Pieces,Shape), polyomino_shape(Pieces,Shape), fail, nl. go10 => true. % % Time to first solution: % SAT: 4min30.03s % CP: % % Total time (all solutions) % SAT: ?? % CP: ?? % go11 ?=> nolog, data(twelve_pentominoes_on_a_chessboard,Pieces,Shape), polyomino_shape(Pieces,Shape), fail, nl. go11 => true. /* polyomino(Pieces,Rows,Cols) Solve a polyomino configuration. */ polyomino(Pieces,Rows,Cols) => polyomino(Pieces,Rows,Cols,false). polyomino(Pieces,Rows,Cols,Print) => garbage_collect(600_000_000), NumPieces = Pieces.len, println([rows=Rows,cols=Cols,numPieces=NumPieces]), % % Generate all possible variants that can fill the main grid (X) % with this shape and its rotation/flip variants. % AllPs = [], foreach(Ps in Pieces) if Print then nl, println(ps=Ps=Ps.len) end, NewPs = [], foreach(P in Ps) if Print then println(piece=P), println("Piece to place:"), foreach(Row in P) println(Row) end, nl end, Rs = [ R.len : R in P], RsLen = Rs.len, foreach(StartI in 1..Rows,StartI+RsLen-1 <= Rows) foreach(StartJ in 1..Cols) NewP = new_array(Rows,Cols), bind_vars(NewP,0), foreach(R in 1..RsLen) foreach(C in 1..Rs[R],StartJ+Rs[R]-1 <= Cols) IR = StartI+R-1, JC = StartJ+C-1, if IR <= Rows, JC <= Cols, P[R,C] > 0 then NewP[IR,JC] := 1 end end end, if NewP.array_matrix_to_list_matrix.flatten.sum > 0 then NewPs := NewPs ++ [NewP], if Print then println(newP=NewP), foreach(Row in NewP) println(Row) end, nl end end end end end, if Print then println(numVariants=NewPs.len) end, AllPs := AllPs ++ [NewPs] end, println(num_variants=[PP.len : PP in AllPs]), X = new_array(Rows,Cols), X :: 1..NumPieces, Variant = new_list(NumPieces), foreach(P in 1..NumPieces) ThesePs = AllPs[P], Variant[P] :: 1..ThesePs.len, Flatten = [TT.array_matrix_to_list_matrix : TT in ThesePs].flatten, FlattenLen = Flatten.len, foreach(I in 1..Rows) foreach(J in 1..Cols) % Select a variant Ix :: 1..FlattenLen, Ix #= (Variant[P]-1)*Rows*Cols + (I-1)*Cols + J, element(Ix,Flatten,Val), Val #= 1 #<=> X[I,J] #= P end end, sum([X[I,J] #= P : I in 1..Rows,J in 1..Cols]) #= ThesePs[1].array_matrix_to_list_matrix.flatten.sum end, Vars = X.vars ++ Variant, println(solve), % solve($[ff,split],Vars), solve($[constr],Vars), println(variant=Variant), foreach(I in 1..Rows) foreach(J in 1..Cols) printf("%3d",X[I,J]) end, nl end, nl. % end polyomino/3 /* polyomino_shape: with a certain shape */ polyomino_shape(Pieces,Shape) => polyomino_shape(Pieces,Shape,false). polyomino_shape(Pieces,Shape,Print) => garbage_collect(600_000_000), Rows = Shape.len, Cols = Shape[1].len, NumPieces = Pieces.len, println([rows=Rows,cols=Cols,numPieces=NumPieces]), % % Generate all possible variants that can fill the main grid (X) % with this shape and its rotation/flip variants. % AllPs = [], foreach(Ps in Pieces) if Print then nl, println(ps=Ps=Ps.len) end, NewPs = [], foreach(P in Ps) if Print then println(piece=P), println("Piece to place:"), foreach(Row in P) println(Row) end, nl end, Rs = [ R.len : R in P], RsLen = Rs.len, foreach(StartI in 1..Rows,StartI+RsLen-1 <= Rows) foreach(StartJ in 1..Cols) NewP = new_array(Rows,Cols), bind_vars(NewP,0), foreach(R in 1..RsLen) foreach(C in 1..Rs[R],StartJ+Rs[R]-1 <= Cols) IR = StartI+R-1, JC = StartJ+C-1, if IR <= Rows, JC <= Cols, P[R,C] > 0 then NewP[IR,JC] := 1 end end end, if NewP.array_matrix_to_list_matrix.flatten.sum > 0 then NewPs := NewPs ++ [NewP], if Print then println(newP=NewP), foreach(Row in NewP) println(Row) end, nl end end end end end, if Print then println(numVariants=NewPs.len) end, AllPs := AllPs ++ [NewPs] end, println(num_variants=[PP.len : PP in AllPs]), X = new_array(Rows,Cols), X :: 0..NumPieces, foreach(I in 1..Rows, J in 1..Cols) if Shape[I,J] == 0 then X[I,J] #= 0 else X[I,J] #> 0 end end, Variant = new_list(NumPieces), foreach(P in 1..NumPieces) ThesePs = AllPs[P], Variant[P] :: 1..ThesePs.len, Flatten = [TT.array_matrix_to_list_matrix : TT in ThesePs].flatten, FlattenLen = Flatten.len, foreach(I in 1..Rows) foreach(J in 1..Cols,Shape[I,J] > 0) % Select a variant Ix :: 1..FlattenLen, Ix #= (Variant[P]-1)*Rows*Cols + (I-1)*Cols + J, element(Ix,Flatten,Val), Val #= 1 #<=> X[I,J] #= P end end end, Vars = X.vars ++ Variant, println(solve), % solve($[ff,split],Vars), solve($[constr],Vars), println(variant=Variant), foreach(I in 1..Rows) foreach(J in 1..Cols) printf("%3d",X[I,J]) end, nl end, nl. % end polyomino_shape/3 print_mat(M) => foreach(Row in M) println(Row) end, nl. /* Here are the twelve pentonomies t: x x x x x u: x x x x x v: x x x x x w: x x x x x x: x x x x x y: x x x x x z: x x x x x f: x x x x x i: x x x x x l: x x x x x p: x x x x x n: x x x x x */ pentominoes() = Map => Map = new_map([ t = [[1,1,1], [0,1,0], [0,1,0]], u = [[1,0,1], [1,1,1]], v = [[1,0,0], [1,0,0], [1,1,1]], w = [[1,0,0], [1,1,0], [0,1,1]], x = [[0,1,0], [1,1,1], [0,1,0]], y = [[0,1], [1,1], [0,1], [0,1]], z = [[1,1,0], [0,1,0], [0,1,1]], f = [[0,1,1], [1,1,0], [0,1,0]], i = [[1], [1], [1], [1], [1]], l = [[1,0], [1,0], [1,0], [1,1]], p = [[0,1], [1,1], [1,1]], n = [[0,1], [0,1], [1,1], [1,0]] ]). /* Data. The general idea is to list all the pieces in a master list [ % Piece 1 and it rotational variants % Piece 2 and its rotational variants % ... ] A piece is represented as an rectangle where 0s are in place of the empty spaces for this pieces. For simplification, the non-empty spaces has been numbered from 1 and onward, but the important thing is that they are != 0. */ /* """ Puzzle 122. A simple polyomino This puzzle uses one monomino, one domino, and two trominoes, for a total of nine squares. Assume that you cannot rotate the shapes. Group the four shapes in a 3 × 3 grid. """ The shapes: x x x x x x x x x 1 2 3 4 (Id) This is tested in go2/0. Note: The next puzzle ("Puzzle 123. Rotating polyomino" below) also asks for rotations of the pieces. */ data(a_simple_polyomino,Pieces,Rows,Cols) :- % Dimension of the grid to fill Rows = 3, Cols = 3, Pieces = [ % 1 [ [[1], [1], [1]] ], % 2 [ [[1,0], [1,1]] ], % 3 [ [[1], [1]] ], % 4 [ [[1]] ] ]. /* """ Puzzle 123. Rotating polyomino This puzzle uses one monomino, one domino, and two trominoes, for a total of nine squares. Assume that you cannot rotate the shapes. Group the four shapes in a 3 × 3 grid. """ The shapes: x x x x x x x x x 1 2 3 4 (Id) There are 48 solutions, for example [1,4,3] [1,2,3] [1,2,2] [4,3,1] [2,3,1] [2,2,1] [1,2,4] [1,2,2] [1,3,3] ... [4,2,3] [2,2,3] [1,1,1] [1,1,1] [3,3,2] [4,2,2] [3,3,2] [4,2,2] [1,1,1] Note that the representation of the shapes only uses 0 and 1, to ensure that the shape x x x only has the variant x x x If it would be represented as [1,2,3] then [3,2,1] would be generated as a variant. The parameter true is for just generating the 4 rotational symmetries, and not the 4 flips This is tested in go3/0. */ data(rotating_polyominos,Pieces,Rows,Cols) :- % Dimension of the grid to fill Rows = 3, Cols = 3, Pieces = [ generate_distinct_symmetries([[1,1,1]],true), % 1 generate_distinct_symmetries([[1,0],[1,1]],true), % 2 generate_distinct_symmetries([[1,1]],true), % 3 generate_distinct_symmetries([[1]],true) % 5 ]. /* """ Puzzle 124. Ten-Yen Ten-yen puzzle consists of ten polyominoes as depicted below (Fig. 12.6). For now, we assume that: shapes cannot be rotated and there are no constraints on the colours of each shape. The task is to assemble the shapes in a 6 × 6 grid. (taken from http://www.gamepuzzles.com/polycub3.htm and published in 1950 by Multiple Prod- ucts Corporation and used here for educational purpose) """ There are two solutions: 1 2 1 3 3 4 1 1 1 3 7 4 5 5 3 3 7 4 5 6 6 7 7 7 5 8 6 6 10 10 8 8 8 9 9 10 1 2 1 3 3 4 1 1 1 3 7 4 5 5 3 3 7 4 5 9 9 7 7 7 5 8 6 6 10 10 8 8 8 6 6 10 This is tested in go4/0. */ data(ten_yen,Pieces,Rows,Cols) :- Rows = 6, Cols = 6, Pieces = [ % 1 [ [[1,0,1], [1,1,1]] ], % 2 [ [[1]] ], % 3) [ [[0,1,1], [0,1,0], [1,1,0]] ], % 4) [ [[1], [1], [1]] ], % 5) [ [[1,1], [1,0], [1,0]] ], % 6) [ [[1,1,0], [0,1,1]] ], % 7) [ [[0,1,0], [0,1,0], [1,1,1]] ], % 8) [ [[0,1,0], [1,1,1]] ], % 9) [ [[1,1]] ], % 10) [ [[1,1], [0,1]] ] ]. /* """ Puzzle 125. Rotating Ten-Yen Let us now rotate some of the polyominoes from the Ten-Yen puzzle. Namely, we can rotate i2, r4, and b3. Which would be a new solution in this case? (adapted from the Ten-Yen puzzle published in 1950 by Multiple Products Corporation and used here for educational purpose) """ 4 solutions: 1 2 1 3 3 4 1 1 1 3 7 4 5 5 3 3 7 4 5 6 6 7 7 7 5 8 6 6 10 10 8 8 8 9 9 10 1 2 1 3 3 4 1 1 1 3 7 4 5 5 3 3 7 4 5 9 9 7 7 7 5 8 6 6 10 10 8 8 8 6 6 10 9 5 5 8 10 10 9 5 8 8 8 10 1 5 1 3 3 4 1 1 1 3 7 4 6 6 3 3 7 4 2 6 6 7 7 7 1 2 1 3 3 4 1 1 1 3 7 4 5 5 3 3 7 4 5 6 6 7 7 7 5 8 6 6 10 9 8 8 8 10 10 9 This is tested in go5/0. */ data(rotating_ten_yen,Pieces,Rows,Cols) :- Rows = 6, Cols = 6, Pieces = [ % 1 [ [[1,0,1], [1,1,1]] ], % 2 [ [[1]] ], % 3) [ [[0,1,1], [0,1,0], [1,1,0]] ], % 4) /* [ [[1], [2], [3]], % variant [[1,2,3]] ], */ generate_distinct_symmetries([[1,1,1]],true), % 5) [ [[1,1], [1,0], [1,0]] ], % 6) [ [[1,1,0], [0,1,1]] ], % 7) [ [[0,1,0], [0,1,0], [1,1,1]] ], % 8) [ [[0,1,0], [1,1,1]] ], % 9) /* [ [[1,2]], % variant [[1], [2]] ], */ generate_distinct_symmetries([[1,1]],true), % 10) /* [ [[1,2], [0,3]], % variants [[0,1], [2,3]], [[1,0], [2,3]], [[1,2], [3,0]] ] */ generate_distinct_symmetries([[1,1],[0,1]],true) ]. /* """ Puzzle 126. A 4 x 5 rectangle Use the following four pieces to fill a 4 × 5 grid. Each shape can be rotated (taken from MCRuffy Pentomino Puzzle Book). """ The four shapes used are x x x x x x x x x x x x x x x x x x x x x x There are two solutions: 1 1 1 1 3 1 4 4 3 3 2 2 4 4 3 2 2 2 4 3 3 4 2 2 2 3 4 4 2 2 3 3 4 4 1 3 1 1 1 1 This is tested in go6/0. */ data(four_by_five_rectangle,Pieces,Rows,Cols) :- Rows = 4, Cols = 5, Pieces = [ generate_distinct_symmetries([[1,0], [1,0], [1,0], [1,1]],true), % 1 generate_distinct_symmetries([[0,1], [1,1], [1,1]],true), % 2 generate_distinct_symmetries([[0,1], [1,1], [0,1], [0,1]],true), % 3 generate_distinct_symmetries([[1,0,0], [1,1,0], [0,1,1]],true) % 4 ]. /* """ Puzzle 127. The 12 pentominoes Show that the 12 pentominoes form a 3 × 20 rectangle. (taken from Golomb (1996)) """ In this instance we allow all 8 symmetries, including flips. This is tested in go7/0 and go7_first_sol/0. The solution first: variant = [63,13,62,44,52,43,110,1,59,17,105,56] 8 12 11 11 11 11 9 6 1 4 4 4 2 2 2 2 2 10 7 7 8 12 12 12 11 9 9 6 1 1 1 4 4 3 5 5 10 10 10 7 8 8 8 12 9 9 6 6 6 1 3 3 3 3 5 5 5 10 7 7 Here are all 8 solutions found by go7/0 (2h48min54.4s) 7 7 10 2 2 2 2 2 12 9 9 6 6 6 1 3 3 3 3 8 7 10 10 10 5 5 12 12 12 11 9 9 6 1 1 1 4 4 3 8 7 7 10 5 5 5 12 11 11 11 11 9 6 1 4 4 4 8 8 8 8 3 3 3 3 1 6 6 6 9 9 12 2 2 2 2 2 10 7 7 8 3 4 4 1 1 1 6 9 9 11 12 12 12 5 5 10 10 10 7 8 8 8 4 4 4 1 6 9 11 11 11 11 12 5 5 5 10 7 7 7 7 10 5 5 5 3 3 3 3 1 6 6 6 9 9 12 8 8 8 7 10 10 10 5 5 3 4 4 1 1 1 6 9 9 11 12 12 12 8 7 7 10 2 2 2 2 2 4 4 4 1 6 9 11 11 11 11 12 8 8 8 8 4 4 4 1 6 9 11 11 11 11 12 5 5 5 10 7 7 8 3 4 4 1 1 1 6 9 9 11 12 12 12 5 5 10 10 10 7 8 3 3 3 3 1 6 6 6 9 9 12 2 2 2 2 2 10 7 7 7 7 10 2 2 2 2 2 4 4 4 1 6 9 11 11 11 11 12 8 7 10 10 10 5 5 3 4 4 1 1 1 6 9 9 11 12 12 12 8 7 7 10 5 5 5 3 3 3 3 1 6 6 6 9 9 12 8 8 8 8 12 11 11 11 11 9 6 1 4 4 4 2 2 2 2 2 10 7 7 8 12 12 12 11 9 9 6 1 1 1 4 4 3 5 5 10 10 10 7 8 8 8 12 9 9 6 6 6 1 3 3 3 3 5 5 5 10 7 7 7 7 10 5 5 5 12 11 11 11 11 9 6 1 4 4 4 8 8 8 7 10 10 10 5 5 12 12 12 11 9 9 6 1 1 1 4 4 3 8 7 7 10 2 2 2 2 2 12 9 9 6 6 6 1 3 3 3 3 8 8 8 8 12 9 9 6 6 6 1 3 3 3 3 5 5 5 10 7 7 8 12 12 12 11 9 9 6 1 1 1 4 4 3 5 5 10 10 10 7 8 12 11 11 11 11 9 6 1 4 4 4 2 2 2 2 2 10 7 7 */ data(the_twelve_pentominoes,Pieces,Rows,Cols) :- Rows = 3, Cols = 20, Ps = pentominoes(), Pieces1 = [], foreach(Type in Ps.keys.sort) P = generate_distinct_symmetries(Ps.get(Type),false), Pieces1 := Pieces1 ++ [P] end, Pieces = Pieces1. /* """ Puzzle 128. Importing six pentominoes Find two solutions to fill a 5 × 6 rectangle with the following five pentonimoes: T, W, Y, Z, I, and L. You can rotate and flip over each pentonimo. (adapted from Golomb (1996)) """ This model gives 4 solutions: 5 5 5 5 5 1 3 4 4 1 1 1 3 3 4 2 2 1 3 6 4 4 2 2 3 6 6 6 6 2 3 6 6 6 6 2 3 6 4 4 2 2 3 3 4 2 2 1 3 4 4 1 1 1 5 5 5 5 5 1 2 6 6 6 6 3 2 2 4 4 6 3 1 2 2 4 3 3 1 1 1 4 4 3 1 5 5 5 5 5 1 5 5 5 5 5 1 1 1 4 4 3 1 2 2 4 3 3 2 2 4 4 6 3 2 6 6 6 6 3 This is tested in go8/0. */ data(importing_six_pentominoes,Pieces,Rows,Cols) :- Rows = 5, Cols = 6, Ps = pentominoes(), Pieces1 = [], foreach(Type in [t,w,y,z,i,l]) P = generate_distinct_symmetries(Ps.get(Type),false), Pieces1 := Pieces1 ++ [P] end, Pieces = Pieces1. /* """ Puzzle 129. Importing other six pentominoes Find two solutions to fill a 5 × 6 rectangle with the following five pentominoes: U , V , X , F, P, and N . You can rotate and flip over each pentomino. (adapted from Golomb (1996)) """ The following solutions are found 1 1 3 2 2 2 1 3 3 3 4 2 1 1 3 4 4 2 5 5 6 6 4 4 5 5 5 6 6 6 1 1 3 2 2 2 1 3 3 3 6 2 1 1 3 4 6 2 5 5 4 4 6 6 5 5 5 4 4 6 5 5 5 4 4 6 5 5 4 4 6 6 1 1 3 4 6 2 1 3 3 3 6 2 1 1 3 2 2 2 5 5 5 6 6 6 5 5 6 6 4 4 1 1 3 4 4 2 1 3 3 3 4 2 1 1 3 2 2 2 6 6 6 5 5 5 4 4 6 6 5 5 2 4 4 3 1 1 2 4 3 3 3 1 2 2 2 3 1 1 6 4 4 5 5 5 6 6 4 4 5 5 2 6 4 3 1 1 2 6 3 3 3 1 2 2 2 3 1 1 2 2 2 3 1 1 2 6 3 3 3 1 2 6 4 3 1 1 6 6 4 4 5 5 6 4 4 5 5 5 2 2 2 3 1 1 2 4 3 3 3 1 2 4 4 3 1 1 4 4 6 6 5 5 6 6 6 5 5 5 This is tested in go9/0. */ data(importing_other_six_pentominoes,Pieces,Rows,Cols) :- Rows = 5, Cols = 6, Ps = pentominoes(), Pieces1 = [], foreach(Type in [u,v,x,f,p,n]) P = generate_distinct_symmetries(Ps.get(Type),false), Pieces1 := Pieces1 ++ [P] end, Pieces = Pieces1. /* """ Puzzle 130. Twelve pentominoes on a chessboard Using each of the twelve pentominoes, find a solution to the 8 × 8 grid with the four- square hole in the middle. (adapted from Golomb (1996)) """ This first solution is found in 4min30.03s: 5 5 5 6 8 8 8 2 12 5 5 6 6 6 8 2 12 12 12 6 1 1 8 2 9 9 12 0 0 1 1 2 11 9 9 0 0 1 10 2 11 11 9 4 4 10 10 10 11 4 4 4 3 7 10 7 11 3 3 3 3 7 7 7 Here are some other solutions: 2 3 3 3 3 4 4 9 2 3 6 4 4 4 9 9 2 11 6 6 6 9 9 12 2 11 6 0 0 12 12 12 2 11 11 0 0 12 1 1 5 11 7 7 10 1 1 8 5 5 7 10 10 10 1 8 5 5 7 7 10 8 8 8 2 7 7 7 8 8 8 6 2 7 10 7 8 6 6 6 2 10 10 10 8 5 5 6 2 1 10 0 0 5 5 5 2 1 1 0 0 4 3 3 1 1 12 9 9 4 4 3 12 12 12 11 9 9 4 3 12 11 11 11 11 9 4 3 7 7 10 2 2 2 2 2 7 10 10 10 4 4 4 6 7 7 10 4 4 6 6 6 5 5 3 0 0 9 9 6 5 5 3 0 0 12 9 9 8 5 3 12 12 12 1 9 8 3 3 12 11 1 1 1 8 8 8 11 11 11 11 1 4 9 9 12 12 8 8 8 4 4 9 9 12 7 7 8 2 4 11 9 12 12 7 8 2 4 11 0 0 7 7 5 2 11 11 0 0 1 5 5 2 6 11 10 1 1 5 5 2 6 10 10 10 1 1 3 6 6 6 10 3 3 3 3 This is tested in go11/0. */ data(twelve_pentominoes_on_a_chessboard,Pieces,Shape) :- Shape = [[1,1,1,1,1,1,1,1], [1,1,1,1,1,1,1,1], [1,1,1,1,1,1,1,1], [1,1,1,0,0,1,1,1], [1,1,1,0,0,1,1,1], [1,1,1,1,1,1,1,1], [1,1,1,1,1,1,1,1], [1,1,1,1,1,1,1,1]], Ps = pentominoes(), Pieces1 = [], foreach(Type in Ps.keys.sort) P = generate_distinct_symmetries(Ps.get(Type),false), Pieces1 := Pieces1 ++ [P] end, Pieces = Pieces1. /* """ Puzzle 131. Five tetrominoes on a strange shape Fill the following shape with five distinct tetrominoes. You can rotate and flip over each piece. (adapted from www.geogebra.org) """ The shapes: i) x x x x s) x x x x t) x x x x k) x x x x l) x x x x The shape to fill x x x x x x x x x x x x x x x x x x x x The unique solution: 0 0 1 2 2 0 0 0 0 3 1 2 2 5 0 0 3 3 1 4 4 5 5 5 0 3 1 0 4 4 0 0 SAT: 5.2s This is tested in go10/0. */ data(five_tetrominoes_on_a_strange_shape,Pieces,Shape) :- Pieces = [ generate_distinct_symmetries([[1,1,1,1]],false), % i generate_distinct_symmetries([[1,1], [1,1]],false), % s generate_distinct_symmetries([[1,1,1], [0,1,0]],false), % t generate_distinct_symmetries([[0,1,1], [1,1,0]],false), % k generate_distinct_symmetries([[1,0,0], [1,1,1]],false) % l ], Shape = [[0,0,1,1,1,0,0,0], [0,1,1,1,1,1,0,0], [1,1,1,1,1,1,1,1], [0,1,1,0,1,1,0,0] ].