Triominoes

Introduction

Triominoes on 12 by 9 Grid

The picture shows one of the 20 574 308 184 277 971 (3*89*1489*51751063817 should you be interested) ways that the six triominoes can completely cover the 12 by 9 grid of squares without overlap. This note shows how this big number was calculated. A triomino is a plane shape made by connecting 3 same sized squares edge to edge. When rotations and reflections are not considered to to be distinct shapes there are two different triominoes, the I and the L. If rotations and reflections are considered to be distinct shapes there are six distinct shapes as can be seen in the picture. There are 41 ways that a 2 by 9 grid can be filled. Problem 161 in Project Euler asks "In how many ways can a 9 by 12 grid be tiled by the six triominoes?"

Project Euler is a website dedicated to a series of computational problems intended to be solved with computer programs. In April 2015 it offered 502 problems, with new ones expected to be added regularly. Problems are of varying difficulty but each should be solvable in less than a minute using an efficient algorithm on a modestly powered computer. The number of people who have solved a problem is an indication of its difficulty. A forum specific to each question may be viewed after the user has correctly answered the given question. In April 2015 Project Euler has about 479602 registered members from all over the world who had solved at least one problem. In April 2015, 1202 people had solved Problem 161.

Methodology

Recursive backtracking programmes are usually good for solving complete cover problems and one was used to work out how reassemble the Bedlam Cube and to put the 13 pieces, the 12 pentacubes and the single tetracube back into their box.

A classic example of a recursive backtracking programme is used to solve the queens problem that finds all arrangements of chess queens on a chess board so that no queen attacks another. In Mathematica a recursive function that works is

nQueens[r_]:= If[r===n+1,Print[q],
Do[ legal=True;
Do[If[q[[i]]===jq[[i]]===j+r-iq[[i]]===j-r+i,legal=False] ,{i,1,r-1}];
If[legal,q[[r]]=j;nQueens[r+1]] ,{j,1,n}]];

n is the number of squares on each side of the chessboard. r is the first empty row number. q represents the solution, for example q might be {3,1,0,0} when there is a queen in row 1 in column 3 and in row 2 in column 1. The two Dos check the legality of placing a queen in each of the 4 columns in the empty third row. For {j,1,n} the cell is initially considered to be legal. It is then checked against the queens that are already on the board. If j is the same column or diagonal as the queen in a previous row then legal becomes false and the programme moves to the next j. If the queen is legally placed then q[[r]] becomes j, the solution is updated and the function nQueens[r+1] looks at the next line. If r>n then there is a solution and the function will look for further solutions.

Looking a four sided chess board by calling on the function n Queens with the Mathematica line

n=4;q={0,0,0,0};nQueens[1]

we get the two solutions {2,4,1,3} and {3,1,4,2}.

Method 1

To find the different ways of arranging the 6 triominoes on a 12 by 9 grid the classic recursive and backtracking function was developed into the following set of lines written in Mathematica.

