Pentomino tiling

From Rosetta Code
Pentomino tiling is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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



C#

Translation of: Java

<lang csharp>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 };
   }

}</lang> 

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

Go

Translation of: Java

<lang go>package main

import ( 

   "fmt"
   "math/rand"
   "time"

)

var F = [][]int{ 

   {1, -1, 1, 0, 1, 1, 2, 1}, {0, 1, 1, -1, 1, 0, 2, 0},
   {1, 0, 1, 1, 1, 2, 2, 1}, {1, 0, 1, 1, 2, -1, 2, 0},
   {1, -2, 1, -1, 1, 0, 2, -1}, {0, 1, 1, 1, 1, 2, 2, 1},
   {1, -1, 1, 0, 1, 1, 2, -1}, {1, -1, 1, 0, 2, 0, 2, 1},

}

var I = [][]int{{0, 1, 0, 2, 0, 3, 0, 4}, {1, 0, 2, 0, 3, 0, 4, 0}}

var L = [][]int{ 

   {1, 0, 1, 1, 1, 2, 1, 3}, {1, 0, 2, 0, 3, -1, 3, 0},
   {0, 1, 0, 2, 0, 3, 1, 3}, {0, 1, 1, 0, 2, 0, 3, 0}, {0, 1, 1, 1, 2, 1, 3, 1},
   {0, 1, 0, 2, 0, 3, 1, 0}, {1, 0, 2, 0, 3, 0, 3, 1}, {1, -3, 1, -2, 1, -1, 1, 0},

}

var N = [][]int{ 

   {0, 1, 1, -2, 1, -1, 1, 0}, {1, 0, 1, 1, 2, 1, 3, 1},
   {0, 1, 0, 2, 1, -1, 1, 0}, {1, 0, 2, 0, 2, 1, 3, 1}, {0, 1, 1, 1, 1, 2, 1, 3},
   {1, 0, 2, -1, 2, 0, 3, -1}, {0, 1, 0, 2, 1, 2, 1, 3}, {1, -1, 1, 0, 2, -1, 3, -1},

}

var P = [][]int{ 

   {0, 1, 1, 0, 1, 1, 2, 1}, {0, 1, 0, 2, 1, 0, 1, 1},
   {1, 0, 1, 1, 2, 0, 2, 1}, {0, 1, 1, -1, 1, 0, 1, 1}, {0, 1, 1, 0, 1, 1, 1, 2},
   {1, -1, 1, 0, 2, -1, 2, 0}, {0, 1, 0, 2, 1, 1, 1, 2}, {0, 1, 1, 0, 1, 1, 2, 0},

}

var T = [][]int{ 

   {0, 1, 0, 2, 1, 1, 2, 1}, {1, -2, 1, -1, 1, 0, 2, 0},
   {1, 0, 2, -1, 2, 0, 2, 1}, {1, 0, 1, 1, 1, 2, 2, 0},

}

var U = [][]int{ 

   {0, 1, 0, 2, 1, 0, 1, 2}, {0, 1, 1, 1, 2, 0, 2, 1},
   {0, 2, 1, 0, 1, 1, 1, 2}, {0, 1, 1, 0, 2, 0, 2, 1},

}

var V = [][]int{ 

   {1, 0, 2, 0, 2, 1, 2, 2}, {0, 1, 0, 2, 1, 0, 2, 0},
   {1, 0, 2, -2, 2, -1, 2, 0}, {0, 1, 0, 2, 1, 2, 2, 2},

}

var W = [][]int{ 

   {1, 0, 1, 1, 2, 1, 2, 2}, {1, -1, 1, 0, 2, -2, 2, -1},
   {0, 1, 1, 1, 1, 2, 2, 2}, {0, 1, 1, -1, 1, 0, 2, -1},

}

var X = [][]intTemplate:1, -1, 1, 0, 1, 1, 2, 0

var Y = [][]int{ 

   {1, -2, 1, -1, 1, 0, 1, 1}, {1, -1, 1, 0, 2, 0, 3, 0},
   {0, 1, 0, 2, 0, 3, 1, 1}, {1, 0, 2, 0, 2, 1, 3, 0}, {0, 1, 0, 2, 0, 3, 1, 2},
   {1, 0, 1, 1, 2, 0, 3, 0}, {1, -1, 1, 0, 1, 1, 1, 2}, {1, 0, 2, -1, 2, 0, 3, 0},

}

