Wang Tiles

In 1961, logician Hao Wang proposed a deceptively simple puzzle: take square tiles whose four edges are each painted a color. Place them on an infinite grid, edge-to-edge, without rotating or flipping. The one rule: adjacent edges must share the same color. Can a given collection of tiles tile the entire infinite plane?

Wang believed the answer was always decidable — that you could always either find a tiling or prove none existed by inspecting a finite patch first. He was wrong. In 1966, Robert Berger proved that the tiling problem is undecidable: no algorithm can examine a set of Wang tiles and guarantee a correct answer for all inputs. And the proof came with a twist — Berger built a set of 20,426 tiles that tiles the plane, but only aperiodically: the pattern never repeats with a translational period.

Wang tiles hide a peculiar depth. The rules are as simple as a child's matching game, yet they reach all the way to the halting problem and the boundary of what mathematics can decide.

Below is a small set of Wang tiles — each square has one color on each edge (top, right, bottom, left). Click a cell on the grid to cycle through the available tiles and place one. Adjacent placed tiles must match at every shared edge. Try to fill the whole grid without a mismatch.

<p class="hint">{{hint}}</p>
<div id="grid"></div>
<div class="status" id="status">{{click_to_place}}</div>
<div class="btns">
  <button id="check">{{btn_check}}</button>
  <button id="solve">{{btn_solve}}</button>
  <button id="reset" class="ghost">{{btn_clear}}</button>
</div>
<div class="legend" id="legend"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#grid { display: grid; grid-template-columns: repeat(5, 58px); gap: 3px; margin: .4rem 0; }
.cell {
  width: 58px; height: 58px; position: relative; cursor: pointer;
  border-radius: 4px; border: 2px solid #b0b8c4; background: #f0f3f6;
  transition: border-color .15s;
}
.cell.error { border-color: #e63946 !important; border-width: 3px; }
.cell.ok    { border-color: #2a9d4a; border-width: 2px; }
.cell.empty { background: #e6eaee; }
/* {{c_wedges}} */
.wedge {
  position: absolute; width: 0; height: 0;
  pointer-events: none;
}
.wedge-T { top:0; left:50%; transform:translateX(-50%);
           border-left: 11px solid transparent;
           border-right: 11px solid transparent;
           border-top: 14px solid; }
.wedge-R { top:50%; right:0; transform:translateY(-50%);
           border-top: 11px solid transparent;
           border-bottom: 11px solid transparent;
           border-right: 14px solid; }
.wedge-B { bottom:0; left:50%; transform:translateX(-50%);
           border-left: 11px solid transparent;
           border-right: 11px solid transparent;
           border-bottom: 14px solid; }
.wedge-L { top:50%; left:0; transform:translateY(-50%);
           border-top: 11px solid transparent;
           border-bottom: 11px solid transparent;
           border-left: 14px solid; }
.cell-idx {
  position: absolute; bottom: 2px; right: 4px;
  font: 600 10px monospace; color: rgba(0,0,0,.35);
}
.status { font-size: .95rem; font-weight: 600; margin: .45rem 0; min-height: 1.4em; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.legend { display: flex; gap: 8px; flex-wrap: wrap; align-items: center; font-size: .82rem; color: #555; }
.legend b { margin-right: 2px; }
.swatch { display: inline-block; width: 14px; height: 14px; border-radius: 3px;
          vertical-align: middle; margin-right: 3px; border: 1px solid rgba(0,0,0,.15); }

// Code not found

Notice how the matching constraint propagates: once you place a tile in the top-left corner, your neighbors are forced, which force their neighbors. In a finite grid you can always backtrack and find a solution — or prove none exists. But on an infinite grid, no algorithm can make that promise for every possible tile set. The demo uses Berger's smallest known aperiodic tile set (a simplified 6-tile version) — fill it completely and you will never find a regularly repeating pattern, no matter how large you draw the grid.

How hard is the Wang tiling problem, really?

• Checking a finite patch is trivial: compare every shared edge in the grid and flag a mismatch.
• Finite grids are decidable: with a finite set of tiles and a finite grid, you can enumerate placements by brute force.
• The infinite plane is undecidable. Berger's 1966 proof reduced the halting problem to tiling: he encoded Turing machine transitions as Wang tile matching rules so that the machine halts if and only if the tiles cannot tile the plane. Since halting is undecidable, so is tiling.
• Every aperiodic tiler is a Turing machine in disguise. If any finite tile set tiles the plane at all, Berger showed it must tile it aperiodically — the pattern must be complex enough to simulate computation.
• Robinson (1971) and Penrose (1974) later found small, elegant aperiodic sets: Robinson reduced Berger's 20,426 tiles to just 6 tiles; Penrose found non-square shapes with just 2 that tile aperiodically.

The undecidability is proven, not just believed hard. This is not like P vs NP where we suspect hardness — Berger's diagonal argument guarantees that no algorithm exists, period. Wang tiles sit one step past NP-complete: they are outside the realm of any Turing-computable decision procedure.

A puzzle about colored squares might seem abstract, but Wang tiles surface in surprising places:

• Quasicrystals: materials that diffract X-rays like crystals but lack a repeating period. Their atomic structure follows aperiodic tiling rules — physically, Wang-tile logic baked into matter. The 2011 Nobel Prize in Chemistry recognized quasicrystals discovered by Dan Shechtman.
• Texture synthesis: computer graphics algorithms use Wang tile sets to generate seamless, non-repeating textures at near-zero memory cost. A small tile set replaces gigabytes of random texture maps.
• Distributed computing lower bounds: researchers encode Wang tiling into local constraint problems to prove that no local algorithm can solve certain symmetry-breaking tasks on infinite grids.
• Mathematical logic: Wang's original goal was to understand the decidability of logical theories. Tiling became a canonical example of a problem that is co-recursively enumerable — you can always eventually detect a failure, but cannot confirm success.
• Recreational mathematics: finding the smallest tile set that forces aperiodicity is still an active research question. The single-tile "einstein" solution was found in 2023 by David Smith et al., proving one tile suffices if the shape is non-square.

Wang tiles are a reminder that undecidability is not a curiosity of abstract logic — it shows up wherever local rules must produce global order across an infinite domain.

Wang tiles are proof that undecidability is not locked inside abstract logic machines — it lives in colored squares on a grid. The matching rule is a child's game; the consequence is that no algorithm can ever decide, for every possible tile set, whether an infinite tiling exists.

The key insight is the link between local rules and global computation: forcing edges to match propagates enough information to simulate any Turing machine, and that is exactly what makes the problem undecidable. The same link appears in physics (quasicrystals), graphics (texture synthesis), and distributed systems.

Next time you see a non-repeating mosaic and wonder if you could ever be sure it tiles forever — you are asking an undecidable question, and that is not a gap in your knowledge. It is a proven limit of mathematics itself. See also the halting problem for the computation-theoretic root of this undecidability.