Polyomino Generation

/* polys(N, Polyominoes) is true if Polyominoes is the list of all           */
/*   polyominoes of order N.                                                 */
/* e.g. polys(4, [[[1,1,1,1]], [[0,1],[1,1],[1,0]], [[1,1],[1,1]],           */
/*                [[1,1,1],[1,0,0]], [[1,1,1],[0,1,0]]]).                    */
polys(1, [[[1]]]):-!.
polys(N, Polys):-
  N > 1,
  N1 is N - 1,
  polys(N1, Polys0),
  polys_1(Polys0, [], [], Polys).

polys_1([], _, NewPolys, NewPolys).
polys_1([Poly|Polys], Orientations0, NewPolys0, NewPolys):-
  matrix_coords(Poly, Cells),
  length(Poly, Height),
  Poly=[Row|_],
  length(Row, Width),
  polys_2(Cells, Cells, Height, Width, Orientations0, Orientations1, 
          NewPolys0, NewPolys1),
  polys_1(Polys, Orientations1, NewPolys1, NewPolys).

polys_2([], _, _, _, Orientations, Orientations, Polys, Polys).
polys_2([Cell|Cells], Cells0, Height, Width, Os0, Os, Polys0, Polys):-
  Deltas=[[0,1],[0,-1],[1,0],[-1,0]],
  polys_3(Deltas, Cell, Cells0, Height, Width, Os0, Os1, Polys0, Polys1),
  polys_2(Cells, Cells0, Height, Width, Os1, Os, Polys1, Polys).
  
/* polys_3([Delta|Deltas], Cell, Cells, Height, Width, Os0, Os, Polys). */
polys_3([], _, _, _, _, Os, Os, Polys, Polys).
polys_3([[K,L]|Deltas], Cell, Cells, Height, Width, Os0, Os, Polys0, Polys):-
  Cell=p(I,J),
  I1 is I + K,
  J1 is J + L,
  NewCell=p(I1,J1),
  \+ member(NewCell, Cells),
  insert(Cells, NewCell, NewCells),
  minimum(1, I1, MinRow),
  maximum(Height, I1, MaxRow),
  minimum(1, J1, MinCol),
  maximum(Width, J1, MaxCol),
  coords_matrix(MinRow, MaxRow, MinCol, MaxCol, NewCells, P),
  \+ member(P, Os0), !,
  rotate(P, O1),
  rotate(O1, O2),
  rotate(O2, O3),
  reverse(P, O4),
  reverse(O1, O5),
  reverse(O2, O6),
  reverse(O3, O7),
  Os1=[P,O1,O2,O3,O4,O5,O6,O7|Os0],
  polys_3(Deltas, Cell, Cells, Height, Width, Os1, Os, [P|Polys0], Polys).
polys_3([_|Deltas], Cell, Cells, Height, Width, Os0, Os, Polys0, Polys):-
  polys_3(Deltas, Cell, Cells, Height, Width, Os0, Os, Polys0, Polys).

/* e.g. matrix_coords([[0,1,1],[0,1,0],[1,1,1]],                             */
/*                    [p(1,2),p(1,3),p(2,2),p(3,1),p(3,2),p(3,3)]).          */
matrix_coords(Matrix, Cells):-
  matrix_coords_1(Matrix, 1, [], Cells0),
  reverse(Cells0, Cells).

matrix_coords_1([], _, Cells, Cells).
matrix_coords_1([Row|Rows], I, Cells0, Cells):-
  matrix_coords_2(Row, I, 1, Cells0, Cells1),
  I1 is I + 1,
  matrix_coords_1(Rows, I1, Cells1, Cells).

matrix_coords_2([], _, _, Cells, Cells).
matrix_coords_2([1|Row], I, J, Cells0, Cells):-!,
  J1 is J + 1,
  matrix_coords_2(Row, I, J1, [p(I,J)|Cells0], Cells).
matrix_coords_2([0|Row], I, J, Cells0, Cells):-!,
  J1 is J + 1,
  matrix_coords_2(Row, I, J1, Cells0, Cells).

/* e.g. coords_matrix(1,3, 1,3, [p(1,2),p(1,3),p(2,2),p(3,1),p(3,2),p(3,3)], */
/*                              [[0,1,1],[0,1,0],[1,1,1]]).                  */
coords_matrix(I, MaxRow, _, _, [], []):-
  I > MaxRow, !.
coords_matrix(I, MaxRow, MinCol, MaxCol, Cells, [Row|Rows]):-
  I1 is I + 1,
  coords_matrix_1(MinCol, MaxCol, I, Cells, Cells1, Row),
  coords_matrix(I1, MaxRow, MinCol, MaxCol, Cells1, Rows).

