We describe a general method, Geometrically Constrained Tree Search (GCTS), to solve certain combinatorial problems of tree search with "geometric constraints", in some respect similar to methods in geometric deep learning, specifically equivariant neural networks. For illustration we shall focus on the tiling problem: given a set of tiles (in 2D or 3D), with or without local matching rules, determine if and how they tile the plane or space, or a subset with prescribed boundary. When working, it shall compensate for a rudimentary (greedy and slow, no heuristics) tree search algorithm, and may provide an interpretable and provably correct algorithm. It shall become clear what is meant by all this.
We shall further restrict to tilings that can be placed on a lattice, i.e., all the vertices shall be on a lattice. In fact, this study was partly inspired by the discovery of the hat and the turtle (Smith et al, 2023) which, aside from being a solution to the "ein stein" problem that was the holy grail for much of tiling theory, actually live on the \(A_2\) lattice. This goes to show that, despite their rather rigid nature, lattice tilings are rich enough to be a furtile playground for combinatorial and discrete geometry, and as a portal to logic and computation via Wang tiles. Moreover, it appears that many known space-fillers are lattice tiles on the standard integer lattice in \(\mathbb{R}^3\).
Tiles and tilings
Let's fix the (standard) \(\mathbb{Z}^3\) lattice in the Euclidean 3-space. By a lattice tile (or tile for short) we shall mean a function
that is finitely supported, taking values between 0 and 1, inclusive. The interpretation of the value \(t({\bf x})\) at a point \({\bf x} \in \mathbb{Z}^3\) shall be the "solid angle" at \({\bf x}\), or the proportion of the \(\epsilon\)-neighborhood of \({\bf x}\) that is supposed to be "inside the tile". (We leave aside the question if or when a polyhedral tile in the usual sense, with all its vertices on the lattice, has a faithful realization as a lattice tile per our definition.)
A lattice tile \(t\) is said to tile space if there exists a subset \(K\) of the group \(G\) of symmetries of the lattice such that
as a function on \(\mathbb{Z}^3\). The group \(G\) consists of permuting and reversing the axes, and translating by integral vectors. Similar definition can be made for a set of tiles \(\{t_1, t_2, \ldots, t_n \}\) to tile space:
(If the right-hand side is replaced by a constant \(N > 1\), it is known as a multi-tiling, or an \(N\)-fold tiling.)
Example. The regular tetrahedron. The vertices are \([1,0,0]\), \([0,1,0]\), \([0,0,1]\), and \([1,1,1]\), where the solid angle is irrational, thus the regular tetrahedron does not tile space. However, together with the regular octahedron (with vertices at \(\pm {\bf e}_i\), \(i=1,2,3\)), they do tile space, in a unique way.
Naturally, if the tile \(t_i\) itself has inherent symmetry, in the sense that \(t_i({\bf x}) = t_i(g^{-1}{\bf x})\), we should "quotient it out" from \(G\) when searching for \(K_i\).
Example. The tetrahedron with vertices at \([0,0,0]\), \([1,0,0]\), \([1,1,0]\), and \([1,1,1]\) does tile space, with six copies filling a unit cube. The value at the four vertices are 1, 3, 3, and 1 forty-eighths, respectively.
Example. The hat and the turtle (see figures). Each is a 14-sided polygon lying on the \(x_1+x_2+x_3=0\) plane, and we can turn it into a cylinder to fit our 3D tiling game. Alternatively, we may restrict \(G\) to symmetries of the sublattice, and to assign the values to be (plain-old, 2D) angles. It happens that the only values are 3, 4, 6, 8, and 9 twelveths. The remarkable fact about the hat (and the turtle) is that it tiles the plane, and only non-periodically (Smith et al, 2023).
Finding the subsets \(K_i\) (or showing none exists) is a problem of combinatorial tree search. We could place the first tile anywhere (or simply with \(i=1\), \(g=1\)), and for a specific \({\bf p}\) with \(0 < t_1({\bf p}) < 1\), there are finitely many ways to place the second tile (choices of \(i\) and \(g \in G\)) such that \(t_i(g^{-1} {\bf p}) > 0\) and
for all \({\bf x}\), and we put this \(g\) in \(K_i\), and repeat the process. Thus we obtain a finite-branching tree to search over. A branch stops or dies if it runs out of choices (for any "boundary point" \({\bf p}\)). We are particularly interested in tiles that admit nontrivial tilings: neither too restricted that the branchings all have a unique choice, nor too loose that any branch appears to lead to valid tilings. Note that this algorithm could not tell whether a (partial) tiling is periodic, and by itself is unable to say if it actually extends to a tiling of the whole space.
The live search maintains this choice structure as a bipartite graph: one class of vertices consists of the current frontier points, and the other consists of candidate tile placements, with an edge whenever a candidate can legally complete a frontier point. Placing or removing a tile changes only the nearby incidences, so the graph is updated locally and rolled back with the search branch. The algorithm can therefore branch at a frontier point of minimum degree without recomputing every point's candidate list from scratch.
In practice, it may be more natural to "branch over" faces instead of boundary points; and we may adopt simple rules to choose the face or the point \({\bf p}\) for each branching, but no need to employ more sophisticated heuristics. This is essentially what is implemented here.
Markings and matching rules
When playing jigsaw puzzles, we would direct our attention to the colors and patterns on the pieces; two pieces fit not just by the geometry (shape of the boundary) but the patterns have to "match". Similarly in tiling, we would often, for the sake of forcing aperiodicity, introduce "markings" on the tiles, along with "matching rules" that the markings need to match in certain ways. Not the least, the Wang tiles work via color matching. Let's formalize all these in a definition, specialized for our discrete setting.
By a marking on a lattice tile \(t\), we shall mean a function
with support that may be larger than that of the tile. We say that \(t\) tiles space with marking \(m\) if, in addition to the above, we have for any \(g, h \in K\),
on the overlap of their supports. This way, all these transformed functions would glue to be a "global section" of this (trivial) sheaf.
It is natural to extend this definition to a vector bundle:
and there is an action of \(G\) on \(\mathbb{R}^n\) (a representation), then the matching rule would be
on the overlap.
Remark (made by GPT). In Yasushi Nagai's A General Framework for Tilings, Delone Sets, Functions, and Measures and Their Interrelation (2019), a tiling and its global marking function are abstract patterns in possibly different \(G\)-abstract pattern spaces. Nagai writes this symmetry group as \(\Gamma\). His Theorems 3.6 and 5.5 say, under their hypotheses, that pattern-equivariant functions determine the original pattern up to mutual local derivability (MLD); Theorem 5.5 includes actions on vector-valued functions.
Example. The turtle admits a marking of straight lines (see Akiyama & Araki or mathblock8128). The two colors represent \(\pm 1\) values for the lattice points on three separate markings, or a rank-3 bundle. The group \(G\) acts on \(\mathbb{R}^3\) by permuting and negating the components (swapping the two colors upon reflections). Note that the domain of each marking may be taken to be arbitrarily long, a sign of long-range order.
Example. The classic "domino puzzle" (with the checkerboard argument) may be cast as a problem of tiling with marking. It seems that a good source of candidates for markings would be the eigenfunctions of the Laplacian operator, with Dirichlet or Neumann (or mixed) boundary conditions.
The (naive) tiling algorithm can be easily modified to incorporate this kind of matching rule, simply by excluding those branches that disagree on overlap, and keeping track of a "global section" from all the tiles. This turns out to work remarkably well for the turtle.
Geometric Deep Learning
We have reduced tiling to its combinatorics, though the markings do retain a geometric flavor, one might say. Where does deep learning come in? As we have seen, the (naive) tiling algorithm for the turtle is greatly accelerated when we enforce the matching rules with straight line markings, which incidentally were identified by human intelligence. It seems natural (and perfectly set up) for a simple machine learning algorithm to learn the markings on this and other tiles, from enough (or even a complete set of) positive and negative samples of local patches. The presence of group action may remind one of equivariant neural networks, sometimes branded as geometric deep learning.
Another component, more of a reinforcement learning nature, may be necessary for a full resolution of the tiling problem. It shall attempt to learn or recognize "patches" or "clusters" of tiles that may themselves have markings on them, giving rise to periodic tilings or hierarchical structure of aperiodic tilings. It may not be out of place to note that Wang's original papers were titled Proving Theorems by Pattern Recognition I & II.