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]):-
heads_and_tails([Xs|Xss], Ys, Xss1),
transpose(Xss1, Yss).
/* heads_and_tails(ListOfLists, Heads, Tails) is true if Heads is the 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. 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]]). */
heads_and_tails([], [], []).
heads_and_tails([[X]|Xss], [X|Ys], Zss):-
heads_and_tails(Xss, Ys, Zss).
heads_and_tails([[X,X1|Xs]|Xss], [X|Ys], [[X1|Xs]|Zss]):-
heads_and_tails(Xss, Ys, Zss).
/* 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.
write_strings([Chars|Charss]):-
string_chars(String, Chars),
write(String), nl,
write_strings(Charss).
/* 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].
LPA Index
Home Page