#### 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]):-
rotate(Xss1, Yss).

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

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