var Z = [][]int{ 

   {0, 1, 1, 0, 2, -1, 2, 0}, {1, 0, 1, 1, 1, 2, 2, 2},
   {0, 1, 1, 1, 2, 1, 2, 2}, {1, -2, 1, -1, 1, 0, 2, -2},

}

var shapes = [][][]int{F, I, L, N, P, T, U, V, W, X, Y, Z}

var symbols = []byte("FILNPTUVWXYZ-")

const ( 

   nRows = 8
   nCols = 8
   blank = 12

)

var grid [nRows][nCols]int var placed [12]bool

func tryPlaceOrientation(o []int, r, c, shapeIndex int) bool { 

   for i := 0; i < len(o); i += 2 {
       x := c + o[i+1]
       y := r + o[i]
       if x < 0 || x >= nCols || y < 0 || y >= nRows || grid[y][x] != -1 {
           return false
       }
   }
   grid[r][c] = shapeIndex
   for i := 0; i < len(o); i += 2 {
       grid[r+o[i]][c+o[i+1]] = shapeIndex
   }
   return true

}

func removeOrientation(o []int, r, c int) { 

   grid[r][c] = -1
   for i := 0; i < len(o); i += 2 {
       grid[r+o[i]][c+o[i+1]] = -1
   }

}

func solve(pos, numPlaced int) bool { 

   if numPlaced == len(shapes) {
       return true
   }
   row := pos / nCols
   col := pos % nCols
   if grid[row][col] != -1 {
       return solve(pos+1, numPlaced)
   }

   for i := range shapes {
       if !placed[i] {
           for _, orientation := range 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

}

func shuffleShapes() { 

   rand.Shuffle(len(shapes), func(i, j int) {
       shapes[i], shapes[j] = shapes[j], shapes[i]
       symbols[i], symbols[j] = symbols[j], symbols[i]
   })

}

func printResult() { 

   for _, r := range grid {
       for _, i := range r {
           fmt.Printf("%c ", symbols[i])
       }
       fmt.Println()
   }

}

func main() { 

   rand.Seed(time.Now().UnixNano())
   shuffleShapes()
   for r := 0; r < nRows; r++ {
       for i := range grid[r] {
           grid[r][i] = -1
       }
   }
   for i := 0; i < 4; i++ {
       var randRow, randCol int
       for {
           randRow = rand.Intn(nRows)
           randCol = rand.Intn(nCols)
           if grid[randRow][randCol] != blank {
               break
           }
       }
       grid[randRow][randCol] = blank
   }
   if solve(0, 0) {
       printResult()
   } else {
       fmt.Println("No solution")
   }

}</lang>

Output:

Sample output: 

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

Java

<lang java>package pentominotiling;

import java.util.*;

public class PentominoTiling { 

   static final char[] symbols = "FILNPTUVWXYZ-".toCharArray();
   static final Random rand = new Random();

   static final int nRows = 8;
   static final int nCols = 8;
   static final int blank = 12;

   static int[][] grid = new int[nRows][nCols];
   static boolean[] placed = new boolean[symbols.length - 1];

   public static void main(String[] args) {
       shuffleShapes();

       for (int r = 0; r < nRows; r++)
           Arrays.fill(grid[r], -1);

       for (int i = 0; i < 4; i++) {
           int randRow, randCol;
           do {
               randRow = rand.nextInt(nRows);
               randCol = rand.nextInt(nCols);
           } while (grid[randRow][randCol] == blank);
           grid[randRow][randCol] = blank;
       }

       if (solve(0, 0)) {
           printResult();
       } else {
           System.out.println("no solution");
       }
   }

   static void shuffleShapes() {
       int n = shapes.length;
       while (n > 1) {
           int r = rand.nextInt(n--);

           int[][] tmp = shapes[r];
           shapes[r] = shapes[n];
           shapes[n] = tmp;

           char tmpSymbol = symbols[r];
           symbols[r] = symbols[n];
           symbols[n] = tmpSymbol;
       }
   }

   static void printResult() {
       for (int[] r : grid) {
           for (int i : r)
               System.out.printf("%c ", symbols[i]);
           System.out.println();
       }
   }

   static boolean tryPlaceOrientation(int[] o, int r, int c, int shapeIndex) {

       for (int i = 0; i < o.length; i += 2) {
           int x = c + o[i + 1];
           int y = r + o[i];
           if (x < 0 || x >= nCols || y < 0 || y >= nRows || grid[y][x] != -1)
               return false;
       }

       grid[r][c] = shapeIndex;
       for (int i = 0; i < o.length; i += 2)
           grid[r + o[i]][c + o[i + 1]] = shapeIndex;

       return true;
   }

   static void removeOrientation(int[] o, int r, int c) {
       grid[r][c] = -1;
       for (int i = 0; i < o.length; i += 2)
           grid[r + o[i]][c + o[i + 1]] = -1;
   }

   static boolean solve(int pos, int numPlaced) {
       if (numPlaced == shapes.length)
           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]) {
               for (int[] orientation : 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;
   }

   static final int[][] F = {{1, -1, 1, 0, 1, 1, 2, 1}, {0, 1, 1, -1, 1, 0, 2, 0},
   {1, 0, 1, 1, 1, 2, 2, 1}, {1, 0, 1, 1, 2, -1, 2, 0}, {1, -2, 1, -1, 1, 0, 2, -1},
   {0, 1, 1, 1, 1, 2, 2, 1}, {1, -1, 1, 0, 1, 1, 2, -1}, {1, -1, 1, 0, 2, 0, 2, 1}};

   static final int[][] I = {{0, 1, 0, 2, 0, 3, 0, 4}, {1, 0, 2, 0, 3, 0, 4, 0}};

   static final int[][] L = {{1, 0, 1, 1, 1, 2, 1, 3}, {1, 0, 2, 0, 3, -1, 3, 0},
   {0, 1, 0, 2, 0, 3, 1, 3}, {0, 1, 1, 0, 2, 0, 3, 0}, {0, 1, 1, 1, 2, 1, 3, 1},
   {0, 1, 0, 2, 0, 3, 1, 0}, {1, 0, 2, 0, 3, 0, 3, 1}, {1, -3, 1, -2, 1, -1, 1, 0}};

   static final int[][] N = {{0, 1, 1, -2, 1, -1, 1, 0}, {1, 0, 1, 1, 2, 1, 3, 1},
   {0, 1, 0, 2, 1, -1, 1, 0}, {1, 0, 2, 0, 2, 1, 3, 1}, {0, 1, 1, 1, 1, 2, 1, 3},
   {1, 0, 2, -1, 2, 0, 3, -1}, {0, 1, 0, 2, 1, 2, 1, 3}, {1, -1, 1, 0, 2, -1, 3, -1}};

   static final int[][] P = {{0, 1, 1, 0, 1, 1, 2, 1}, {0, 1, 0, 2, 1, 0, 1, 1},
   {1, 0, 1, 1, 2, 0, 2, 1}, {0, 1, 1, -1, 1, 0, 1, 1}, {0, 1, 1, 0, 1, 1, 1, 2},
   {1, -1, 1, 0, 2, -1, 2, 0}, {0, 1, 0, 2, 1, 1, 1, 2}, {0, 1, 1, 0, 1, 1, 2, 0}};

   static final int[][] T = {{0, 1, 0, 2, 1, 1, 2, 1}, {1, -2, 1, -1, 1, 0, 2, 0},
   {1, 0, 2, -1, 2, 0, 2, 1}, {1, 0, 1, 1, 1, 2, 2, 0}};

   static final int[][] U = {{0, 1, 0, 2, 1, 0, 1, 2}, {0, 1, 1, 1, 2, 0, 2, 1},
   {0, 2, 1, 0, 1, 1, 1, 2}, {0, 1, 1, 0, 2, 0, 2, 1}};

   static final int[][] V = {{1, 0, 2, 0, 2, 1, 2, 2}, {0, 1, 0, 2, 1, 0, 2, 0},
   {1, 0, 2, -2, 2, -1, 2, 0}, {0, 1, 0, 2, 1, 2, 2, 2}};

   static final int[][] W = {{1, 0, 1, 1, 2, 1, 2, 2}, {1, -1, 1, 0, 2, -2, 2, -1},
   {0, 1, 1, 1, 1, 2, 2, 2}, {0, 1, 1, -1, 1, 0, 2, -1}};

   static final int[][] X = Template:1, -1, 1, 0, 1, 1, 2, 0;

   static final int[][] Y = {{1, -2, 1, -1, 1, 0, 1, 1}, {1, -1, 1, 0, 2, 0, 3, 0},
   {0, 1, 0, 2, 0, 3, 1, 1}, {1, 0, 2, 0, 2, 1, 3, 0}, {0, 1, 0, 2, 0, 3, 1, 2},
   {1, 0, 1, 1, 2, 0, 3, 0}, {1, -1, 1, 0, 1, 1, 1, 2}, {1, 0, 2, -1, 2, 0, 3, 0}};

   static final int[][] Z = {{0, 1, 1, 0, 2, -1, 2, 0}, {1, 0, 1, 1, 1, 2, 2, 2},
   {0, 1, 1, 1, 2, 1, 2, 2}, {1, -2, 1, -1, 1, 0, 2, -2}};

   static final int[][][] shapes = {F, I, L, N, P, T, U, V, W, X, Y, Z};

}</lang> 

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

Kotlin

Translation of: Java

<lang scala>// 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")

}</lang>

Sample output: 

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

Phix

Apart from the shape table creation, the solving part is a translation of Go.
I also added a fast unsolveable() check routine, not that it desperately needed it. <lang Phix>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 shape = {}
       integer letter
       for orientation=0 to 7 do
           sequence this = {}
           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
                           this &= {r-fr,c-fc}
                       end if
                   end if
               end for
           end for
           if not find(this,shape) then
               shape = append(shape,this)
           end if
       end for
       res = append(res,{letter&"",shape})
   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))

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
   grid[r][c] = ch
   for i=1 to length(o) by 2 do
       grid[r+o[i]][c+o[i+1]] = ch
   end for
   return true

