/* 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).