TAOCP 2.3.4.3 Exercise 4

Let the given finite set of tetrad types be $T$.

taocpmathematicsalgorithmsvolume-1

Section 2.3.4.3:

Exercise 4. [**] [M25] (H. Wang.) The six tetrad types (2) lead to a toroidal solution to the tiling problem, that is, a solution in which some rectangular pattern, namely (3), is replicated throughout the entire plane.

Assume without proof that whenever it is possible to tile the plane with a finite set of tetrad types, there is a toroidal solution using those tetrad types. Use this assumption together with the infinity lemma to design an algorithm that, given the specifications of any finite set of tetrad types, determines in a finite number of steps whether or not there exists a way to tile the plane with these types.

Verified: yes
Solve time: 3m22s

Let the given finite set of tetrad types be $T$.

By the hypothesis of the exercise, the plane can be tiled with $T$ if and only if there exists a toroidal solution using $T$. Thus it suffices to decide whether either a toroidal solution exists or no plane tiling exists.

Construct a rooted tree $\mathcal T$ as follows.

For each $n\ge 1$, let level $n$ consist of all admissible $n\times n$ square patterns formed from the tetrad types in $T$, where "admissible" means that every pair of neighboring edges matches correctly. Since $T$ is finite, there are only finitely many such patterns at each level.

A node $P$ at level $n$ is joined to a node $Q$ at level $n+1$ if the central $n\times n$ subpattern of $Q$ is exactly $P$. Thus each child extends its parent by one layer of cells around the boundary.

Because only finitely many tetrad types are available, each node has only finitely many children. Hence $\mathcal T$ is a finitely branching rooted tree.

Now observe:

  • If there is a tiling of the entire plane, then for every $n$ the restriction of that tiling to the square

$$ [-n,n]\times[-n,n] $$

determines an admissible finite pattern. These patterns form an infinite path in $\mathcal T$. Therefore every level of $\mathcal T$ is nonempty.

  • Conversely, suppose every level of $\mathcal T$ is nonempty. Since $\mathcal T$ is finitely branching, the infinity lemma implies that $\mathcal T$ contains an infinite path

$$ P_1,P_2,P_3,\ldots . $$

The patterns are nested by construction, so their union determines a consistent tiling of the entire plane. Hence a plane tiling exists.

Therefore

$$ \text{the plane is tileable} \quad\Longleftrightarrow\quad \text{every level of }\mathcal T\text{ is nonempty}. $$

This gives a finite certificate for nonexistence: if the plane is not tileable, then by the preceding equivalence not every level is nonempty. Hence there is some integer $N$ such that level $N$ of $\mathcal T$ is empty.

We now describe the decision procedure.

  1. Enumerate all admissible $n\times n$ patterns for $n=1,2,3,\ldots$, thereby constructing successive levels of $\mathcal T$.
  2. Simultaneously enumerate all rectangular toroidal patterns. Since the set $T$ is finite, for each pair of dimensions $m,n$ there are only finitely many candidate $m\times n$ patterns, and it is decidable whether a given one satisfies the toroidal boundary conditions.
  3. Run the two searches in parallel.
  • If a toroidal pattern is found, halt and answer YES. By the hypothesis of the exercise, the existence of a toroidal solution implies that the plane can be tiled.
  • If some level $N$ of $\mathcal T$ is found to be empty, halt and answer NO. Indeed, if a plane tiling existed, every level would be nonempty; equivalently, by the infinity lemma, an empty level implies that no infinite path and hence no plane tiling exists.

Termination is guaranteed.

  • If the plane is tileable, then by the assumed theorem there exists a toroidal solution. The toroidal search eventually finds it and answers YES.
  • If the plane is not tileable, then $\mathcal T$ cannot have all levels nonempty, for otherwise the infinity lemma would yield an infinite path and hence a plane tiling. Therefore some level is empty, and the first search eventually discovers this and answers NO.

Thus the algorithm always halts after finitely many steps and correctly decides whether the given finite set of tetrad types can tile the plane. ∎