Previous timing tests (here and here) made it seem likely that template tilings as computable by GenerateTiling could possibly be enumerated more rapidly by a home brewed algorithm. The underlying reason is that SatsifiabilityInstances is designed for a special class of boolean functions (using only And, Or, Not); whereas, the template tiling problem is really just an exact cover problem. It turns out that our developing intuition on this question is probably correct. The purpose of this memo is to show base case evidence, which looks very promising with regard to a competitive new method for GenerateTiling (and other related search functions).
In fact, the first attempt was a total failure, where pre-existing code even outpaced construction of the basic data for the exact cover problem. We then went back to the drawing board to find a much simpler schema, which is easy to understand and easy to compute on. The schema is computed by two functions only:
PadTemplate[template_, size_] :=
With[{colLen = size[[2]] + Dimensions[template][[2]] - 1},
Join[PadRight[#, colLen, _] & /@ template,
Table[ConstantArray[_, colLen], {size[[1]] - 1}]]]
AllTemplates[template_, size_] := With[{
padded = PadTemplate[template, size]},
Catenate@Outer[Function[{row, col},
RotateRight[RotateRight[#, col] & /@ padded, row
][[-size[[1]] ;; -1, -size[[2]] ;; -1]]],
Range[0, size[[1]] + Dimensions[template][[1]] - 2],
Range[0, size[[2]] + Dimensions[template][[2]] - 2],
1]]
And computations are done using only two or three functions:
EitherMatchQ[a_, b_] := Or[MatchQ[a, b], MatchQ[b, a]]
RowsCombine[row1_, row2_] := Catch[MapThread[If[EitherMatchQ[#1, #2],
First[Sort[{#1, #2}]], Throw[Nothing] ] &, {row1, row2}]]
GenerateBinaryCover[templates_, size_Integer] :=
GenerateBinaryCover[templates, {size, size}]
GenerateBinaryCover[templates_, size_] := Fold[
Union@Catenate[Outer[RowsCombine, #1, #2, 1]] &, {Table[_,
Times @@ size]},
Transpose[(Catenate /@ AllTemplates[#, size]) & /@ templates ]]
The basic use case is:
AbsoluteTiming[
Length@ResourceFunction["GenerateTiling"][{IdentityMatrix[2],
Reverse[IdentityMatrix[2]]}, {}, 10, All]]
Out[]= {0.170944, 2}
AbsoluteTiming[
Length@GenerateBinaryCover[{IdentityMatrix[2],
Reverse[IdentityMatrix[2]]}, 10]]
Out[]= {0.073363, 2}
From what I could read, this isn't written in the documentation, but setting "All" disables the fast SAT solver. In subsequent tests, we need to gauge comprehensive GenerateBinaryCover against GenerateTiling when it looks for only one result. In that case, the SAT solver wins the timing test above, because there is an easy answer to be found. In general, if there is no solution, the SAT solver still has to traverse an entire search tree, so does not necessarily improve its time over setting "All".
We will generate all binary $2 \times 2$ templates, and recursively test whether or not finite subsets lead successfully to a tiling of a $3\times3$ space. Level one only leads to monotonic, all black or all white tilings. The corresponding all-black and all-white templates can be filtered out of the set of sixteen, to obtain inputs for subsequent levels of the search:
templates2 = Partition[IntegerDigits[#, 2, 4], 2] & /@ Range[1, 2^4 - 2];
Grid[Partition[ArrayPlot[#, ImageSize -> 50] & /@ templates2, 7],
Spacings -> {1, 1}]
data1 = Length@GenerateBinaryCover[#, 3] & /@ Subsets[templates2, {2}];
data2 = Replace[
ResourceFunction["GenerateTiling"][#, {}, 3,
All], {_Failure -> 0, x_List :> Length[x]}] & /@
Subsets[templates2, {2}];
SameQ[data1, data2]
Flatten[Position[data1, 2]]
Out[] = True
Out[] = {34, 51, 58}
The positions tell us which pairs of templates lead to periodic patterns. These can be filtered out when going to level 3, but first we need to check times:
times1 = AbsoluteTiming[GenerateBinaryCover[#, 3];][[1]] & /@
Subsets[templates2, {2}];
times2 = AbsoluteTiming[
ResourceFunction["GenerateTiling"][#, {}, 3];][[1]] & /@
Subsets[templates2, {2}];
Total[times1]
Total[times2]
Out[] = 0.068119
Out[] = 0.134045
It's only a factor of two overall, but we're testing a relatively naive and comprehensive Fold-based searcher against a solver, which we assume to be compiled and optimized by capable computer scientists. In that case, a factor of two sounds pretty good. Let's look more closely at the timing data:
ListPlot[{times2, times1},
PlotStyle -> {Red, Darker@Green},
PlotRange -> All]
Notice three spikes on the green data (for GenerateBinaryCover) where the searcher is finding more than one viable tiling. These spikes could probably be removed by depth first searching, and perhaps an optimized depth-first search would increase the timing gap to a reliable order of magnitude.
At level three we find four more positive results:
templates34Sub = Select[Subsets[templates2, {3}],
And @@ Function[{set}, !
SubsetQ[set, Subsets[templates2, {2}][[#]]] & /@ {34, 51,
58}][#] &]
data1 = Length@Union@GenerateBinaryCover[#, 3] & /@ templates34Sub;
data2 = Replace[
ResourceFunction["GenerateTiling"][#, {}, 3,
All], {_Failure -> 0, x_List :> Length[x]}] & /@
templates34Sub;
SameQ[data1, data2]
Position[data1, x_Integer /; x > 0]
Out[] = True
Out[] = {{42}, {90}, {268}, {283}}
And the timing comparison is:
times13 = AbsoluteTiming[GenerateBinaryCover[#, 3];][[1]] & /@
templates34Sub;
times23 = AbsoluteTiming[
ResourceFunction["GenerateTiling"][#, {}, 3];][[1]] & /@
templates34Sub;
ListPlot[{times13, times23},
PlotStyle -> {Darker@Green, Red},
PlotRange -> All]
Similarly for levels 4 & 5:
At level five total time is a draw due to increasing variance of the green data set, why? The variance is about a factor of eight, and eight is also the number of equivalent tilings found when a set is capable of tiling. So the variance can probably be blamed on the fact that GenerateBinaryCover is not designed for depth-first searching.
Although the timing stats above show a clear but narrow win for our simlpe algorithm, more work remains to be done improving the search recursion. More testing needs to be done to see if the ExactCover method scales as well as that SAT solver, maybe not.
