Dancing Links: Solve a Pentomino Tiling

Introduction

Exact cover is a deceptively simple question: given a universe of items and a collection of sets, can you choose a sub-collection such that every item appears in exactly one chosen set? No gaps, no overlaps — perfect coverage.

The puzzle appears everywhere. Can twelve pentomino pieces tile a 6×10 rectangle with no overlap? Can 81 Sudoku cells be filled so each digit covers each row, column, and box exactly once? Both reduce to exact cover, and exact cover is NP-complete.

In 2000, Donald Knuth published "Dancing Links" — a paper that shows how to solve exact-cover problems with breathtaking efficiency. The key insight is not an algorithmic trick but a data-structure one: represent the constraint matrix as a doubly-linked toroidal list, then implement backtracking by unlinking and relinking nodes. When a search branch fails and you need to undo, deleted nodes dance back into place — each node still knows its old neighbors even while removed, so restoration is O(1) per node.

Try It: Pentomino Tiler

The board below is a 4×5 grid (20 cells). We use four of the twelve standard pentominoes — L, P, N, U — each covering exactly 5 cells (4 × 5 = 20 total), with no overlap and no gap. Fitting them perfectly is an exact-cover problem.

<p class="hint">A 4×5 grid (20 cells) tiled by four pentominoes: <b>L, P, N, U</b>.
    Each piece covers exactly 5 cells — 4 × 5 = 20. No overlaps, no gaps.
    DLX picks the cell covered by the fewest placements (S heuristic), tries each,
    and backtracks on failure — pointer unlinks and relinks in O(1).</p>
<div id="grid"></div>
<div class="info-row">
  <span class="label">Placements tried: <b id="steps">0</b></span>
  <span id="msg" class="label bold">Press Step or Solve.</span>
</div>
<div class="btns">
  <button id="btn-step">Step</button>
  <button id="btn-solve">Solve</button>
  <button id="btn-reset" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#grid { display: grid; grid-template-columns: repeat(5, 46px); gap: 3px; margin: .4rem 0; }
.cell { width: 46px; height: 46px; border-radius: 7px; border: 1px solid #bcc5ce;
        background: #e8eef3; transition: background .15s; display: flex;
        align-items: center; justify-content: center;
        font: 700 14px ui-monospace, monospace; color: rgba(0,0,0,.4); }
