A pentomino is a polyomino that consists of 5 squares. There are 12 pentomino shapes,
if you don't count rotations and reflections. Most pentominoes can form their own mirror image through
rotation, but some of them have to be flipped over.

        I                                                                        
        I     L       N                                                 Y        
 FF     I     L      NN     PP     TTT              V       W     X    YY      ZZ
FF      I     L      N      PP      T     U U       V      WW    XXX    Y      Z 
 F      I     LL     N      P       T     UUU     VVV     WW      X     Y     ZZ


A Pentomino tiling is an example of an exact cover problem and can take on many forms.
A traditional tiling presents an 8 by 8 grid, where 4 cells are left uncovered. The other cells are covered
by the 12 pentomino shapes, without overlaps, with every shape only used once.

The 4 uncovered cells should be chosen at random. Note that not all configurations are solvable.



Task
Create an 8 by 8 tiling and print the result.



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


Related tasks
 Free polyominoes enumeration


with javascript_semantics
constant pentominoes = split("""
......I................................................................
......I.....L......N.........................................Y.........
.FF...I.....L.....NN....PP....TTT...........V.....W....X....YY.....ZZ..
FF....I.....L.....N.....PP.....T....U.U.....V....WW...XXX....Y.....Z...
.F....I.....LL....N.....P......T....UUU...VVV...WW.....X.....Y....ZZ...""",'\n')
----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- 
 
function get_shapes()
    sequence res = {}
    for offset=0 to length(pentominoes[1]) by 6 do
        --
        -- scan left/right, and up/down, both ways, to give 8 orientations
        --      (computes the equivalent of those hard-coded tables in
        --       other examples, albeit in a slightly different order.)
        --
        sequence shapes = {}
        integer letter
        for orientation=0 to 7 do
            sequence shape = {}
            bool found = false
            integer fr, fc
            for r=1 to 5 do
                for c=1 to 5 do
                    integer rr = iff(and_bits(orientation,#01)?6-r:r),
                            cc = iff(and_bits(orientation,#02)?6-c:c)
                    if and_bits(orientation,#04) then {rr,cc} = {cc,rr} end if
                    integer ch = pentominoes[rr,offset+cc]
                    if ch!='.' then
                        if not found then
                            {found,fr,fc,letter} = {true,r,c,ch}
                        else
                            shape &= {r-fr,c-fc}
                        end if
                    end if
                end for
            end for
            if not find(shape,shapes) then
                shapes = append(shapes,shape)
            end if
        end for
        res = append(res,{letter&"",shapes})
    end for
    return res
end function
 
constant shapes = get_shapes(),
         nRows = 8,
         nCols = 8
 
sequence grid = repeat(repeat(' ',nCols),nRows),
         placed = repeat(false,length(shapes))
 
procedure re_place(sequence o, integer r, c, ch=' ')
    grid[r][c] = ch
    for i=1 to length(o) by 2 do
        grid[r+o[i]][c+o[i+1]] = ch
    end for
end procedure

function can_place(sequence o, integer r, c, ch)
    for i=1 to length(o) by 2 do
        integer x := c + o[i+1],
                y := r + o[i]
        if x<1 or x>nCols
        or y<1 or y>nRows
        or grid[y][x]!=' ' then
            return false
        end if
    end for
    re_place(o,r,c,ch)
    return true
end function
 
function solve(integer pos=0, numPlaced=0)
    if numPlaced == length(shapes) then
        return true
    end if
    integer row = floor(pos/8)+1,
            col = mod(pos,8)+1
    if grid[row][col]!=' ' then
        return solve(pos+1, numPlaced)
    end if
    for i=1 to length(shapes) do
        if not placed[i] then
            integer ch = shapes[i][1][1]
            for j=1 to length(shapes[i][2]) do
                sequence o = shapes[i][2][j]
                if can_place(o, row, col, ch) then
                    placed[i] = true
                    if solve(pos+1, numPlaced+1) then
                        return true
                    end if
                    re_place(o, row, col)
                    placed[i] = false
                end if
            end for
        end if
    end for
    return false
end function
 
function unsolveable()
--
-- The only unsolvable grids seen have 
--  -.- or -..- or -... at edge/corner,
--   -      --      ---           -
--  or somewhere in the middle a -.- 
--                                -
--
-- Simply place all shapes at all positions/orientations,
--  all the while checking for any untouchable cells.
--
    sequence griddled = deep_copy(grid)
    for r=1 to 8 do
        for c=1 to 8 do
            if grid[r][c]=' ' then
                for i=1 to length(shapes) do
                    integer ch = shapes[i][1][1]
                    for j=1 to length(shapes[i][2]) do
                        sequence o = shapes[i][2][j]
                        if can_place(o, r, c, ch) then
                            grid[r][c] = ' '
                            griddled[r][c] = '-'
                            for k=1 to length(o) by 2 do
                                grid[r+o[k]][c+o[k+1]] = ' '
                                griddled[r+o[k]][c+o[k+1]] = '-'
                            end for
                        end if
                    end for
                end for
                if griddled[r][c]!='-' then return true end if
            end if
        end for
    end for
    return false
end function
 
procedure add_four_randomly()
    integer count = 0
    while count<4 do
        integer r = rand(8),
                c = rand(8)
        if grid[r][c]=' ' then
            grid[r][c] = '-'
            count += 1
        end if
    end while
end procedure
 
procedure main()
    add_four_randomly()
    if unsolveable() then
        puts(1,"No solution\n")
    else
        if not solve() then ?9/0 end if
    end if
    puts(1,join(grid,"\n")&"\n")
end procedure
main()
