```{
A pentomino is an arrangement of five unit squares that are joined along their
edges. There are 12 possible shapes, which are depicted below. Traditionally,
each piece is labelled by the letter that most accurately reflects its shape.

+-+      +-+-+-+     +-+     +-+                +-+-+      +-+-+  +-+-+
| |      | | | |     | |     | |                | | |      | | |  | | |
+-+      +-+-+-+   +-+-+-+   +-+-+     +-+ +-+  +-+-+    +-+-+-+  +-+-+
| |        | |     | | | |   | | |     | | | |    | |    | | |    | | |
+-+-+-+    +-+     +-+-+-+   +-+-+-+   +-+-+-+    +-+-+  +-+-+    +-+-+
| | | |    | |       | |       | | |   | | | |    | | |    | |    | |
+-+-+-+    +-+       +-+       +-+-+   +-+-+-+    +-+-+    +-+    +-+
V         T         X         W         U        Z        F      P

+-+       +-+      +-+   +-+
| |       | |      | |   | |
+-+     +-+-+    +-+-+   +-+
| |     | | |    | | |   | |
+-+     +-+-+    +-+-+   +-+
| |     | |        | |   | |
+-+     +-+        +-+   +-+-+
| |     | |        | |   | | |
+-+     +-+        +-+   +-+-+
| |
+-+
I       N          Y      L

Typical problem is to fit the 12 pentomino pieces into various shapes, mostly rectangles.
Each piece can be rotated and flipped.
Possible rectangle shapes that fit all 60 squares can be 3x20, 4x15, 5x12, and 6x10.
An example of a 6 x 10 solution is this:

V V V T I I I I I W
L L V T T T N N W W
L F V T N N N W W Z
L F F F X U U Z Z Z
L Y F X X X U Z P P
Y Y Y Y X U U P P P

Not counting rotations and reflections, the number of solutions for each pentomino
problem can be summarized as follows:

6x10: 2339
5x12: 1010
4x15:  368
3x10:    2

Other shapes are possible. The code below solves all rectangular problems, but it
is trivial to modify it to solve pentomino layout for different shapes.

There are two possible approaches to tackle the pentomino problem: calculate until
all pieces are used or calculate until the whole board is covered. Covering the
whole board is much faster, as any impossible solution is detected much sooner.
Additionally, covering a rectangle is much faster when we start covering along
the smaller of the rectangle dimensions. Again, this is because using the shorter
side first we detect impossible solutions much faster.

The solution are calculated by running the following queries:

all Pentomino(10,6)     // all pentomino solutions for rectangle 10x6
all Pentomino(12,5)     // all pentomino solutions for rectangle 12x5
all Pentomino(15,4)     // all pentomino solutions for rectangle 15x4
all Pentomino(20,3)     // all pentomino solutions for rectangle 20x3

Using the queries above, the calculation will take anything from one second to several
minutes, based on the rectangle and the speed of the CPU.

Final note:

As mentioned before, calculating along the longer rectangle side first, i.e.
the query

all Pentomino(6,10)

will take much longer then the query

all Pentomino(10,6)

In this case, the calculation can take several hours.
Of course, the results will be the same (albeit not in the same order).

}

Block = [0..]->[0..]->I

// In this program, we implement the pentomino pieces as rectangles, with some elements
// "transparent", i.e. initialized as " " (space), the non-transparent elements are
// initialzied based on the pentomino piece label.

BlockV :< Block = [["V"," "," "],
["V"," "," "],
["V","V","V"]]

BlockT :< Block = [["T","T","T"],
[" ","T"," "],
[" ","T"," "]]

BlockX :< Block = [[" ","X"," "],
["X","X","X"],
[" ","X"," "]]

BlockW :< Block = [["W"," "," "],
["W","W"," "],
[" ","W","W"]]

BlockU :< Block = [["U"," ","U"],
["U","U","U"]]

BlockZ :< Block = [["Z","Z"," "],
[" ","Z"," "],
[" ","Z","Z"]]

BlockF :< Block = [[" ","F","F"],
["F","F"," "],
[" ","F"," "]]

BlockP :< Block = [["P","P"],
["P","P"],
["P"," "]]

BlockI :< Block = [["I"],
["I"],
["I"],
["I"],
["I"]]

BlockN :< Block = [[" ","N"],
["N","N"],
["N"," "],
["N"," "]]

BlockY :< Block = [[" ","Y"],
["Y","Y"],
[" ","Y"],
[" ","Y"]]

BlockL :< Block = [["L"," "],
["L"," "],
["L"," "],
["L","L"]]

local BlockEx = piece:Block,origin:I
local Board = [0..]->[0..]->I
local AllPieces = [0..]->>[0..]->BlockEx
local Used = [0..]->I

pred Pentomino(rows:<[1..], columns:<I[1..]) iff
Print('\n Solving Rectangular Pentomino Problem ',rows, ' x ',columns,'\n\n') &

// Initialize the "board", i.e. the rectangle which we want to fill with
// the pentomino pieces. We intialize all position as " " (no pieces placed yet)

board:.Board & Dupl(rows,Dupl(columns," "),board) &

// Each pentomino piece can have several orientations, we let the program
// to calculate them.

CreatePossibleShapes(BlockV,aBlockV) &
CreatePossibleShapes(BlockT,aBlockT) &
CreatePossibleShapes(BlockX,aBlockX) &
CreatePossibleShapes(BlockW,aBlockW) &
CreatePossibleShapes(BlockU,aBlockU) &
CreatePossibleShapes(BlockI,aBlockI) &
CreatePossibleShapes(BlockL,aBlockL) &
CreatePossibleShapes(BlockZ,aBlockZ) &
CreatePossibleShapes(BlockF,aBlockF) &
CreatePossibleShapes(BlockP,aBlockP) &
CreatePossibleShapes(BlockN,aBlockN) &
CreatePossibleShapes(BlockY,aBlockY) &

// Create an array of all arrays of all possible pentomino pieces orientations.
// Note that it does not matter that the array elements may have different
// lengths.

pieces :> AllPieces & pieces =
[aBlockV,aBlockT,aBlockX,aBlockW,aBlockU,aBlockI,aBlockL,aBlockZ,aBlockF,aBlockP,aBlockN,aBlockY] &

// We keep track of used pentomino pieces in "used".
// We initialize the map of used pentomino pieces to 0 (no piece used used)

used :.Used & Dupl(Len(pieces),0,used) &

// Having initialized the board, all possible pieces orientations and used pieces map
// we can start the actual computation

CoverAllBlocks(board,pieces,used) &

// A solution was found, so print it

PrintFormattedSolution(board,0)

// Cover the board as long as we can find any place on the board
// that is not covered yet by a pentomino.
local pred CoverAllBlocks(board:.Board,pieces:<AllPieces,used:.Used) iff
if FindFreeRowCol(board,row,col,0) then
PlaceOnePiece(board,pieces,used,row,col,0) & CoverAllBlocks(board,pieces,used)
end

// Board position at row,col is unused. Place there a piece.
local pred PlaceOnePiece(board:.Board,pieces:<AllPieces,used:.Used,row:<I,col:<I,i:<I) iff
p::I[0..] & p < Len(pieces) & used(p) = 0 & // get an unused piece index
piece = pieces(p) &                         // get an unused piece
rot::I[0..] & rot < Len(piece) &            // piece can have this many transformations
CheckPosition(board,piece(rot),row,col,0) & // validate we can place this piece
PlacePosition(board,piece(rot),row,col,0) & // place the piece on the board
used(p) := 1                                // mark the piece as used

local pred PlacePosition(board:.Board,piece:<BlockEx,row:<I,col:<I,prow:<I)  iff
if prow < Len(piece.piece) then
PlaceOneRow(board,piece.piece,row,col-piece.origin,prow, 0) &
PlacePosition(board,piece,row,col,prow+1)
end

local pred PlaceOneRow(board:.Board,piece :< Block, row:<I, col:<I, prow:<I, pcol:<I)  iff
if pcol < Len(piece(0)) then
if piece(prow,pcol) <> " " then
board(row+prow,col+pcol) := piece(prow,pcol)
end & PlaceOneRow(board,piece,row,col, prow,pcol+1)
end

local pred CheckPosition(board:.Board,piece :< BlockEx, row:<I, col:<I, prow:<I)  iff
if prow < Len(piece.piece) then
CheckOneRow(board,piece.piece,row,col-piece.origin,prow, 0) &
CheckPosition(board,piece,row,col, prow+1)
end

local pred CheckOneRow(board:.Board,piece :< Block, row:<I, col:<I, prow:<I, pcol:<I)  iff
if pcol < Len(piece(0)) then
if piece(prow,pcol) <> " " then
board(row+prow,col+pcol) = " "
end & CheckOneRow(board,piece,row,col, prow,pcol+1)
end

// Find the first occurence of a free board square.
local proc FindFreeRowCol(board:<Board,row:>I, col:>I, i:<I) iff
i < Len(board) &
if FindFreeCol(board(i),col1,0) then
row = i & col = col1
else
FindFreeRowCol(board,row,col,i+1) & true
end

local proc FindFreeCol(board:<[0..]->I,col:>I,i:<I) iff
i < Len(board) &
if board(i) = " " then
col = i
else
FindFreeCol(board,col,i+1)
end

// Print the solution in a more presentable way

local proc PrintFormattedSolution(board:<Board,row:<I) iff
if row < Len(board) then
Print('\n') & PrintOneRow(board(row),0) & PrintFormattedSolution(board,row+1)
else
Print('\n')
end

local proc PrintOneRow(r:<[0..]->I,col:<I) iff
if col < Len(r) then
if r(col) < 10 then
Print(' ')
end &
Print(r(col):S,' ') & PrintOneRow(r,col+1)
end

// In principle, we can place any pentomino piece in 4x2 different ways:
// each piece can be rotate 0,90,180 or 360 degrees and for each rotation
// we can flip the piece upside down (mirror image). Of course, this would
// lead to many identical solutions, as various pentomino pieces exhibit various
// degrees of symmetry. Instead of rotating and flipping the pentomino pieces
// at run-time, we precalculate all possible orientation of a pentomino
// piece, at the same time avoiding identical shapes due to rotational/mirror
// symmetry.

// All the code bellow deals with calculating all possible shapes of a pentomino
// piece: rotations by 0, 90, 180, 270 degrees and all flipped (mirror) images
// corresponding to all rotations.
// Additionally, since our representation of a (irregular) pentomino piece is
// a rectangle with some fields defined as "transparent" (initialized as " "),
// for each piece orientation we also calculate the piece "origin", i.e. the first
// "non-transparent" column.

// NOTE: in order not to generate solutions that are simple rotations or
// mirror reflection of another solution, we simply fix the "L" pentomino
// to include only two shapes: regular "L" and "L" rotated by 90 degrees.
// (Instead of "L this could be any piece that can have 4x2 different orientations)

local proc CreatePossibleShapes(piece:<Block,aBlock:>[0..]->BlockEx) iff
newpieces :. list BlockEx & newpieces := (piece,CalcOffset(piece)),Nil &

// Special cas the "L" piece (see the note above)

if piece = BlockL then
Rotate(piece,0,newpiece0) &
newpieces := newpiece0,newpieces
else
Flip(piece,fnewpiece) &
if ~fnewpiece in newpieces then
newpieces := fnewpiece,newpieces
end &

Rotate(piece,0,newpiece0) &
if ~newpiece0 in newpieces then
newpieces := newpiece0,newpieces
end &
Flip(newpiece0.piece,fnewpiece0) &
if ~fnewpiece0 in newpieces then
newpieces := fnewpiece0,newpieces
end &

Rotate(piece,1,newpiece1) &
if ~newpiece1 in newpieces then
newpieces := newpiece1,newpieces
end &
Flip(newpiece1.piece,fnewpiece1) &
if ~fnewpiece1 in newpieces then
newpieces := fnewpiece1,newpieces
end &

Rotate(piece,2,newpiece2) &
if ~newpiece2 in newpieces then
newpieces := newpiece2,newpieces
end &
Flip(newpiece2.piece,fnewpiece2) &
if ~fnewpiece2 in newpieces then
newpieces := fnewpiece2,newpieces
end
end & aBlock = newpieces:[0..]->BlockEx

// in each row reverse columns
local proc Flip(piece:<Block,fpiece:>BlockEx) iff
fpiece0 :.[0..]->[0..]->I & Dupl(Len(piece),Dupl(Len(piece(0)),0),fpiece0) &
ReverseColumns(piece,fpiece0,0) &
fpiece = fpiece0,CalcOffset(fpiece0)

local proc Rotate(piece:<Block,i:<I,newpiece:>BlockEx) iff
if i = 0 then //rotate by 90 degrees, swap rows & columns
rpiece0 :.[0..]->[0..]->I & Dupl(Len(piece(0)),Dupl(Len(piece),0),rpiece0) &
rpiece00 :.[0..]->[0..]->I & Dupl(Len(piece(0)),Dupl(Len(piece),0),rpiece00) &
Transpose(piece,rpiece0) &
ReverseColumns(rpiece0,rpiece00,0) &
newpiece = rpiece00,CalcOffset(rpiece00)
elsif i = 1 then //180
rpiece1 :.[0..]->[0..]->I & Dupl(Len(piece),Dupl(Len(piece(0)),0),rpiece1) &
RtlReverse(piece,rpiece) & ReverseColumns(rpiece,rpiece1,0) & newpiece = rpiece1,CalcOffset(rpiece1)
else //i = 2, rotate by 270
rpiece2 :.[0..]->[0..]->I & Dupl(Len(piece(0)),Dupl(Len(piece),0),rpiece2) &
Transpose(piece,rpiece2) &
RtlReverse(rpiece2,newpiece2) & newpiece = newpiece2,CalcOffset(newpiece2)
end

local proc ReverseColumns(piece:<Block,rpiece:.Block, col:<I) iff
if col < Len(piece) then
RtlReverse(piece(col),rpiece(col)) &
ReverseColumns(piece,rpiece,col+1)
end

local proc Transpose(a :<Block, b:.Block) iff
TransposeRows(a,b,0,Len(b))

local proc TransposeRows(a:<Block, b:.Block,r:<I, maxr:<I) iff
if r < maxr then
Len(b(r),Len(a)) & TransposeColumns(a,b,r,0,Len(a)) &
TransposeRows(a,b,r+1, maxr)
end

local proc TransposeColumns(a:<Block,b:.Block,r:<I,c:<I,maxc:<I) iff
if c < maxc then
b(r,c) := a(c,r) & TransposeColumns(a,b,r,c+1,maxc)
end

// Fo our program purposes, each pentomino piece is placed within a bounding rectangle.
// The "unused" portion of the rectangle is initialized as " " (space).
// Here we simply find the first "non-transparent" element of the pentomino piece.
local proc CalcOffset(piece:<Block,offset:>I) iff
x:.I & x := 0 & CalcOffsetX(piece(0),x,0) & offset = x

local proc CalcOffsetX(a:<[0..]->I,x:.I,i:<I) iff
if i < Len(a) then
if a(i) = " " then
x := x+1 & CalcOffsetX(a,x,i+1)
end
end

```