/* e.g. coords_matrix_1(1, 3, 1, [p(1,2),p(1,3)], [], [0,1,1]). */
coords_matrix_1(J, MaxCol, _, Cells, Cells, []):-
  J > MaxCol, !.
coords_matrix_1(J, MaxCol, I, [p(I,J)|Cells], Cells1, [1|Row]):-!,
  J1 is J + 1,
  coords_matrix_1(J1, MaxCol, I, Cells, Cells1, Row).
coords_matrix_1(J, MaxCol, I, Cells, Cells1, [0|Row]):-
  J1 is J + 1,
  coords_matrix_1(J1, MaxCol, I, Cells, Cells1, Row).

/* rotate(Matrix1, Matrix2) is true if Matrix2 is the Matrix1 rotated      */
/*   clockwise by 90 degrees.  Each Matrix is represented by a list of     */
/*   rows, each row being a list of numbers.                               */
/* e.g. rotate([[1,2,3],[4,5,6]], [[4,1],[5,2],[6,3]]).                    */
rotate([], []).
rotate([Xs|Xss], [Ys|Yss]):-
  reversed_heads_and_tails([Xs|Xss], [], Ys, Xss1),
  rotate(Xss1, Yss).

/* reversed_heads_and_tails(ListOfLists, [], Heads, Tails) is true if      */
/*   Heads is the reversed list of the heads of the members of the         */
/*   ListOfLists, and Tails is the list of the (non-empty) tails of the    */
/*   members of the ListOfLists.                                           */
/* e.g. reversed_heads_and_tails([[1,2,3],[4,5,6]],[],[4,1],[[2,3],[5,6]]).*/
/* e.g. reversed_heads_and_tails([[1,2,3],[4]],    [],[4,1],[[2,3]]).      */
reversed_heads_and_tails([], Ys, Ys, []).
reversed_heads_and_tails([[X]|Xss], Ys0, Ys, Zss):-!,
  reversed_heads_and_tails(Xss, [X|Ys0], Ys, Zss).
reversed_heads_and_tails([[X,X1|Xs]|Xss], Ys0, Ys, [[X1|Xs]|Zss]):-
  reversed_heads_and_tails(Xss, [X|Ys0], Ys, Zss).

/* insert(Ys, X, Zs) is true if Zs is the ordered list resulting from        */
/*   inserting X into the ordered list Ys.                                   */
insert([Y|Ys], X, [Y|Zs]):-less_than(Y, X), !, insert(Ys, X, Zs).
insert(Ys, X, [X|Ys]).

less_than(p(I,_), p(K,_)):-I < K, !.
less_than(p(I,J), p(I,L)):-J < L, !.

/* draw(Polyominoes) displays a list of Polyominoes in matrix form in a more */
/*   user-friendly format.                                                   */
draw([]).
draw([Pss|Psss]):-
  draw_1(Pss), nl,
  draw(Psss).
  
draw_1([]).
draw_1([Ps|Pss]):-
  draw_2(Ps), nl,
  draw_1(Pss).
  
draw_2([]).
draw_2([0|Ps]):-!,
  write(' '),
  draw_2(Ps).
draw_2([1|Ps]):-!,
  write('X'),
  draw_2(Ps).

/*
 * Library predicates
 */

/* length(Xs, L) is true if L is the number of elements in the list Xs.    */
%length(Xs, L):-length_1(Xs, 0, L).

/* length_1(Xs, L0, L) is true if L is equal to L0 plus the number of      */
/*   elements in the list Xs.                                              */
%length_1([], L, L).
%length_1([_|Xs], L0, L):-L1 is L0 + 1, length_1(Xs, L1, L).

/* member(X, Ys) is true if the element X is contained in the list Ys.     */
%member(X, [X|_]).
%member(X, [_|Ys]):-member(X, Ys).

/* maximum(X, Y, Z) is true if Z is the maximum of the numbers X and Y.    */
maximum(X, Y, Z):-X >= Y, !, Z=X.
maximum(_, Y, Y).

/* minimum(X, Y, Z) is true if Z is the minimum of the numbers X and Y.    */
minimum(X, Y, Z):-X =< Y, !, Z=X.
minimum(_, Y, Y).
  
/* reverse(Xs, Ys) is true if Ys is the result of reversing the order of   */
/*   the elements in the list Xs.                                          */
%reverse(Xs, Ys):-reverse_1(Xs, [], Ys).

%reverse_1([], As, As).
%reverse_1([X|Xs], As, Ys):-reverse_1(Xs, [X|As], Ys).

LPA Index     Home Page

Valid HTML 4.01 Strict