Wang World

Wang Tiles Encyclopedia · Article 1 of 10

Wang Tiles: A Short History of Local Rules and Infinite Patterns

How four colored edges led from a decision problem to aperiodic order, symbolic dynamics, and a durable language for puzzles and computation.

A Wang tile has a color on each directed edge. Tiles may be translated, but classical Wang tiles are not rotated or reflected.
A Wang tile has a color on each directed edge. Tiles may be translated, but classical Wang tiles are not rotated or reflected.

A Wang tile is a unit square whose four edges carry colors or symbols. Copies are placed on the integer grid so that every shared edge has the same color on both sides. The definition is almost austere: no overlaps, normally no rotations, and no long-range rule. Yet those local equalities can control the structure of an entire infinite plane.

From logic to the domino problem

Hao Wang introduced the tiles in 1961 while studying whether logical reasoning could be mechanized. The associated domino problem asks whether a finite set of tile types can cover the whole plane. Wang described a procedure that would work if every tile set capable of tiling also admitted a periodic tiling. That periodicity conjecture was the vulnerable point.

Robert Berger, Wang’s student, proved the domino problem undecidable. His 1964 thesis, published as an AMS memoir in 1966, encoded computation in matching rules and produced the first aperiodic Wang set: a finite collection that tiles the plane, but never periodically. Berger’s original construction was enormous—20,426 tiles in the published reduction—but its purpose was foundational rather than recreational.

The search for smaller aperiodic sets

Subsequent constructions made aperiodicity visible rather than merely possible. Raphael Robinson reduced the number of Wang tiles and developed related six-tile shapes. Karel Culik II published an aperiodic set of 13 Wang tiles in 1996. In 2015 Emmanuel Jeandel and Michael Rao announced an aperiodic set of 11 tiles and proved by exhaustive methods that no aperiodic Wang set with ten or fewer tiles exists. Eleven is therefore the current minimum for unrestricted Wang tiles.

Local rule, global consequence. A tile checks only four neighbors. Aperiodicity emerges because those checks force structures at arbitrarily large scales.

Conventions and terminology

Authors write a tile as a four-tuple, but tuple order varies. This encyclopedia uses top, right, bottom, left. Colors are abstract labels: red and blue on screen could just as well be 0 and 1 in a proof. A protoset is the finite catalog of allowed tile types; a tiling is an assignment of copies to positions.

Traditional theory assumes unlimited copies and fixed orientation. Puzzle software may add finite inventories, rotation, boundary identifications, holes, walls, or linked positions. Those are useful extensions, but they should be stated explicitly because they alter both solving strategy and mathematical behavior. Continue with Wang tile puzzles, or go directly to aperiodicity.

Sources and further reading

  1. Hao Wang, “Proving Theorems by Pattern Recognition II,” Bell System Technical Journal 40 (1961), doi:10.1002/j.1538-7305.1961.tb03975.x.
  2. Robert Berger, The Undecidability of the Domino Problem, Memoirs of the AMS 66 (1966), doi:10.1090/memo/0066.
  3. Karel Culik II, “An Aperiodic Set of 13 Wang Tiles,” Discrete Mathematics 160 (1996), doi:10.1016/S0012-365X(96)00118-5.
  4. Emmanuel Jeandel and Michael Rao, “An aperiodic set of 11 Wang tiles,” arXiv:1506.06492.