# What is dancing links?

> Dancing links removes and restores nodes in doubly linked lists so backtracking can undo work instantly. How it powers Algorithm X for exact cover.

**Dancing links**: Dancing links is a technique for backtracking in which nodes are removed from doubly linked lists and later restored from their own stale pointers, used by Knuth's Algorithm X to solve exact cover problems.

**Dancing links** (often called DLX) is the observation that if you remove node x from a doubly linked list with `L[R[x]] = L[x]` and `R[L[x]] = R[x]`, but leave x's own pointers alone, you can put it back later with `L[R[x]] = x` and `R[L[x]] = x`. Backtracking search can then undo every step instantly. Knuth named it and made it the engine of **Algorithm X** for [exact cover](https://cracked.guide/glossary/exact-cover).

## Why it matters

A backtracking search spends most of its time trying a choice, recursing, and undoing the choice. If the data structure can be undone in constant time without copying, the search stays fast. In Algorithm X, the items to cover are a doubly linked list of headers, each with a vertical list of the options that cover it. Choosing an option removes every conflicting option from every list; backtracking puts them back, in exactly reverse order.

## What it solves

Anything you can phrase as exact cover: sudoku, pentomino and polycube packing, N-queens, word puzzles and scheduling. Knuth extends it with secondary items, colors (XCC) and multiplicities (MCC) in Volume 4B, §7.2.2.1. On the path that section takes three weeks: [part 1](https://cracked.guide/guide/knuth-w119-0), [part 2](https://cracked.guide/guide/knuth-w120-0) and [part 3](https://cracked.guide/guide/knuth-w121-0). His annual Christmas lectures on dancing links are free on YouTube and a good warm-up.

## Questions

### Who invented dancing links?

The link-removal trick predates Knuth (he credits Hitotumatu and Noshita, 1979), but Knuth named it "dancing links", popularized it in a 2000 paper and built Algorithm X around it.

### Is DLX the fastest sudoku solver?

It solves any sudoku in a blink and is easy to get right, but hand-tuned constraint solvers can be faster. Its strength is that one program handles every exact cover puzzle.

---

Source: https://cracked.guide/glossary/dancing-links
cracked.guide: A free, dated 145-week path to getting genuinely cracked at programming.