count:=Total[world[[Range[2,Length[world]],#]]]&/@Range[Length[world[[1]]]];
square:=Select[Ordering[Total[world[[Range[2,Length[world]],#]]]&/@Range[Length[world[[2]]]]],#>1&][[1]];
placings:=Flatten[Position[world[[2;;Length[world],square]],1,1]]+1;
columns:=Select[Flatten[Position[world[[row]],1]],#>1&];
rows :=(list=world[[#]][[columns]]&/@Range[2,Length[world]];Reap[Do[If[MemberQ[list[[i]],1],Sow[i]],{i,1,Length[list]}]][[2,1]]+1);
partialQ:=!MemberQ[Drop[Total[world[[Range[2,Length[world]],#]]]&/@Range[Length[world[[1]]]],1],0];

prog[r_]:=If[r===n+1, AppendTo[solutions,solution],
world=root;
Do[row=Level[Position[world[[All,1]],solution[[i]]],2][[1]];
world=Fold[Drop[#1,{},{#2}]&,Fold[Drop[#1,{#2}]&,world,Reverse[rows]],Reverse[columns]],{i,1,r-1}];
If[partialQ,stack[[r]]=world[[placings]][[All,1]];
Do[solution[[r]]=sol;prog[r+1],{sol,stack[[r]]}]] ]

root is an array that is 527 lines long and 109 columns wide. It identifies every way that each of the 6 triominoes can be placed squarely in the 12 by 9 grid. The first column gives the row number and the first row gives the number of the squares on which the triomino is placed. For example the row root[[100]] is{100,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}. The positions of the 1s gives the squares in the grid over which this triomino is placed.

The Mathematica lines needed to kick start this recursive function are
n=36;
stack=Table[{},{n}];
solution={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
solutions={};
Monitor[prog[1],Length[solutions]]

First Arrangement

The first solution generated was {2,12,287,10,285,8,283,6,281,4,279,277,35,45,320,43,318,41,316,39,314,37,312,310,68,343,70,345,72,347,74,349,76,351,78,353}. Each number in the solution identifies the row of the root and hence the placing of a triomino. This solution which is illustrated in the above picture. It didn't really need a computer programme to find this arrangement. On my computer this method finds about 90 new different ways of filling a 12 by 9 grid in a minute. It would take many years to find and count all of them. So another way must be found.

Method 2

The second method divides the problem into 10 steps where the first 9 steps each fill the first row of a 9 by 3 grid. The recursive function now looks like this.

count:=Total[world[[Range[2,Length[world]],Drop[Flatten[Position[world[[1]],#]&/@Range[9]],1]]]];
placings:=Flatten[Position[world[[2;;Length[world],2]],1,1]]+1;
columns:=Select[Flatten[Position[world[[row]],1]],#>1&];
rows :=(list=world[[#]][[columns]]&/@Range[2,Length[world]];Reap[Do[If[MemberQ[list[[i]],1],Sow[i]],{i,1,Length[list]}]][[2,1]]+1);
partialQ:=!MemberQ[count,0];
completeQ:=(range=Drop[Flatten[Position[newroot[[1]],#]&/@Range[9]],1];Total[newroot[[Flatten[Position[newroot[[All,1]],#]&/@Select[solution,#=!=0&]]]][[All,#]]]&/@range==Table[1,{Length[range]}]);

prog[r_]:= ( solution=Drop[Flatten[Append[Take[solution,r-1],{0,0,0,0,0,0,0,0,0}]],-r+1];
If[completeQ,AppendTo[solutions,solution],
world=newroot;
Do[row=Level[Position[world[[All,1]],solution[[i]]],2][[1]];
world=Fold[Drop[#1,{},{#2}]&,Fold[Drop[#1,{#2}]&,world,Reverse[rows]],Reverse[columns]],{i,1,r-1}];
If[partialQ,stack[[r]]=world[[placings]][[All,1]];
Do[solution[[r]]=sol;prog[r+1],{sol,stack[[r]]}]] ])

Although it looks similar to the recursive function in Method 1 there are some significant differences. Solutions can vary in size so must be trimmed and a complete solution no longer depends on n but when the first row of the 9 by 3 grid is covered.

root is now an array that is 49 lines long and 28 columns wide. It identifies every way that each of the 6 triominoes can be placed squarely in the 9 by 3 grid, covering each square on its first row. The first column gives the row number and the first row gives the number of the squares on which the triomino is placed.

The recursive function is used int he following programme.

cs:=Flatten[Position[sp,1]]+1;
rs :=Union[Sort[Flatten[Position[world[[Range[2,Length[world]],#]],1]&/@cs]]]+1;

wwwww:=(Monitor[Timing[
xxxxx={};
numberofnextsteps={};
Do[
sp=startingpositions[[r]];
numberof=numberofsps[[r]];
world=root;
newroot=Fold[Drop[#1,{},{#2}]&,Fold[Drop[#1,{#2}]&,world,Reverse[rs]],Reverse[cs]];
n=9;
stack=Table[{},{n}];
solution={0,0,0,0,0,0,0,0,0};
solutions={};
prog[1];
nextstartingpositions={};
Do[AppendTo[nextstartingpositions,
Drop[Total[Prepend[root[[Select[solutions[[i]],#=!=0&]]],Flatten[Append[Prepend[sp,1],{0,0,0,0,0,0,0,0,0}]]][[All,#]]]&/@Range[28],10]],{i,1,Length[solutions]}];
positions={};
Do[list=nextstartingpositions[[i]];
If[MemberQ[xxxxx,list],AppendTo[positions,Position[xxxxx,list]],
AppendTo[xxxxx,list];AppendTo[numberofnextsteps,numberof]],
{i,1,Length[nextstartingpositions]}]; numberofnextsteps[[#]]+=numberof&/@Flatten[positions];
,{r,1,Length[startingpositions]}];
{Length[xxxxx],Total[numberofnextsteps]}],r])

At each step there is a set of startingpositions each of which describes the squares of the 9 by 3 grid that are filled. At Step1 the first and second rows have no filled squares so
startingpositions={{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}} and the number of starting positions numberofsps={{1}} and as a result newroot = root. With this start, the recursive function prog[1] will give 1738 solutions. One solution, solutions[[669]] = {10,45,23,16,42,0,0,0,0}, looks like the following:-

solutions[[669]]

And the starting position for the next step will be {0,1,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,1}. Some of the 1738 solutions will give the same startingposition and the number of ways of reaching a given startingposition is counted. By iterating this procedure 8 more times the number of starting position and the number of each can be found at each step.

Do[startingpositions=xxxxx;numberofsps=numberofnextsteps;wwwww;Print[TimeUsed[]," ",Length[xxxxx]," ",Total[numberofnextsteps]],{8}]

Step TimeUsed in Sec Number of Different Starting Positions Total Number of Solutions
One 12.68 1 1 738
Two 296.79 1296 41 449
Three 1198.84 5097 1 011 735
Four 2151.55 6535 34 800 152
Five 3131.44 6561 975 983 958
Six 4096.68 6561 26 854 709 445
Seven 5107.75 6561 792 279 280 542
Eight 6097.19 6561 22 401 220 849 335
Nine 7060.43 6561 631 253 071 120 930

Final Step

There are 6561 different startingpositions at the beginning of Step Ten but there is a large number separate ways of reaching each of these starting positions. For example there are 4 884 136 683 215 ways of reaching startingposition at Step Ten with {1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0} and 396 447 933 ways of reaching the startingposition with {1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1}. These are the maximum and minimum number of ways respectively. The recursive function is adapted and used as follows. finalroot is a 28 by 95 array that describes how each of the six triominoes can be placed on a 9 by 3 grid. The first column gives the row number and the first row numbers the squares.

finalstartingpositions=xxxxx;
numberoffinalstartingpositions=numberofnextsteps;

fprog[r_]:=If[r===n+1,AppendTo[solutions,solution],
world=newroot;
Do[
row=Level[Position[world[[All,1]],solution[[i]]],2][[1]];
world=Fold[Drop[#1,{},{#2}]&,Fold[Drop[#1,{#2}]&,world,Reverse[rows]],Reverse[columns]],{i,1,r-1}];
If[partialQ,stack[[r]]=world[[placings]][[All,1]];
Do[solution[[r]]=sol;fprog[r+1],{sol,stack[[r]]}]] ]

finalsolutions={};
Monitor[Timing[Do[ sp=finalstartingpositions[[r]];
world=finalroot;
newroot=Fold[Drop[#1,{},{#2}]&,Fold[Drop[#1,{#2}]&,world,Reverse[rs]],Reverse[cs]];
n=9-Total[sp]/3;
stack=Table[{},{n}];
solution=Table[0,{n}];
solutions={};
fprog[1];
AppendTo[finalsolutions,Length[solutions]], {r,1,Length[finalstartingpositions]}]],r]

.

doesthiswork={};
Do[AppendTo[doesthiswork,finalsolutions[[i]]*numberoffinalstartingpositions[[i]]],{i,1,Length[finalsolutions]}];
Total[doesthiswork] = 20574308184277971

This programme takes each of the 6561 finalstartingpositions in turn and finds everyway that the 9 by 3 grid can then be covered in triominoes. The number of solutions is then counted for each finalstartingposition. The total of the products of the count and the number of ways of reaching each finalstartingposition for all finalstartingpositions is 20 574 308 184 277 971.

Forum

This number was entered into the answer box for Problem 161 in ProjectEuler happily allowing access to the thread for this problem. There were 91 posts, the first in September 2007 and the last in February 2015. Only one of these used Mathematica. All much quicker than the above though none showing a preferred method, inspite of Method 2 breaking the one minute rule. Saving a random solution at each step leads to the graphic of a random layout of 36 Triominoes on a 12 by 9 Grid seen at the beginning of this note.