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


// Version 1.1.4-3
 
import java.util.Random
 
val F = arrayOf(
    intArrayOf(1, -1, 1, 0, 1, 1, 2, 1), intArrayOf(0, 1, 1, -1, 1, 0, 2, 0),
    intArrayOf(1, 0, 1, 1, 1, 2, 2, 1), intArrayOf(1, 0, 1, 1, 2, -1, 2, 0),
    intArrayOf(1, -2, 1, -1, 1, 0, 2, -1), intArrayOf(0, 1, 1, 1, 1, 2, 2, 1), 
    intArrayOf(1, -1, 1, 0, 1, 1, 2, -1), intArrayOf(1, -1, 1, 0, 2, 0, 2, 1)
)
 
val I = arrayOf(
    intArrayOf(0, 1, 0, 2, 0, 3, 0, 4), intArrayOf(1, 0, 2, 0, 3, 0, 4, 0)
)
 
val L = arrayOf(
    intArrayOf(1, 0, 1, 1, 1, 2, 1, 3), intArrayOf(1, 0, 2, 0, 3, -1, 3, 0),
    intArrayOf(0, 1, 0, 2, 0, 3, 1, 3), intArrayOf(0, 1, 1, 0, 2, 0, 3, 0),
    intArrayOf(0, 1, 1, 1, 2, 1, 3, 1), intArrayOf(0, 1, 0, 2, 0, 3, 1, 0),
    intArrayOf(1, 0, 2, 0, 3, 0, 3, 1), intArrayOf(1, -3, 1, -2, 1, -1, 1, 0)
)
 
val N = arrayOf(
    intArrayOf(0, 1, 1, -2, 1, -1, 1, 0), intArrayOf(1, 0, 1, 1, 2, 1, 3, 1),
    intArrayOf(0, 1, 0, 2, 1, -1, 1, 0), intArrayOf(1, 0, 2, 0, 2, 1, 3, 1),
    intArrayOf(0, 1, 1, 1, 1, 2, 1, 3), intArrayOf(1, 0, 2, -1, 2, 0, 3, -1), 
    intArrayOf(0, 1, 0, 2, 1, 2, 1, 3), intArrayOf(1, -1, 1, 0, 2, -1, 3, -1)
)
 
val P = arrayOf(
    intArrayOf(0, 1, 1, 0, 1, 1, 2, 1), intArrayOf(0, 1, 0, 2, 1, 0, 1, 1),
    intArrayOf(1, 0, 1, 1, 2, 0, 2, 1), intArrayOf(0, 1, 1, -1, 1, 0, 1, 1),
    intArrayOf(0, 1, 1, 0, 1, 1, 1, 2), intArrayOf(1, -1, 1, 0, 2, -1, 2, 0),
    intArrayOf(0, 1, 0, 2, 1, 1, 1, 2), intArrayOf(0, 1, 1, 0, 1, 1, 2, 0)
)
 
val T = arrayOf(
    intArrayOf(0, 1, 0, 2, 1, 1, 2, 1), intArrayOf(1, -2, 1, -1, 1, 0, 2, 0),
    intArrayOf(1, 0, 2, -1, 2, 0, 2, 1), intArrayOf(1, 0, 1, 1, 1, 2, 2, 0)
)
 
val U = arrayOf(
    intArrayOf(0, 1, 0, 2, 1, 0, 1, 2), intArrayOf(0, 1, 1, 1, 2, 0, 2, 1),
    intArrayOf(0, 2, 1, 0, 1, 1, 1, 2), intArrayOf(0, 1, 1, 0, 2, 0, 2, 1)
)
 
val V = arrayOf(
    intArrayOf(1, 0, 2, 0, 2, 1, 2, 2), intArrayOf(0, 1, 0, 2, 1, 0, 2, 0),
    intArrayOf(1, 0, 2, -2, 2, -1, 2, 0), intArrayOf(0, 1, 0, 2, 1, 2, 2, 2)
)
 