.c-L { background: #e63946; color: #fff; border-color: #c92f3c; }
.c-P { background: #2a9d8f; color: #fff; border-color: #1f7d71; }
.c-N { background: #e9c46a; color: #555; border-color: #c9a450; }
.c-U { background: #a8dadc; color: #1d3557; border-color: #80bdbf; }
.info-row { display: flex; gap: 1rem; align-items: center; font-size: .9rem;
            margin: .35rem 0; flex-wrap: wrap; }
.label { color: #444; }
.bold { font-weight: 600; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .3rem; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Dancing Links (DLX) – pentomino exact-cover demo
// Board: 4 rows × 5 cols = 20 cells.
// Pieces: L, P, N, U (each 5 cells → 4 × 5 = 20 = exact fit).
//
// Exact-cover formulation:
//   Columns 0-19 → board cells (each must be covered exactly once)
//   Rows         → one per (piece, orientation, anchor) triple
//
// Algorithm X with S heuristic: always pick the column (cell) covered by the
// fewest placements to minimise branching. Real DLX does cover/uncover in O(1)
// via doubly-linked list pointer rewrites; here we use Sets for readability.

const ROWS = 4, COLS = 5, NCELLS = 20;

// Canonical piece shapes as (row, col) offsets from top-left anchor.
const PIECE_DEF = {
  L: [[0,0],[1,0],[2,0],[3,0],[3,1]],   // vertical bar + foot right
  P: [[0,0],[0,1],[1,0],[1,1],[2,0]],   // 2×2 block + tail below-left
  N: [[0,0],[1,0],[1,1],[2,1],[3,1]],   // S-zigzag
  U: [[0,0],[0,2],[1,0],[1,1],[1,2]]    // U shape (open top-middle)
};
const PIECE_NAMES = ['L','P','N','U'];

function rotCW(cells)  { return cells.map(([r,c]) => [c, -r]); }
function flipH(cells)  { return cells.map(([r,c]) => [-r, c]); }
function normalise(cells) {
  const minR = Math.min(...cells.map(x => x[0]));
  const minC = Math.min(...cells.map(x => x[1]));
  return cells.map(([r,c]) => [r-minR, c-minC])
              .sort((a, b) => a[0]-b[0] || a[1]-b[1]);
}
function orientations(cells) {
  const seen = new Set(), out = [];
  for (const base of [cells, flipH(cells)]) {
    let cur = base;
    for (let i = 0; i < 4; i++) {
      const norm = normalise(cur);
      const key  = norm.map(x => x.join(',')).join('|');
      if (!seen.has(key)) { seen.add(key); out.push(norm); }
      cur = rotCW(cur);
    }
  }
  return out;
}

// Build the full placement table (piece name + list of cell indices covered).
const ALL_PLACEMENTS = [];
for (const name of PIECE_NAMES) {
  for (const rot of orientations(PIECE_DEF[name])) {
    const maxR = Math.max(...rot.map(x => x[0]));
    const maxC = Math.max(...rot.map(x => x[1]));
    for (let ar = 0; ar + maxR < ROWS; ar++) {
      for (let ac = 0; ac + maxC < COLS; ac++) {
        const cells = rot.map(([r,c]) => (ar+r)*COLS + (ac+c));
        ALL_PLACEMENTS.push({ piece: name, cells });
      }
    }
  }
}

// --- Iterative Algorithm X state ---
let board    = new Array(NCELLS).fill(null);
let stepCount = 0;
let solved    = false;
let noSol     = false;
let stack     = [];
let initiated = false;

function initSearch() {
  board = new Array(NCELLS).fill(null);
  stepCount = 0; solved = false; noSol = false; initiated = true;
  stack = [{
    uncovered: new Set([...Array(NCELLS).keys()]),
    pieces:    new Set(PIECE_NAMES),
    chosen:    [],
    candidates: null,
    idx: 0
  }];
}

// Advance one backtracking step.
// Returns 'solved' | 'no-solution' | 'continue'.
function dlxStep() {
  if (solved) return 'solved';
  while (stack.length > 0) {
    const frame = stack[stack.length - 1];

    // Initialise this frame: pick best column (S heuristic).
    if (frame.candidates === null) {
      if (frame.uncovered.size === 0) {
        // All cells covered — we have a solution.
        solved = true;
        board = new Array(NCELLS).fill(null);
        for (const p of frame.chosen)
          for (const c of p.cells) board[c] = p.piece;
        return 'solved';
      }
      // S heuristic: pick the uncovered cell with fewest valid placements.
      let bestCol = -1, bestCount = Infinity;
      for (const col of frame.uncovered) {
        const cnt = ALL_PLACEMENTS.filter(
          p => frame.pieces.has(p.piece) && p.cells.includes(col)
        ).length;
        if (cnt < bestCount) { bestCount = cnt; bestCol = col; }
      }
      if (bestCount === 0) { stack.pop(); continue; } // dead end — backtrack
      frame.col = bestCol;
      frame.candidates = ALL_PLACEMENTS.filter(
        p => frame.pieces.has(p.piece) && p.cells.includes(bestCol)
      );
      frame.idx = 0;
    }

    // Try next candidate for this column.
    if (frame.idx >= frame.candidates.length) { stack.pop(); continue; }
    const placement = frame.candidates[frame.idx++];
    stepCount++;

    // Skip if any cell of this placement is already covered.
    if (placement.cells.some(c => !frame.uncovered.has(c))) continue;

    // Cover: remove cells and piece.
    const newU = new Set(frame.uncovered);
    for (const c of placement.cells) newU.delete(c);
    const newP = new Set(frame.pieces);
    newP.delete(placement.piece);
    const newChosen = [...frame.chosen, placement];

    // Visualise partial solution.
    board = new Array(NCELLS).fill(null);
    for (const p of newChosen) for (const c of p.cells) board[c] = p.piece;

    // Push child frame (uncover happens automatically on backtrack via pop).
    stack.push({
      uncovered: newU,
      pieces:    newP,
      chosen:    newChosen,
      candidates: null,
      idx: 0
    });
    return 'continue';
  }
  noSol = true;
  return 'no-solution';
}

// --- UI ---
function render() {
  const g = document.getElementById('grid'); g.innerHTML = '';
  for (let i = 0; i < NCELLS; i++) {
    const d = document.createElement('div');
    const p = board[i];
    d.className = 'cell' + (p ? ' c-'+p : '');
    d.textContent = p || '';
    g.appendChild(d);
  }
}
function setMsg(t)  { document.getElementById('msg').textContent = t; }
function setSteps() { document.getElementById('steps').textContent = stepCount; }
function setButtons(busy) {
  document.getElementById('btn-step').disabled  = busy || solved || noSol;
  document.getElementById('btn-solve').disabled = busy || solved || noSol;
}

document.getElementById('btn-step').addEventListener('click', () => {
  if (!initiated) initSearch();
  const r = dlxStep();
  render(); setSteps();
  if (r === 'solved')       { setMsg('Solved! All 4 pieces fit perfectly.'); setButtons(false); }
  else if (r === 'no-solution') { setMsg('No solution exists.'); setButtons(false); }
  else setMsg(fmt('Searching… (step %stepCount%)', { stepCount: stepCount }));
});

document.getElementById('btn-solve').addEventListener('click', () => {
  if (!initiated) initSearch();
  setButtons(true);
  let r = 'continue';
  while (r === 'continue') r = dlxStep();
  render(); setSteps();
  if (r === 'solved') setMsg('Solved! All 4 pieces fit perfectly.');
  else setMsg('No solution exists.');
  setButtons(false);
});

document.getElementById('btn-reset').addEventListener('click', () => {
  initiated = false; solved = false; noSol = false;
  board = new Array(NCELLS).fill(null);
  stepCount = 0; stack = [];
  render(); setSteps(); setMsg('Press Step or Solve.');
  document.getElementById('btn-step').disabled  = false;
  document.getElementById('btn-solve').disabled = false;
});

render();

<p class="hint">A 4×5 grid (20 cells) tiled by four pentominoes: <b>L, P, N, U</b>.
    Each piece covers exactly 5 cells — 4 × 5 = 20. No overlaps, no gaps.
    DLX picks the cell covered by the fewest placements (S heuristic), tries each,
    and backtracks on failure — pointer unlinks and relinks in O(1).</p>
<div id="grid"></div>
<div class="info-row">
  <span class="label">Placements tried: <b id="steps">0</b></span>
  <span id="msg" class="label bold">Press Step or Solve.</span>
</div>
<div class="btns">
  <button id="btn-step">Step</button>
  <button id="btn-solve">Solve</button>
  <button id="btn-reset" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#grid { display: grid; grid-template-columns: repeat(5, 46px); gap: 3px; margin: .4rem 0; }
.cell { width: 46px; height: 46px; border-radius: 7px; border: 1px solid #bcc5ce;
        background: #e8eef3; transition: background .15s; display: flex;
        align-items: center; justify-content: center;
        font: 700 14px ui-monospace, monospace; color: rgba(0,0,0,.4); }
.c-L { background: #e63946; color: #fff; border-color: #c92f3c; }
.c-P { background: #2a9d8f; color: #fff; border-color: #1f7d71; }
.c-N { background: #e9c46a; color: #555; border-color: #c9a450; }
.c-U { background: #a8dadc; color: #1d3557; border-color: #80bdbf; }
.info-row { display: flex; gap: 1rem; align-items: center; font-size: .9rem;
            margin: .35rem 0; flex-wrap: wrap; }
.label { color: #444; }
.bold { font-weight: 600; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .3rem; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Dancing Links (DLX) – pentomino exact-cover demo
// Board: 4 rows × 5 cols = 20 cells.
// Pieces: L, P, N, U (each 5 cells → 4 × 5 = 20 = exact fit).
//
// Exact-cover formulation:
//   Columns 0-19 → board cells (each must be covered exactly once)
//   Rows         → one per (piece, orientation, anchor) triple
//
// Algorithm X with S heuristic: always pick the column (cell) covered by the
// fewest placements to minimise branching. Real DLX does cover/uncover in O(1)
// via doubly-linked list pointer rewrites; here we use Sets for readability.

const ROWS = 4, COLS = 5, NCELLS = 20;

// Canonical piece shapes as (row, col) offsets from top-left anchor.
const PIECE_DEF = {
  L: [[0,0],[1,0],[2,0],[3,0],[3,1]],   // vertical bar + foot right
  P: [[0,0],[0,1],[1,0],[1,1],[2,0]],   // 2×2 block + tail below-left
  N: [[0,0],[1,0],[1,1],[2,1],[3,1]],   // S-zigzag
  U: [[0,0],[0,2],[1,0],[1,1],[1,2]]    // U shape (open top-middle)
};
const PIECE_NAMES = ['L','P','N','U'];

function rotCW(cells)  { return cells.map(([r,c]) => [c, -r]); }
function flipH(cells)  { return cells.map(([r,c]) => [-r, c]); }
function normalise(cells) {
  const minR = Math.min(...cells.map(x => x[0]));
  const minC = Math.min(...cells.map(x => x[1]));
  return cells.map(([r,c]) => [r-minR, c-minC])
              .sort((a, b) => a[0]-b[0] || a[1]-b[1]);
}
function orientations(cells) {
  const seen = new Set(), out = [];
  for (const base of [cells, flipH(cells)]) {
    let cur = base;
    for (let i = 0; i < 4; i++) {
      const norm = normalise(cur);
      const key  = norm.map(x => x.join(',')).join('|');
      if (!seen.has(key)) { seen.add(key); out.push(norm); }
      cur = rotCW(cur);
    }
  }
  return out;
}

// Build the full placement table (piece name + list of cell indices covered).
const ALL_PLACEMENTS = [];
for (const name of PIECE_NAMES) {
  for (const rot of orientations(PIECE_DEF[name])) {
    const maxR = Math.max(...rot.map(x => x[0]));
    const maxC = Math.max(...rot.map(x => x[1]));
    for (let ar = 0; ar + maxR < ROWS; ar++) {
      for (let ac = 0; ac + maxC < COLS; ac++) {
        const cells = rot.map(([r,c]) => (ar+r)*COLS + (ac+c));
        ALL_PLACEMENTS.push({ piece: name, cells });
      }
    }
  }
}

// --- Iterative Algorithm X state ---
let board    = new Array(NCELLS).fill(null);
let stepCount = 0;
let solved    = false;
let noSol     = false;
let stack     = [];
let initiated = false;

function initSearch() {
  board = new Array(NCELLS).fill(null);
  stepCount = 0; solved = false; noSol = false; initiated = true;
  stack = [{
    uncovered: new Set([...Array(NCELLS).keys()]),
    pieces:    new Set(PIECE_NAMES),
    chosen:    [],
    candidates: null,
    idx: 0
  }];
}

// Advance one backtracking step.
// Returns 'solved' | 'no-solution' | 'continue'.
function dlxStep() {
  if (solved) return 'solved';
  while (stack.length > 0) {
    const frame = stack[stack.length - 1];

    // Initialise this frame: pick best column (S heuristic).
    if (frame.candidates === null) {
      if (frame.uncovered.size === 0) {
        // All cells covered — we have a solution.
        solved = true;
        board = new Array(NCELLS).fill(null);
        for (const p of frame.chosen)
          for (const c of p.cells) board[c] = p.piece;
        return 'solved';
      }
      // S heuristic: pick the uncovered cell with fewest valid placements.
      let bestCol = -1, bestCount = Infinity;
      for (const col of frame.uncovered) {
        const cnt = ALL_PLACEMENTS.filter(
          p => frame.pieces.has(p.piece) && p.cells.includes(col)
        ).length;
        if (cnt < bestCount) { bestCount = cnt; bestCol = col; }
      }
      if (bestCount === 0) { stack.pop(); continue; } // dead end — backtrack
      frame.col = bestCol;
      frame.candidates = ALL_PLACEMENTS.filter(
        p => frame.pieces.has(p.piece) && p.cells.includes(bestCol)
      );
      frame.idx = 0;
    }

    // Try next candidate for this column.
    if (frame.idx >= frame.candidates.length) { stack.pop(); continue; }
    const placement = frame.candidates[frame.idx++];
    stepCount++;

    // Skip if any cell of this placement is already covered.
    if (placement.cells.some(c => !frame.uncovered.has(c))) continue;

    // Cover: remove cells and piece.
    const newU = new Set(frame.uncovered);
    for (const c of placement.cells) newU.delete(c);
    const newP = new Set(frame.pieces);
    newP.delete(placement.piece);
    const newChosen = [...frame.chosen, placement];

    // Visualise partial solution.
    board = new Array(NCELLS).fill(null);
    for (const p of newChosen) for (const c of p.cells) board[c] = p.piece;

    // Push child frame (uncover happens automatically on backtrack via pop).
    stack.push({
      uncovered: newU,
      pieces:    newP,
      chosen:    newChosen,
      candidates: null,
      idx: 0
    });
    return 'continue';
  }
  noSol = true;
  return 'no-solution';
}

// --- UI ---
function render() {
  const g = document.getElementById('grid'); g.innerHTML = '';
  for (let i = 0; i < NCELLS; i++) {
    const d = document.createElement('div');
    const p = board[i];
    d.className = 'cell' + (p ? ' c-'+p : '');
    d.textContent = p || '';
    g.appendChild(d);
  }
}
function setMsg(t)  { document.getElementById('msg').textContent = t; }
function setSteps() { document.getElementById('steps').textContent = stepCount; }
function setButtons(busy) {
  document.getElementById('btn-step').disabled  = busy || solved || noSol;
  document.getElementById('btn-solve').disabled = busy || solved || noSol;
}

document.getElementById('btn-step').addEventListener('click', () => {
  if (!initiated) initSearch();
  const r = dlxStep();
  render(); setSteps();
  if (r === 'solved')       { setMsg('Solved! All 4 pieces fit perfectly.'); setButtons(false); }
  else if (r === 'no-solution') { setMsg('No solution exists.'); setButtons(false); }
  else setMsg(fmt('Searching… (step %stepCount%)', { stepCount: stepCount }));
});

document.getElementById('btn-solve').addEventListener('click', () => {
  if (!initiated) initSearch();
  setButtons(true);
  let r = 'continue';
  while (r === 'continue') r = dlxStep();
  render(); setSteps();
  if (r === 'solved') setMsg('Solved! All 4 pieces fit perfectly.');
  else setMsg('No solution exists.');
  setButtons(false);
});

document.getElementById('btn-reset').addEventListener('click', () => {
  initiated = false; solved = false; noSol = false;
  board = new Array(NCELLS).fill(null);
  stepCount = 0; stack = [];
  render(); setSteps(); setMsg('Press Step or Solve.');
  document.getElementById('btn-step').disabled  = false;
  document.getElementById('btn-solve').disabled = false;
});

render();

Result

Console

Press Step to watch DLX pick the cell covered by the fewest placements (S heuristic), select a row (piece placement) that covers it, recursively solve the rest, and backtrack when stuck. Press Solve to find the complete solution at once. The counter shows how many placements DLX tried — exact cover is NP-complete, but the right data structure keeps the constant factor tiny.

The Real Complexity

Exact cover is NP-complete — proven by reduction from 3-dimensional matching. That means no polynomial-time algorithm is known, and for the worst inputs you cannot avoid exponential search. So where does DLX's speed come from?

Algorithm X (Knuth 2000) is a systematic backtracking search. At each step it picks an uncovered column (constraint), tries every row that covers it (choice), recursively solves the reduced problem, and backtracks on failure. The correctness is trivial; the cost is the branching factor times the recursion depth.
The S heuristic: always choose the column with the fewest rows covering it ("minimum remaining values"). This prunes the search tree dramatically — a column with zero options is detected immediately; one with only two options limits branching to 2.
O(1) cover/uncover: because nodes remain in memory and still hold their old left/right/up/down pointers, removing a node from a list is four pointer writes, and restoring it is four more. No heap allocation, no searching — just pointer gymnastics. This is the dancing in Dancing Links.
Empirical speed: DLX finds solutions to millions-of-cell Sudoku puzzles and pentomino tilings in milliseconds, even though the problem class is NP-complete. The pruning and cache-friendly structure make the constant factor small enough for practical use.

The takeaway: NP-completeness characterizes worst-case behaviour on adversarial inputs. Real puzzles have rich structure that branch-and-bound with a good heuristic exploits heavily.

Where It Matters

Exact cover sounds abstract, but it is the hidden shape of countless real problems:

Puzzle solving: Sudoku, pentominos, polyomino tilings, N-queens, and Latin squares all reduce naturally to exact cover — DLX solves them faster than any other general method.
Scheduling and timetabling: assign tasks to slots so each task gets exactly one slot and each slot holds exactly one task. This is exact cover. See also scheduling.
Compiler register allocation: partition live variables into register groups so each variable is in exactly one group and no two conflicting variables share a group.
DNA sequencing: shotgun assembly asks which fragments tile the genome exactly — an exact-cover formulation reduces the search space.
Set partitioning in operations research: flight crew scheduling, vehicle routing, and warehouse order batching all use variants of exact cover solved by branch-and-price algorithms that share DLX's cover/uncover logic.

Understanding DLX means understanding how to turn a combinatorial explosion into disciplined search — the same skill that powers modern SAT solvers and constraint-programming engines.

Conclusion

Dancing Links is a masterclass in a principle that never goes out of style: choose your data structure first, then the algorithm writes itself. Exact cover is NP-complete, yet DLX tears through Sudoku puzzles and pentomino tilings in milliseconds because every backtrack step costs only a handful of pointer writes.

Knuth called the paper "Dancing Links" because the nodes literally dance — removed from a list, they still remember where they belong, and they glide back the instant the algorithm backtracks. It is a rare case where the implementation detail is also the most beautiful idea.

The next time you face a problem that smells like "cover everything exactly once," reach for DLX before reaching for despair. NP-completeness is a ceiling on the worst case — not a wall against good engineering.

Comments

Loading comments...

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

Cookies & privacy

Dancing Links (DLX)

When backtracking becomes a ballet of self-relinking nodes