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#[edit]

Translation of: Java
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 };
}
}
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

Java[edit]

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 = {{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};
}
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[edit]

Translation of: Java
// 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")
}

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

zkl[edit]

Translation of: Java
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
}
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)));
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");
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