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


using System;
using System.Linq;
 
namespace PentominoTiling
{
    class Program
    {
        static readonly char[] symbols = "FILNPTUVWXYZ-".ToCharArray();
 
        static readonly int nRows = 8;
        static readonly int nCols = 8;
        static readonly int target = 12;
        static readonly int blank = 12;
 
        static int[][] grid = new int[nRows][];
        static bool[] placed = new bool[target];
 
        static void Main(string[] args)
        {
            var rand = new Random();
 
            for (int r = 0; r < nRows; r++)
                grid[r] = Enumerable.Repeat(-1, nCols).ToArray();
 
            for (int i = 0; i < 4; i++)
            {
                int randRow, randCol;
                do
                {
                    randRow = rand.Next(nRows);
                    randCol = rand.Next(nCols);
                } 
                while (grid[randRow][randCol] == blank);
 
                grid[randRow][randCol] = blank;
            }
 
            if (Solve(0, 0))
            {
                PrintResult();
            }
            else
            {
                Console.WriteLine("no solution");
            }
 
            Console.ReadKey();
        }
 
        private static void PrintResult()
        {
            foreach (int[] r in grid)
            {
                foreach (int i in r)
                    Console.Write("{0} ", symbols[i]);
                Console.WriteLine();
            }
        }
 
