Domino and Tromino Tilings

Adam Rumpf, 10/16/2017

Introduction

If a single square is removed from a (2^n)×(2^n) chess board, then it is always possible to tile the remaining squares using L-shaped trominos. Likewise, if two opposite-colored squares are removed, then it is always possible to tile the remaining squares using standard dominos. This program generates tromino and domino tilings for chess boards of various sizes, with controls to select the type of tile used, the size of the board, and the location(s) of the blank square(s).

The tromino tiling algorithm is recursive, and is based on the inductive proof of the existence of the tiling. Given a (2^n)×(2^n) board missing one square, we can divide it into four (2^(n-1))×(2^(n-1)) boards, exactly one of which is missing a square. From the remaining three we remove the corner at the center of the board. This results in four (2^(n-1))×(2^(n-1)) boards, each missing a square. Three of these missing squares are located at the center of the board, and can easily be tiled by a single L-shaped tromino. To tile the rest of the sub-boards, we recursively apply the process until reaching the base case of a 2×2 board missing a square, which can obviously be tiled by a single L-shaped tromino.

The domino tiling algorithm is also based on the proof of the existence of the tiling. We begin by finding a Hamiltonian cycle on the original board. Removing two squares cuts this cycle into one or two paths. The tiling can be generated by laying down dominos in line with the path(s). Note that it is only possible to complete this domino tiling if the removed squares are opposite colors. This is because each domino must cover one black square and one white square, so any tileable board must have the same number of each color square.

Code

Initialization

(* Given n and a coordinate, find a tiling of the remaining grid using L-shaped triominoes. The output is an array of real numbers, where cells with the same real number correspond to the same triomino, and the cell with a value of 0 represents the blank. *)
tmat[n_,p_:{0,0}]:=Module[{pos=Round[p],grid=ConstantArray[1,{(2^n),(2^n)}],squares={}},
(* Setting up the grid. *)
If[Min[pos]<1||Max[pos]>(2^n),
pos=RandomInteger[{1,(2^n)},2];
];
grid[[pos[[1]],pos[[2]]]]=0;
(* Call the recursive subroutine tsub to come up with the colors. *)
grid=tsub[grid];
(* Draw the result. *)
grid
]

(* Recursive subroutine for the triomino tiling algorithm. *)
tsub[m_]:=Module[{mat=m,s=Length[m],tl,tr,bl,br,num=RandomReal[]},
(* If we have a 2x2 grid, recolor it. *)
If[s≤2,
For[i=1,i≤2,i++,
For[j=1,j≤2,j++,
If[mat[[i,j]]==1,
mat[[i,j]]=num;
];
];
];,
(* Otherwise, begin by quartering the grid. *)
tl=mat[[1;;(s/2),1;;(s/2)]];
tr=mat[[1;;(s/2),(s/2)+1;;s]];
bl=mat[[(s/2)+1;;s,1;;(s/2)]];
br=mat[[(s/2)+1;;s,(s/2)+1;;s]];
(* Find where the single colored square is, and color the other three centers. *)
If[Count[Flatten[tl],1]==((((s/2)))^2),
tl[[(s/2),(s/2)]]=num;
];
If[Count[Flatten[tr],1]==((((s/2)))^2),
tr[[(s/2),1]]=num;
];
If[Count[Flatten[bl],1]==((((s/2)))^2),
bl[[1,(s/2)]]=num;
];
If[Count[Flatten[br],1]==((((s/2)))^2),
br[[1,1]]=num;
];
(* Color the rest of the squares by going through the same process. *)
tl=tsub[tl];
tr=tsub[tr];
bl=tsub[bl];
br=tsub[br];
(* Reassemble the main grid. *)
mat[[1;;(s/2),1;;(s/2)]]=tl;
mat[[1;;(s/2),(s/2)+1;;s]]=tr;
mat[[(s/2)+1;;s,1;;(s/2)]]=bl;
mat[[(s/2)+1;;s,(s/2)+1;;s]]=br;
];
mat
]

(* Paint the regions deterministically by first finding the centroids of all regions and using the centroids as random seeds. *)
Dynamic[pal];
pal=1;
cpainter[mat_,pal_]:=Module[{list,temp,c,s},
list=DeleteCases[DeleteDuplicates[Flatten[mat]],0];
temp=Table[Position[mat,list[[i]]],{i,1,Length[list]}];
c=ConstantArray[{0,0},Length[temp]];
Do[
c[[i]]={((Max[temp[[i,;;,1]]]+Min[temp[[i,;;,1]]])/2),((Max[temp[[i,;;,2]]]+Min[temp[[i,;;,2]]])/2)},
{i,1,Length[c]}];
s=ConstantArray["",Length[c]];
Do[
SeedRandom[Ceiling[30(c[[i,1]]+pal Length[mat]c[[i,2]])]];
s[[i]]=RandomReal[1,3],
{i,1,Length[c]}];
ArrayPlot[mat,ColorRules->Join[{0->White},Table[list[[i]]->RGBColor@@s[[i]],{i,1,Length[list]}]]]
]

