Topic · Computation

Wang Tiles

Squares with coloured edges that quietly carry any computation.

Hao Wang's 1961 puzzle — match the colours on touching edges — turned out to hide the halting problem inside a children's matching game. Below: the rules, the surprise, and two interactives that let you place tiles by hand and watch an aperiodic patch grow.

Discover the story → Open the Explorer

First encounter

Match the edges. That's the whole game.

The big idea

Take a square. Paint each of its four edges a colour. That's a Wang tile. Place several side by side, but only where the edges that touch share a colour — north against south, east against west, with no rotations allowed. From that one rule, in a way nobody saw coming in 1961, you can encode any computation a machine can do.

A concrete example

Three tiles, two edge colours. The bottom row is two copies of tile A; the top row is two copies of tile B. A's east edge matches A's west; B's east matches B's west; and A's north matches B's south. One small patch, and you have already discovered that some tile sets click together and others can't.

valid 2×2

Why it matters

In 1966 Robert Berger proved that no algorithm can decide, in general, whether a given Wang tile set tiles the plane. To do it he built a set of 20,426 tiles that tile only aperiodically — no translation of the pattern ever maps it back to itself. The line of work that followed shrank that record from 20,426 to 13 (Culik, 1996) to 11 (Jeandel–Rao, 2015) and lit the path to Penrose tilings and the modern aperiodic monotile.

Below: place tiles yourself so every shared edge matches, then watch a backtracking search fill a region with a demo set built in the spirit of the Culik and Jeandel-Rao records.

Section 01 · Wang's question

Can you decide if a tile set tiles the plane?

In 1961 the logician Hao Wang asked a deceptively concrete question: given a finite set of square tiles with coloured edges, is there an algorithm that decides whether copies of them (no rotations, no reflections) can be assembled into a tiling of the entire infinite plane? Wang's own conjecture said yes — and stronger, he believed every tile set that tiles the plane must admit some periodic tiling, a pattern that repeats by translation. If that were true, a finite check would settle the Domino Problem once and for all. The plane would yield to a finite calculation.

Section 02 · Berger's theorem

Undecidable. And aperiodic tile sets exist.

In 1966, Wang's student Robert Berger destroyed both halves of the conjecture in one stroke. He constructed a set of 20,426 Wang tiles that does tile the plane — but only aperiodically. No translation of any tiling using that set ever maps it back to itself. And he proved the Domino Problem is undecidable: no algorithm, no clever finite check, will tell you in general whether a tile set tiles the plane at all. A finite list of squares with coloured edges can be Turing-complete in disguise.

Berger · 1966

Domino Problem ∈ undecidable

No algorithm decides, in general, whether a finite Wang tile set tiles the plane. The proof reduces the halting problem to a tiling question.

Interactive · place tiles, edges must match

0 placed · 0 valid

Palette · 8 tiles

Click a cell to cycle through eight tiles; click again past the last one to clear it. A red ring marks a tile whose edge disagrees with a neighbour. Try to fill the 3×3 with every shared edge matching — some configurations have many solutions, others none.

Section 03 · Encoding computation

Turing machines, painted onto edges

Berger's construction is a translation: take any Turing machine and produce a Wang tile set that tiles the upper half-plane if and only if the machine never halts on its blank input. Each row of tiles spells out one full machine configuration — the tape contents and the head position — and each row-to-row transition is forced by edge-matching to be exactly one step of the machine. The infinite tiling, if it exists, is the infinite computation. Asking «does this tile set tile?» becomes «does this machine run forever?» — and the latter is the halting problem, the oldest undecidable problem we know.

Section 04 · From 20,426 to 11

Robinson, Culik, Jeandel–Rao

Berger's 20,426 tiles were a proof, not a sculpture. The decades that followed were a hunt for the smallest aperiodic Wang set. Raphael Robinson got it down to 56 in 1971 with a cleaner hierarchical construction. In 1996 Jarkko Kari published 14, then Karel Culik II, building directly on Kari's ideas, found 13 the same year — a record that stood for nearly two decades. In 2015 Emmanuel Jeandel and Michaël Rao proved by exhaustive computer search that 11 is the true minimum: there is an aperiodic set of 11 Wang tiles, and no set of 10 or fewer can be aperiodic. The story has a finite answer, and it is 11.

Shrinking the aperiodic record

Year	Author	Tiles
1961	Hao Wang: conjecture, no such set exists	n/a
1966	Robert Berger: first aperiodic set	20,426
1971	Raphael Robinson	56
1996	Jarkko Kari	14
1996	Karel Culik II	13
2015	Jeandel & Rao: proven minimum	11

Interactive · grow an aperiodic patch

Tile set

in the spirit of Culik 1996

A randomised backtracking search fills the canvas, cell by cell, with tiles from the chosen set. These are illustrative demo sets in the spirit of the Culik and Jeandel-Rao records, not the exact published tables, so read the growing patch as a feel for how edge-matching search behaves rather than a proof of aperiodicity.

seed · 00c0ffee

Section 05 · Quasicrystals

Penrose, Shechtman, and patterns that refuse to repeat

In 1974 Roger Penrose published his first aperiodic tiling, a set of six tiles, which he soon refined down to just two rhombi, a kinder, more geometric cousin of Berger's monsters. In 1982 Dan Shechtman observed sharp diffraction patterns with five-fold symmetry in a rapidly cooled aluminium-manganese alloy (he published the result in 1984), something physically forbidden for any periodic crystal. The structure he had found was a quasicrystal: matter arranged in an aperiodic pattern. Wang tiles had been the conceptual ancestor of both. A combinatorial game about coloured edges turned out to describe a phase of matter that won Shechtman the 2011 Nobel Prize in Chemistry.

Section 06 · The aperiodic monotile

2023 — one tile is enough

For more than half a century the open question was whether a single tile could force aperiodicity — an «einstein», from German ein Stein, one stone. In March 2023, David Smith, Joseph Myers, Craig Kaplan, and Chaim Goodman-Strauss announced the hat: a 13-sided polygon that tiles the plane only aperiodically, using reflections. Two months later the same team produced the spectre, an aperiodic monotile that needs no reflections. The chain that started with Wang's 1961 conjecture — through Berger's 20,426, Robinson's 56, Culik's 13, Jeandel–Rao's 11 — terminates, six decades later, at 1.

Smith · Myers · Kaplan · Goodman-Strauss · 2023

ein Stein · 1

The «hat» (March 2023) tiles only aperiodically, using reflections. The «spectre» (May 2023) removes even that requirement.

→ Open the Explorer

Place a tile. The plane decides.

The Explorer lets you switch between an explicitly periodic set and aperiodic-style ones, and watch the algorithm backtrack live when it paints itself into a corner. Everything you just read is one click away.

→ Open the Explorer

Where you meet it

How and where this technique lives in the world today.

Real-time graphics

Wang tilesets are used to pack non-repeating textures (grass, brick, sand) into tiny texture atlases — important on memory-constrained devices like mobile GPUs.

Procedural level design

Game engines (Houdini, custom roguelike engines) use Wang tiles to assemble large dungeon/world maps from small modular building blocks without visible seams.

Materials & quasicrystals

Wang tile theory partially overlaps with quasicrystal mathematics — both produce aperiodic infinite arrangements.