Introduction

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.

Try Tiling

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">Each square has a color on every edge (T/R/B/L). Click a cell to cycle through tiles. Adjacent tiles <b>must match</b> at shared edges. Fill the grid — notice: you can always finish a finite grid, but for an <em>infinite</em> plane no algorithm can guarantee it for every tile set.</p>
<div id="grid"></div>
<div class="status" id="status">Click cells to place tiles.</div>
<div class="btns">
  <button id="check">Check edges</button>
  <button id="solve">Auto-fill</button>
  <button id="reset" class="ghost">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; }
/* triangle wedges for each edge */
.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); }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Wang tiles: each tile = [Top, Right, Bottom, Left] color index.
// Colors: 0=red 1=blue 2=green 3=yellow
// This is a simplified 6-tile set inspired by Robinson's reduction of Berger's set.
const COLORS = ['#e63946','#457b9d','#2a9d4a','#e9c46a'];
const CNAMES = ['Red','Blue','Green','Yellow'];

// 6 tiles: [T, R, B, L]
const TILES = [
  [0,1,2,3],  // 0: R/B/G/Y
  [2,0,1,3],  // 1: G/R/B/Y
  [1,2,3,0],  // 2: B/G/Y/R
  [3,1,0,2],  // 3: Y/B/R/G
  [0,3,2,1],  // 4: R/Y/G/B
  [2,3,1,0],  // 5: G/Y/B/R
];
const ROWS = 5, COLS = 5;
let grid = Array.from({length: ROWS}, () => Array(COLS).fill(-1));

function tileAt(r,c){ return grid[r][c]; }
function edgesMatch(r,c){
  const t = tileAt(r,c); if(t<0) return true;
  const [T,R,B,L] = TILES[t];
  if(r>0){ const n=tileAt(r-1,c); if(n>=0 && TILES[n][2]!==T) return false; }
  if(c<COLS-1){ const n=tileAt(r,c+1); if(n>=0 && TILES[n][3]!==R) return false; }
  if(r<ROWS-1){ const n=tileAt(r+1,c); if(n>=0 && TILES[n][0]!==B) return false; }
  if(c>0){ const n=tileAt(r,c-1); if(n>=0 && TILES[n][1]!==L) return false; }
  return true;
}

function makeWedge(side, colorIdx){
  const d = document.createElement('div');
  d.className = 'wedge wedge-'+side;
  d.style['border-'+({T:'top',R:'right',B:'bottom',L:'left'}[side])+'-color'] = COLORS[colorIdx];
  return d;
}

function renderCell(r,c){
  const cell = document.getElementById('cell-'+r+'-'+c);
  cell.innerHTML = '';
  const t = tileAt(r,c);
  if(t<0){ cell.className='cell empty'; return; }
  const [T,R,B,L] = TILES[t];
  cell.className = 'cell';
  cell.appendChild(makeWedge('T',T));
  cell.appendChild(makeWedge('R',R));
  cell.appendChild(makeWedge('B',B));
  cell.appendChild(makeWedge('L',L));
  const idx = document.createElement('span');
  idx.className='cell-idx'; idx.textContent=t;
  cell.appendChild(idx);
}

function render(){
  for(let r=0;r<ROWS;r++) for(let c=0;c<COLS;c++) renderCell(r,c);
}

function buildGrid(){
  const g = document.getElementById('grid'); g.innerHTML='';
  for(let r=0;r<ROWS;r++) for(let c=0;c<COLS;c++){
    const cell=document.createElement('div');
    cell.className='cell empty'; cell.id='cell-'+r+'-'+c;
    cell.addEventListener('click',()=>{
      // cycle: -1 → 0 → 1 → ... → 5 → -1
      grid[r][c] = (grid[r][c]+2) % (TILES.length+1) - 1;
      renderCell(r,c);
      setStatus('Click cells to place tiles.','');
    });
    g.appendChild(cell);
  }
}

function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function checkAll(){
  let bad=0, filled=0;
  for(let r=0;r<ROWS;r++) for(let c=0;c<COLS;c++){
    const cell=document.getElementById('cell-'+r+'-'+c);
    const t=tileAt(r,c);
    if(t>=0){ filled++;
      if(!edgesMatch(r,c)){ cell.classList.add('error'); cell.classList.remove('ok'); bad++; }
      else { cell.classList.remove('error'); cell.classList.add('ok'); }
    } else { cell.classList.remove('error','ok'); }
  }
  if(filled===0) setStatus('Place some tiles first.','');
  else if(bad>0) setStatus(fmt('✗  %bad% edge mismatch%v%. Edges must share the same color.', { bad: bad, v: bad>1?'es':'' }),'bad');
  else if(filled===ROWS*COLS) setStatus(fmt('✓  All %filled% tiles placed with matching edges! Notice: this is just a 5×5 patch — the infinite case is undecidable.', { filled: filled }),'ok');
  else setStatus(fmt('✓  No mismatches so far (%filled%/%v% tiles placed).', { filled: filled, v: ROWS*COLS }),'ok');
}

// Backtracking solver for the finite grid
function solve(){
  const flat = [];
  for(let r=0;r<ROWS;r++) for(let c=0;c<COLS;c++) flat.push([r,c]);
  grid = Array.from({length:ROWS},()=>Array(COLS).fill(-1));
  let steps = 0;
  function bt(i){
    if(i===flat.length) return true;
    const [r,c]=flat[i];
    for(let t=0;t<TILES.length;t++){
      steps++;
      grid[r][c]=t;
      if(edgesMatch(r,c) && bt(i+1)) return true;
    }
    grid[r][c]=-1; return false;
  }
  const ok=bt(0);
  render();
  if(ok) setStatus(fmt('✓  Auto-filled in %steps% steps. For an infinite grid, no algorithm can always find — or rule out — a solution.', { steps: steps }),'ok');
  else setStatus('No valid tiling found (this set always has one — try a larger count!','bad');
}

document.getElementById('check').addEventListener('click', checkAll);
document.getElementById('solve').addEventListener('click', solve);
document.getElementById('reset').addEventListener('click',()=>{
  grid = Array.from({length:ROWS},()=>Array(COLS).fill(-1));
  render();
  for(let r=0;r<ROWS;r++) for(let c=0;c<COLS;c++)
    document.getElementById('cell-'+r+'-'+c).classList.remove('error','ok');
  setStatus('Click cells to place tiles.','');
});

// Build legend
const leg=document.getElementById('legend');
leg.innerHTML='<b>Colors:</b> ';
CNAMES.forEach((n,i)=>{
  const s=document.createElement('span');
  s.innerHTML='<span class="swatch" style="background:'+COLORS[i]+'"></span>'+n+' ';
  leg.appendChild(s);
});
leg.innerHTML += ' &nbsp; <b>Tile index shown bottom-right of each cell.</b>';

buildGrid();
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/wang-tiles/Content licensed under CC BY-NC 4.0.