        private static bool Solve(int pos, int numPlaced)
        {
            if (numPlaced == target)
                return true;
 
            int row = pos / nCols;
            int col = pos % nCols;
 
            if (grid[row][col] != -1)
                return Solve(pos + 1, numPlaced);
 
            for (int i = 0; i < shapes.Length; i++)
            {
                if (!placed[i])
                {
                    foreach (int[] 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;
        }
 
        private static void RemoveOrientation(int[] orientation, int row, int col)
        {
            grid[row][col] = -1;
            for (int i = 0; i < orientation.Length; i += 2)
                grid[row + orientation[i]][col + orientation[i + 1]] = -1;
        }
 
        private static bool TryPlaceOrientation(int[] orientation, int row, int col, int shapeIndex)
        {
            for (int i = 0; i < orientation.Length; i += 2)
            {
                int x = col + orientation[i + 1];
                int y = row + orientation[i];
                if (x < 0 || x >= nCols || y < 0 || y >= nRows || grid[y][x] != -1)
                    return false;
            }
 
            grid[row][col] = shapeIndex;
            for (int i = 0; i < orientation.Length; i += 2)
                grid[row + orientation[i]][col + orientation[i + 1]] = shapeIndex;
 
            return true;
        }
 
        // four (x, y) pairs are listed, (0,0) not included
        static readonly int[][] F = {
            new int[] {1, -1, 1, 0, 1, 1, 2, 1}, new int[] {0, 1, 1, -1, 1, 0, 2, 0},
            new int[] {1, 0, 1, 1, 1, 2, 2, 1}, new int[] {1, 0, 1, 1, 2, -1, 2, 0},
            new int[] {1, -2, 1, -1, 1, 0, 2, -1}, new int[] {0, 1, 1, 1, 1, 2, 2, 1},
            new int[] {1, -1, 1, 0, 1, 1, 2, -1}, new int[] {1, -1, 1, 0, 2, 0, 2, 1}};
 
        static readonly int[][] I = {
            new int[] { 0, 1, 0, 2, 0, 3, 0, 4 }, new int[] { 1, 0, 2, 0, 3, 0, 4, 0 } };
 
        static readonly int[][] L = {
            new int[] {1, 0, 1, 1, 1, 2, 1, 3}, new int[] {1, 0, 2, 0, 3, -1, 3, 0},
            new int[] {0, 1, 0, 2, 0, 3, 1, 3}, new int[] {0, 1, 1, 0, 2, 0, 3, 0},
            new int[] {0, 1, 1, 1, 2, 1, 3, 1}, new int[] {0, 1, 0, 2, 0, 3, 1, 0},
            new int[] {1, 0, 2, 0, 3, 0, 3, 1}, new int[] {1, -3, 1, -2, 1, -1, 1, 0}};
 
        static readonly int[][] N = {
            new int[] {0, 1, 1, -2, 1, -1, 1, 0}, new int[] {1, 0, 1, 1, 2, 1, 3, 1},
            new int[]  {0, 1, 0, 2, 1, -1, 1, 0}, new int[] {1, 0, 2, 0, 2, 1, 3, 1},
            new int[] {0, 1, 1, 1, 1, 2, 1, 3}, new int[] {1, 0, 2, -1, 2, 0, 3, -1},
            new int[] {0, 1, 0, 2, 1, 2, 1, 3}, new int[] {1, -1, 1, 0, 2, -1, 3, -1}};
 
        static readonly int[][] P = {
            new int[] {0, 1, 1, 0, 1, 1, 2, 1}, new int[] {0, 1, 0, 2, 1, 0, 1, 1},
            new int[] {1, 0, 1, 1, 2, 0, 2, 1}, new int[] {0, 1, 1, -1, 1, 0, 1, 1},
            new int[] {0, 1, 1, 0, 1, 1, 1, 2}, new int[] {1, -1, 1, 0, 2, -1, 2, 0},
            new int[] {0, 1, 0, 2, 1, 1, 1, 2}, new int[] {0, 1, 1, 0, 1, 1, 2, 0}};
 
        static readonly int[][] T = {
            new int[] {0, 1, 0, 2, 1, 1, 2, 1}, new int[] {1, -2, 1, -1, 1, 0, 2, 0},
            new int[] {1, 0, 2, -1, 2, 0, 2, 1}, new int[] {1, 0, 1, 1, 1, 2, 2, 0}};
 
        static readonly int[][] U = {
            new int[] {0, 1, 0, 2, 1, 0, 1, 2}, new int[] {0, 1, 1, 1, 2, 0, 2, 1},
            new int[]  {0, 2, 1, 0, 1, 1, 1, 2}, new int[] {0, 1, 1, 0, 2, 0, 2, 1}};
 
        static readonly int[][] V = {
            new int[] {1, 0, 2, 0, 2, 1, 2, 2}, new int[] {0, 1, 0, 2, 1, 0, 2, 0},
            new int[] {1, 0, 2, -2, 2, -1, 2, 0}, new int[] {0, 1, 0, 2, 1, 2, 2, 2}};
 
        static readonly int[][] W = {
            new int[] {1, 0, 1, 1, 2, 1, 2, 2}, new int[] {1, -1, 1, 0, 2, -2, 2, -1},
            new int[] {0, 1, 1, 1, 1, 2, 2, 2}, new int[] {0, 1, 1, -1, 1, 0, 2, -1}};
 
        static readonly int[][] X = { new int[] { 1, -1, 1, 0, 1, 1, 2, 0 } };
 
        static readonly int[][] Y = {
            new int[] {1, -2, 1, -1, 1, 0, 1, 1}, new int[] {1, -1, 1, 0, 2, 0, 3, 0},
            new int[] {0, 1, 0, 2, 0, 3, 1, 1}, new int[] {1, 0, 2, 0, 2, 1, 3, 0},
            new int[] {0, 1, 0, 2, 0, 3, 1, 2}, new int[] {1, 0, 1, 1, 2, 0, 3, 0},
            new int[] {1, -1, 1, 0, 1, 1, 1, 2}, new int[] {1, 0, 2, -1, 2, 0, 3, 0}};
 
        static readonly int[][] Z = {
            new int[] {0, 1, 1, 0, 2, -1, 2, 0}, new int[] {1, 0, 1, 1, 1, 2, 2, 2},
            new int[] {0, 1, 1, 1, 2, 1, 2, 2}, new int[] {1, -2, 1, -1, 1, 0, 2, -2}};
 
        static readonly int[][][] shapes = { F, I, L, N, P, T, U, V, W, X, Y, Z };
    }
}