(* Given n, generate a Hamiltonian cycle on a (2^n)×(2^n) grid and output the resulting graph. *)
cyclegraph[n_]:=Module[{e={}},
e=Join[e,Table[{i,1}\[UndirectedEdge]{i+1,1},{i,1,(2^n)-1}]];(* left side *)
e=Join[e,Table[{(2^n),j}\[UndirectedEdge]{(2^n),j+1},{j,1,(2^n)-1}]];(* bottom *)
e=Join[e,Table[{i,(2^n)}\[UndirectedEdge]{i-1,(2^n)},{i,(2^n),2,-1}]];(* right side *)
Do[
(* vertical bars *)
e=Join[e,Table[{i,j}\[UndirectedEdge]{i+1,j},{i,1,(2^n)-2}]],
{j,2,(2^n)-1}];
e=Join[e,Table[{1,j}\[UndirectedEdge]{1,j+1},{j,1,(2^n)-1,2}]];(* top horizontal links *)
e=Join[e,Table[{(2^n)-1,j}\[UndirectedEdge]{(2^n)-1,j+1},{j,2,(2^n)-2,2}]];(* bottom horizontal links *)
e
]

(* Given a graph, return the names of the leaves. *)
findleaves[g_]:=Module[{v,leaf={}},
v=VertexList[g];
Do[
If[VertexDegree[g,v[[i]]]==1,
leaf=Append[leaf,v[[i]]];
],
{i,1,Length[v]}];
leaf
]

(* Given a graph and a starting vertex, perform a DFS, and return a list of the vertices visited in order. *)
dfs[g_,s_]:=Reap[DepthFirstScan[g,s,{"PrevisitVertex"->Sow}]][[2,1]]

(* Given n, and the coordinates of two vertices to delete, generate a (2^n)×(2^n) array of real numbers, where entries with the same value correspond to the same domino. *)
dmat[n_,p1_:{1,1},p2_:{1,2}]:=Module[{g,gc,cc,start,chain,mat=ConstantArray[0,{(2^n),(2^n)}]},
g=VertexDelete[Graph[cyclegraph[n]],{p1,p2}];
cc=ConnectedComponents[g];
gc=Table[Subgraph[g,cc[[k]]],{k,1,Length[cc]}];
If[Length[gc]==2,
(* two separate chains *)
start={findleaves[gc[[1]]][[1]],findleaves[gc[[2]]][[1]]},
(* one chain *)
start={findleaves[gc[[1]]][[1]]};
];
Do[
(* assign random numbers to pairs of consecutive vertices in each chain *)
chain=dfs[gc[[i]],start[[i]]];
Do[
mat[[(chain[[j,1]]),(chain[[j,2]])]]=mat[[(chain[[j+1,1]]),(chain[[j+1,2]])]]=RandomReal[],
{j,1,Length[chain]-1,2}],
{i,1,Length[start]}];
mat
]

Demonstration

Manipulate[Module[{pt1,pt2,mat,black,white},
black=Flatten[Table[{i,2j-Mod[i+1,2]},{j,1,n/2},{i,1,n}],1];
white=Flatten[Table[{i,2j-Mod[i,2]},{j,1,n/2},{i,1,n}],1];
If[type==3,
(* triominoes *)
pt1={Min[Floor[x1[[1]]],n],Min[Floor[x1[[2]]],n]};
mat=Reverse[Transpose[tmat[Log[2,n],pt1]]],
(* dominoes *)
pt1=Nearest[black,x1][[1]];
pt2=Nearest[white,x2][[1]];
mat=Reverse[Transpose[dmat[Log[2,n],pt1,pt2]]];
];
cpainter[mat,pal]
],{{type,3,"tile type"},{3->"triominoes",2->"dominoes"},RadioButton},"",
PaneSelector[{3->Row[{Control[{{x1,{1.5,n+0.5},"blanks"},{1,1},{n+1,n+1}}]}],2->Row[{Control[{{x1,{1.5,n+0.5},"blanks"},{1,1},{n+1,n+1}}],"",
Control[{{x2,{1.5,n+0.5},""},{1,1},{n+1,n+1}}]}]},Dynamic[type]],"",
{{n,(2^3),"board width"},Table[(2^k),{k,1,5}]},"",
Button["randomize colors",pal=RandomInteger[{1,10000}]],ControlPlacement->Left,SaveDefinitions->True,TrackedSymbols:>{type,x1,x2,n,pal}]