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