end function

procedure un_place(sequence o, integer r, c) 

   grid[r][c] = ' '
   for i=1 to length(o) by 2 do
       grid[r+o[i]][c+o[i+1]] = ' '
   end for

end procedure

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
                   un_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 = 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()</lang>

Output:
FFPPPVVV
YFFPPX-V
YFUUXXXV
YYU-ZX-I
YTUUZZZI
-TTTWWZI
LTNNNWWI
LLLLNNWI

zkl

Translation of: Java

<lang zkl>fcn printResult 

  { foreach row in (grid){ row.apply(symbols.get).concat(" ").println() } }

fcn tryPlaceOrientation(o, R,C, shapeIndex){ 

  foreach ro,co in (o){ r,c:=R+ro, C+co;
     if(r<0 or r>=nRows or c<0 or c>=nCols or grid[r][c]!=-1) return(False);
  }
  grid[R][C]=shapeIndex; foreach ro,co in (o){ grid[R+ro][C+co]=shapeIndex }
  True

} fcn removeOrientation(o, r,c) 

 { grid[r][c]=-1; foreach ro,co in (o){ grid[r+ro][c+co]=-1 } }

fcn solve(pos,numPlaced){ 

  if(numPlaced==target) return(True);

  row,col:=pos.divr(nCols);
  if(grid[row][col]!=-1) return(solve(pos+1,numPlaced));

  foreach i in (shapes.len()){
     if(not placed[i]){

foreach orientation in (shapes[i]){ if(not tryPlaceOrientation(orientation, row,col, i)) continue; placed[i]=True; if(solve(pos+1,numPlaced+1)) return(True); removeOrientation(orientation, row,col); placed[i]=False; } 

     }
  }
  False

}</lang> <lang zkl>reg [private] // the shapes are made of groups of 4 (r,c) pairs 

  _F=T(T(1,-1, 1,0,  1,1,  2,1), T(0,1,  1,-1, 1,0,  2,0),
       T(1,0 , 1,1,  1,2,  2,1), T(1,0,  1,1,  2,-1, 2,0),  T(1,-2, 1,-1, 1,0,  2,-1),
       T(0,1,  1,1,  1,2,  2,1), T(1,-1, 1,0,  1,1,  2,-1), T(1,-1, 1,0,  2,0,  2,1)),
  _I=T(T(0,1,  0,2,  0,3,  0,4), T(1,0,  2,0,  3,0,  4,0)),
  _L=T(T(1,0,  1,1,  1,2,  1,3), T(1,0,  2,0,  3,-1, 3,0),
       T(0,1,  0,2,  0,3,  1,3), T(0,1,  1,0,  2,0,  3,0),  T(0,1,  1,1,  2,1,  3,1),
       T(0,1,  0,2,  0,3,  1,0), T(1,0,  2,0,  3,0,  3,1),  T(1,-3, 1,-2, 1,-1, 1,0)),
  _N=T(T(0,1,  1,-2, 1,-1, 1,0), T(1,0,  1,1,  2,1,  3,1),
       T(0,1,  0,2,  1,-1, 1,0), T(1,0,  2,0,  2,1,  3,1),  T(0,1,  1,1,  1,2,  1,3),
       T(1,0,  2,-1, 2,0,  3,-1),T(0,1,  0,2,  1,2,  1,3),  T(1,-1, 1,0,  2,-1, 3,-1)),
  _P=T(T(0,1,  1,0,  1,1,  2,1), T(0,1,  0,2,  1,0,  1,1),
       T(1,0,  1,1,  2,0,  2,1), T(0,1,  1,-1, 1,0,  1,1),  T(0,1,  1,0,  1,1,  1,2),
       T(1,-1, 1,0,  2,-1, 2,0), T(0,1,  0,2,  1,1,  1,2),  T(0,1,  1,0,  1,1,  2,0)),
  _T=T(T(0,1,  0,2,  1,1,  2,1), T(1,-2, 1,-1, 1,0,  2,0),
       T(1,0,  2,-1, 2,0,  2,1), T(1,0,  1,1,  1,2,  2,0)),
  _U=T(T(0,1,  0,2,  1,0,  1,2), T(0,1,  1,1,  2,0,  2,1),
       T(0,2,  1,0,  1,1,  1,2), T(0,1,  1,0,  2,0,  2,1)),
  _V=T(T(1,0,  2,0,  2,1,  2,2), T(0,1,  0,2,  1,0,  2,0),
       T(1,0,  2,-2, 2,-1, 2,0), T(0,1,  0,2,  1,2,  2,2)),
  _W=T(T(1,0,  1,1,  2,1,  2,2), T(1,-1, 1,0,  2,-2, 2,-1),
       T(0,1,  1,1,  1,2,  2,2), T(0,1,  1,-1, 1,0,  2,-1)),
  _X=T(T(1,-1, 1,0,  1,1,  2,0)),
  _Y=T(T(1,-2, 1,-1, 1,0,  1,1), T(1,-1, 1,0,  2,0,  3,0),
       T(0,1,  0,2,  0,3,  1,1), T(1,0,  2,0,  2,1,  3,0),  T(0,1,  0,2,  0,3,  1,2),
       T(1,0,  1,1,  2,0,  3,0), T(1,-1, 1,0,  1,1,  1,2),  T(1,0,  2,-1, 2,0,  3,0)),
  _Z=T(T(0,1,  1,0,  2,-1, 2,0), T(1,0,  1,1,  1,2,  2,2),
       T(0,1,  1,1,  2,1,  2,2), T(1,-2, 1,-1, 1,0,  2,-2));

const nRows=8, nCols=8, target=12, blank=12; var [const] 

  grid   = nRows.pump(List(),nCols.pump(List(),-1).copy),
  placed = target.pump(List(),False),

  symbols="FILNPTUVWXYZ-".split(""),
  shapes=T(_F,_I,_L,_N,_P,_T,_U,_V,_W,_X,_Y,_Z) // ((a,b, c,d))-->(((a,b),(c,d)))
      .pump(List,List("pump",List,List("pump",List,Void.Read,T.create)));</lang>

<lang zkl>foreach r,c in ([0..nRows-1].walk().shuffle().zip([0..nCols-1].walk().shuffle())[0,4]) 

  { grid[r][c]=blank }  // make sure 4 unique random spots

if(solve(0,0)) printResult(); else println("No solution");</lang>

Output:
F Y Y Y Y U U U
F F F Y - U X U
I F W W L X X X
I W W N L - X T
I W N N L T T T
I V N L L Z Z T
I V N P P P Z -
- V V V P P Z Z
Retrieved from "https://rosettacode.org/wiki/Pentomino_tiling?oldid=266593"