{
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

This page was created by F1toHTML