#### Pentominoes

```/* pen(Height, Width, UnusableCells)                                       */
/* Place all (or a subset) of the 12 pentominoes so as to completely fill  */
/*   a Height-by-Width board without occupying the UnusableCells.          */
/*   Only one solution is generated.                                       */
/* Examples:
20 x 3...
pen(20,3,[]).
15 x 4...
pen(15,4,[]).
10 x 6...
pen(10,6,[]).
8 x 8 with a hole in the middle...
pen(8,8,[27,28,35,36]).
8 x 8 with holes inside...
pen(8,8,[19,29,34,44]).
4 staggered lines of 15...
pen(18,4,[0,1,2,4,5,8,63,66,67,69,70,71]).
5 staggered lines of 12...
pen(16,5,[0,1,2,3,5,6,7,10,11,15,64,68,69,72,73,74,76,77,78,79]).
1 x 5 and 11 x 5...
pen(13,5,[5,6,7,8,9]).
*/
pen(Height, Width, UnusableCells):-
length(UnusableCells, Length),
Area is Height * Width,
UsableArea is Area - Length,
UsableArea =< 60,
UsableArea mod 5 =:= 0,
N is UsableArea // 5,
Area_1 is Area - 1,
balanced_tree(0, Area_1, '*', Board0),
set_values(UnusableCells, 32 /* blank */, Board0, Board1),
pieces(Pieces),
search(N, Pieces, Height, Width, Board1, Board),
!,
/* Display the transposed Board... */
in_order(Board, List),
rows(List, Width, Rows),
transpose(Rows, Columns),
write_strings(Columns).

/* balanced_tree(M, N, Value, Tree) is true if Tree is a balanced ordered  */
/*   binary tree containing nodes with keys from M to N inclusive, with    */
/*   Value associated with each key.                                       */
balanced_tree(M, N, _, void):-
M > N, !.
balanced_tree(M, N, Value, tree(Key,Value,Left,Right)):-
Key is (M + N) // 2,
N1 is Key - 1, balanced_tree(M, N1, Value, Left),
M1 is Key + 1, balanced_tree(M1, N, Value, Right).

set_values([], _, Tree, Tree).
set_values([Key|Keys], Value, Tree0, Tree):-
set_value(Tree0, Key, Value, Tree1),
set_values(Keys, Value, Tree1, Tree).

/* set_value(Tree, Key, Value, NewTree) is true if the NewTree is the      */
/*   result of associating the Value with the Key in the Tree.             */
set_value(tree(Key,_,L,R), Key, Value, tree(Key,Value,L,R)):-!.
set_value(tree(Key1,Value1,L,R), Key, Value, tree(Key1,Value1,L1,R)):-
Key < Key1, !, set_value(L, Key, Value, L1).
set_value(tree(Key1,Value1,L,R), Key, Value, tree(Key1,Value1,L,R1)):-
Key > Key1, set_value(R, Key, Value, R1).

/* search(N, Pieces, Height, Width, Board0, Board) is true if Board is the */
/*   result of legally placing N of the Pieces on Board0, which has the    */
/*   given Height and Width.                                               */
search(0, _, _, _, Board, Board):-
/* No Pieces left - solution found */
!.
search(N, Pieces, Height, Width, Board0, Board):-
/* Solution not found - find first empty cell (Row, Col)... */
in_order(Board0, List),
nth(List, Index, '*'),
Row is Index // Width,
Col is Index mod Width,
/* Find the Orientation of a Piece to occupy (Row, Col)... */
piece(Pieces, s(Board0,Row,Col,Height,Width), Pieces1, ID, Orientation),
/* Update the Board... */
update_board([[0,0]|Orientation], Row, Col, Width, ID, Board0, Board1),
N1 is N - 1,
search(N1, Pieces1, Height, Width, Board1, Board).

/* in_order(Tree, List) is true if List is an in-order traversal of the    */
/*   binary tree Tree.                                                     */
in_order(Tree, List):-in_order_dl(Tree, List, []).

in_order_dl(void, Xs, Xs).
in_order_dl(tree(_,X,L,R), Xs, Zs):-
in_order_dl(R, Ys, Zs),
in_order_dl(L, Xs, [X|Ys]).

/* nth(+Xs, ?N, ?X) is true if X is the N-th (base 0) element of the       */
/*   list Xs.                                                              */
nth(Xs, N, X):-nth_1(Xs, X, 0, N).

nth_1([X|_], X, N, N):-!.
nth_1([_|Xs], X, N0, N):-
N1 is N0 + 1,
nth_1(Xs, X, N1, N).

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

/*   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. heads_and_tails([[1,2,3],[4,5,6]], [1,4], [[2,3],[5,6]]).        */
/*   e.g. heads_and_tails([[1,2,3],[4]],     [1,4], [[2,3]]).              */

/* piece(Pieces, s(Board,Row,Col,Height,Width), Pieces1, ID, Orientation)  */
/*   is true if Orientation is the orientation of a piece (identified by   */
/*   ID) contained in Pieces such that when placed on the Board (of the    */
/*   given Height and Width) at (Row, Col) it doesn't overflow the Board   */
/*   or overlap other pieces.  The remaining unused pieces are in Pieces1. */
piece([p(ID,P)|Ps], State, Ps, ID, Orientation):-
orientation(P, State, Orientation).
piece([P|Ps], State, [P|Ps1], ID, Orientation):-
piece(Ps, State, Ps1, ID, Orientation).

/* orientation(Piece, s(Board,Row,Col,Height,Width), Orientation) is true  */
/*   if Orientation is the orientation of the Piece such that when placed  */
/*   on the Board (of the given Height and Width) at (Row, Col) it doesn't */
/*   overflow the Board or overlap other pieces.                           */
orientation([Orientation|_], State, Orientation):-
all_squares_valid(Orientation, State).
orientation([_|Orientations], State, Orientation):-
orientation(Orientations, State, Orientation).

/* all_squares_valid(Orientation, s(Board,Row,Col,Height,Width)) is true   */
/*   if, when placed on the Board of the given Height and Width at         */
/*   (Row, Col), the Orientation doesn't overflow the Board or overlap     */
/*   other pieces.                                                         */
all_squares_valid([], _).
all_squares_valid([[Row0,Col0]|Squares], State):-
State = s(Board, Row, Col, Height, Width),
Col1 is Col0 + Col,
Col1 >= 0,
Col1 < Width,
Row1 is Row0 + Row,
/* Row1 cannot be negative */
Row1 < Height,
N is Row1 * Width + Col1,
lookup(Board, N, '*'),
all_squares_valid(Squares, State).

/* lookup(+Tree, +Key, ?Value) is true if the Value is associated with     */
/*   the Key in the Tree.                                                  */
lookup(tree(Key,Value,_,_), Key, Value):-!.
lookup(tree(Key1,_,Left,_), Key, Value):-
Key < Key1, !, lookup(Left, Key, Value).
lookup(tree(Key1,_,_,Right), Key, Value):-
Key > Key1, lookup(Right, Key, Value).

/* update_board(Orientation, Row, Col, Width, ID, Board0, Board) is true   */
/*   if Board is the result of placing Orientation on Board0 of the given  */
/*   Width at (Row, Col).  Orientation is represented by the character ID  */
/*   on the Board.                                                         */
update_board([], _, _, _, _, Board, Board).
update_board([[Row0,Col0]|Squares], Row, Col, Width, ID, Board0, Board):-
Index is (Row0 + Row) * Width + (Col0 + Col),
set_value(Board0, Index, ID, Board1),
update_board(Squares, Row, Col, Width, ID, Board1, Board).

/* rows([1,2,3,4,5,6,7], 3, [[1,2,3],[4,5,6],[7]]) */
rows([], _, []):-!.
rows(Xs, Width, [Ys|Yss]):-
rows_1(Width, Xs, Ys, Xs1),
rows(Xs1, Width, Yss).

/* rows_1(3, [1,2,3,4,5,6,7], [1,2,3], [4,5,6,7]) */
rows_1(Width, [X|Xs], [X|Ys], Zs):-
Width > 0, !,
Width1 is Width - 1,
rows_1(Width1, Xs, Ys, Zs).
rows_1(_, Xs, [], Xs).

write_strings([]):-nl.
string_chars(String, Chars),
write(String), nl,

/* There are 12 Pieces; there are up to 8 Orientations per Piece; each     */
/*   Orientation contains 5 Squares, [0,0] being implicit.                 */
pieces(Pieces):-
U = p( 85, [[[0, 1], [0, 2], [1, 0], [1, 2]],
[[0, 1], [1, 1], [2, 0], [2, 1]],
[[0, 2], [1, 0], [1, 1], [1, 2]],
[[0, 1], [1, 0], [2, 0], [2, 1]]]),
X = p( 88, [[[1,-1], [1, 0], [1, 1], [2, 0]]]),
I = p( 73, [[[1, 0], [2, 0], [3, 0], [4, 0]],
[[0, 1], [0, 2], [0, 3], [0, 4]]]),
P = p( 80, [[[1,-1], [1, 0], [2,-1], [2, 0]],
[[0, 1], [1, 0], [1, 1], [1, 2]],
[[0, 1], [1, 0], [1, 1], [2, 0]],
[[0, 1], [0, 2], [1, 1], [1, 2]],
[[1, 0], [1, 1], [2, 0], [2, 1]],
[[0, 1], [0, 2], [1, 0], [1, 1]],
[[0, 1], [1, 0], [1, 1], [2, 1]],
[[0, 1], [1,-1], [1, 0], [1, 1]]]),
L = p( 76, [[[0, 1], [1, 1], [2, 1], [3, 1]],
[[1,-3], [1,-2], [1,-1], [1, 0]],
[[1, 0], [2, 0], [3, 0], [3, 1]],
[[0, 1], [0, 2], [0, 3], [1, 0]],
[[0, 1], [1, 0], [2, 0], [3, 0]],
[[0, 1], [0, 2], [0, 3], [1, 3]],
[[1, 0], [2, 0], [3,-1], [3, 0]],
[[1, 0], [1, 1], [1, 2], [1, 3]]]),
N = p( 78, [[[1,-1], [1, 0], [2,-1], [3,-1]],
[[0, 1], [0, 2], [1, 2], [1, 3]],
[[1, 0], [2,-1], [2, 0], [3,-1]],
[[0, 1], [1, 1], [1, 2], [1, 3]],
[[1, 0], [1, 1], [2, 1], [3, 1]],
[[0, 1], [1,-2], [1,-1], [1, 0]],
[[1, 0], [2, 0], [2, 1], [3, 1]],
[[0, 1], [0, 2], [1,-1], [1, 0]]]),
F = p( 70, [[[1, 0], [1, 1], [2,-1], [2, 0]],
[[1, 0], [1, 1], [1, 2], [2, 1]],
[[0, 1], [1,-1], [1, 0], [2, 0]],
[[1,-1], [1, 0], [1, 1], [2, 1]],
[[1,-1], [1, 0], [2, 0], [2, 1]],
[[1,-1], [1, 0], [1, 1], [2,-1]],
[[0, 1], [1, 1], [1, 2], [2, 1]],
[[1,-2], [1,-1], [1, 0], [2,-1]]]),
T = p( 84, [[[1,-2], [1,-1], [1, 0], [2, 0]],
[[1, 0], [2,-1], [2, 0], [2, 1]],
[[1, 0], [1, 1], [1, 2], [2, 0]],
[[0, 1], [0, 2], [1, 1], [2, 1]]]),
W = p( 87, [[[0, 1], [1, 1], [1, 2], [2, 2]],
[[1,-1], [1, 0], [2,-2], [2,-1]],
[[1, 0], [1, 1], [2, 1], [2, 2]],
[[0, 1], [1,-1], [1, 0], [2,-1]]]),
Y = p( 89, [[[1, 0], [2, 0], [3, 0], [1, 1]],
[[0, 1], [0, 2], [0, 3], [1, 2]],
[[1, 0], [2,-1], [2, 0], [3, 0]],
[[1,-1], [1, 0], [1, 1], [1, 2]],
[[1,-1], [1, 0], [2, 0], [3, 0]],
[[1,-2], [1,-1], [1, 0], [1, 1]],
[[1, 0], [2, 0], [2, 1], [3, 0]],
[[0, 1], [0, 2], [0, 3], [1, 1]]]),
Z = p( 90, [[[0, 1], [1, 0], [2,-1], [2, 0]],
[[1, 0], [1, 1], [1, 2], [2, 2]],
[[0, 1], [1, 1], [2, 1], [2, 2]],
[[1,-2], [1,-1], [1, 0], [2,-2]]]),
V = p( 86, [[[1, 0], [2,-2], [2,-1], [2, 0]],
[[1, 0], [2, 0], [2, 1], [2, 2]],
[[0, 1], [0, 2], [1, 0], [2, 0]],
[[0, 1], [0, 2], [1, 2], [2, 2]]]),
Pieces = [U, X, I, P, L, N, F, T, W, Y, Z, V].
```