val W = arrayOf(
    intArrayOf(1, 0, 1, 1, 2, 1, 2, 2), intArrayOf(1, -1, 1, 0, 2, -2, 2, -1),
    intArrayOf(0, 1, 1, 1, 1, 2, 2, 2), intArrayOf(0, 1, 1, -1, 1, 0, 2, -1)
)
 
val X = arrayOf(intArrayOf(1, -1, 1, 0, 1, 1, 2, 0))
 
val Y = arrayOf(
    intArrayOf(1, -2, 1, -1, 1, 0, 1, 1), intArrayOf(1, -1, 1, 0, 2, 0, 3, 0),
    intArrayOf(0, 1, 0, 2, 0, 3, 1, 1), intArrayOf(1, 0, 2, 0, 2, 1, 3, 0),
    intArrayOf(0, 1, 0, 2, 0, 3, 1, 2), intArrayOf(1, 0, 1, 1, 2, 0, 3, 0),
    intArrayOf(1, -1, 1, 0, 1, 1, 1, 2), intArrayOf(1, 0, 2, -1, 2, 0, 3, 0)
)
 
val Z = arrayOf(
    intArrayOf(0, 1, 1, 0, 2, -1, 2, 0), intArrayOf(1, 0, 1, 1, 1, 2, 2, 2),
    intArrayOf(0, 1, 1, 1, 2, 1, 2, 2), intArrayOf(1, -2, 1, -1, 1, 0, 2, -2)
)
 
val shapes = arrayOf(F, I, L, N, P, T, U, V, W, X, Y, Z)
val rand = Random()
 
val symbols = "FILNPTUVWXYZ-".toCharArray()
 
val nRows = 8
val nCols = 8
val blank = 12
 
val grid = Array(nRows) { IntArray(nCols) }
val placed = BooleanArray(symbols.size - 1)
 
fun tryPlaceOrientation(o: IntArray, r: Int, c: Int, shapeIndex: Int): Boolean {
    for (i in 0 until o.size step 2) {
        val x = c + o[i + 1]
        val y = r + o[i]
        if (x !in (0 until nCols) || y !in (0 until nRows) || grid[y][x] != - 1) return false
    }
    grid[r][c] = shapeIndex
    for (i in 0 until o.size step 2) grid[r + o[i]][c + o[i + 1]] = shapeIndex
    return true
}
 
fun removeOrientation(o: IntArray, r: Int, c: Int) {
    grid[r][c] = -1
    for (i in 0 until o.size step 2) grid[r + o[i]][c + o[i + 1]] = -1
}
 
fun solve(pos: Int, numPlaced: Int): Boolean {
    if (numPlaced == shapes.size) return true
    val row = pos / nCols
    val col = pos % nCols
    if (grid[row][col] != -1) return solve(pos + 1, numPlaced)
 
    for (i in 0 until shapes.size) {
        if (!placed[i]) {
            for (orientation in shapes[i]) {
                if (!tryPlaceOrientation(orientation, row, col, i)) continue
                placed[i] = true
                if (solve(pos + 1, numPlaced + 1)) return true
                removeOrientation(orientation, row, col)
                placed[i] = false
            }
        }
    }
    return false
}
 
fun shuffleShapes() {
    var n = shapes.size
    while (n > 1) {
        val r = rand.nextInt(n--)
        val tmp = shapes[r]
        shapes[r] = shapes[n]
        shapes[n] = tmp
        val tmpSymbol= symbols[r]
        symbols[r] = symbols[n]
        symbols[n] = tmpSymbol
    }
}
 
fun printResult() {
    for (r in grid) {
        for (i in r) print("${symbols[i]} ")
        println()
    }
}
 
fun main(args: Array<String>) {
    shuffleShapes()
    for (r in 0 until nRows) grid[r].fill(-1)
    for (i in 0..3) {
        var randRow: Int
        var randCol: Int
        do {
            randRow = rand.nextInt(nRows)
            randCol = rand.nextInt(nCols)
        }
        while (grid[randRow][randCol] == blank)
        grid[randRow][randCol] = blank
    }
    if (solve(0, 0)) printResult()
    else println("No solution")
}