Pentomino tiling

From Rosetta Code
Revision as of 12:27, 16 September 2016 by rosettacode>Fwend (formatting of task description)
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



Java

<lang java>import java.util.*;

public class PentominoTiling { 

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

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

   static int[][] grid = new int[nRows][nCols];
   static boolean[] placed = new boolean[target];

   public static void main(String[] args) {
       Random rand = new Random();

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

       for (int i = 0; i < 4; i++)
           grid[rand.nextInt(nRows)][rand.nextInt(nCols)] = blank;

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

   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 == 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]) {

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

   // four (x, y) pairs are listed, (0,0) not included
   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

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=266583"