Pentomino tiling: Difference between revisions

=={{header|zkl}}==

{{trans|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>

{{out}}

<pre>

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

</pre>