Skip to content
Tutorials Center
My learning

Topics

Lesson 69 of 225 ยท Recursion and Backtracking

Exact Cover and Dancing Links (Algorithm X)

Solve exact cover problems with Knuth's Algorithm X and the Dancing Links data structure in Python, then use it to count N-queens solutions and solve Sudoku.

Sudoku, N-queens, tiling a board with dominoes and scheduling puzzles look unrelated, yet they share one shape. You have a set of items that must each be handled exactly once, and a list of options, each covering some items. Pick options so that every item is covered exactly once. This is the exact cover problem.

Donald Knuth's Algorithm X solves it by plain backtracking with one smart rule: always branch on the item that has the fewest options left. His Dancing Links (DLX) trick makes the undo step almost free using doubly linked lists. In this lesson you will build both, check them on a small puzzle, count N-queens solutions and solve a Sudoku. You should know backtracking, N-Queens and doubly linked lists.

The exact cover problem

Take the items 1..7 and these options (each a set of items):

TEXT
A = {1, 4, 7}    B = {1, 4}    C = {4, 5, 7}
D = {3, 5, 6}    E = {2, 3, 6, 7}    F = {2, 7}

An exact cover picks options whose sets are disjoint and together cover every item: here B + D + F works ({1,4} + {3,5,6} + {2,7}). No other choice does.

A natural picture is a matrix with a column per item and a row per option; a 1 means "this option covers this item". An exact cover is a set of rows with exactly one 1 in every column.

Algorithm X

  1. If the matrix has no columns left, you have a solution.
  2. Choose a column c, preferably the one with the fewest 1s. If it has none, this branch fails.
  3. For each row r with a 1 in column c: select r, then remove every column that r covers, and every row that conflicts (shares a column with r). Recurse. Then undo the removals.

Choosing the smallest column keeps the branching factor small, often forcing moves with only one option. A simple version represents the matrix as a dictionary from item to the set of options containing it.

Python Algorithm X with dictionaries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The domino example finds the 3 tilings of a 2 by 3 board.

Algorithm X spends most of its time removing and restoring entries. Knuth noticed a neat property of doubly linked lists: if you unlink a node x by setting x.left.right = x.right and x.right.left = x.left, the node itself still remembers its neighbors. Relinking it later needs only x.left.right = x; x.right.left = x. Undoing is as cheap as doing, and it works in reverse order perfectly. That reversible unlinking is called dancing links.

The matrix is stored as a grid of nodes. Each 1-entry is a node linked left and right to its row neighbors (circularly) and up and down to its column neighbors (circularly). Every column has a header node with a count S, and a root node links all headers.

flowchart LR
  root["root"] --- c1["item 1 (S=2)"]
  c1 --- c2["item 2 (S=2)"]
  c2 --- c3["item 3 (S=2)"]
  c1 -.-> n1["option A node"]
  n1 -.-> n2["option B node"]

Headers form a circular list through the root. Each header also owns a circular vertical list of its nodes.

Two operations do the work:

  • cover(c): unlink header c from the header list; for each row i in column c, unlink every other node of that row from its own column (and decrement that column's size).
  • uncover(c): do exactly the reverse, in the reverse order.

DLX also supports secondary items: items that may be covered at most once (no requirement to cover them). They appear in the node grid but not in the header list, so the search never branches on them. N-queens uses them for diagonals.

Python Dancing Links solver, small example and N-queens

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The class is about 70 lines and every operation is O(1) per node touched. The search is still exponential in the worst case, because exact cover is NP-complete (see NP-completeness), but the "smallest column first" rule and the cheap undo make it very fast on puzzles.

N-queens as exact cover

Place n queens on an n x n board with no two attacking each other.

  • Primary items (must be covered exactly once): each row r and each column c.
  • Secondary items (at most once): each diagonal r + c and each anti-diagonal r - c.
  • Options: one per square (r, c), covering row r, column c, diagonal r + c and anti-diagonal r - c.

An exact cover of the primary items is a placement of n queens with at most one per diagonal. The function queens_dlx at the bottom of the DLX example above builds exactly these options and counts the solutions; it prints the number of solutions for boards of size 1 to 8.

The counts 1, 0, 0, 2, 10, 4, 40, 92 are the known number of solutions of the N-queens problem.

Sudoku as exact cover

A Sudoku has four kinds of constraint, each primary and each satisfied exactly once:

  1. every cell holds exactly one digit (81 items),
  2. every row contains each digit once (81 items),
  3. every column contains each digit once (81 items),
  4. every box contains each digit once (81 items).

An option "put digit d in cell (r, c)" covers one item of each kind: 4 items. There are 729 options. Given clues simply remove all other options for those cells.

Python Sudoku with Algorithm X (dictionary version)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The solver finishes this puzzle almost instantly: most columns quickly reach size 1, which forces moves with no guessing.

Algorithm X versus plain backtracking

Idea Plain backtracking Algorithm X / DLX
Next decision first free cell or row the item with the fewest options
Undo recompute or restore copies reverse the linked-list unlinks in O(1)
Constraint modeling written by hand per puzzle uniform: write the items and options
Best for simple searches puzzles with many interacting exact constraints

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does an exact cover require?

    Each item must be covered once: no item uncovered and no item covered twice.
  2. 2. Why does Algorithm X branch on the item with the fewest remaining options?

    An item with one option forces a move, and an item with zero options proves the branch dead at once. Fewer choices means fewer branches.
  3. 3. What makes Dancing Links efficient for backtracking?

    After x.left.right = x.right, x still knows its neighbors, so restoring needs just two pointer assignments.
  4. 4. In the N-queens encoding, which items are secondary?

    Every row and column must contain exactly one queen, but a diagonal may be empty, so diagonals only need to be covered at most once.

Summary

  • Exact cover: choose options so every item is covered exactly once; Sudoku, N-queens and tilings all reduce to it.
  • Algorithm X branches on the item with the fewest options and removes the conflicting rows and columns before recursing.
  • Dancing Links stores the matrix as circular doubly linked lists, so cover and uncover are cheap and exactly reversible.
  • Secondary items model "at most once" constraints such as chess diagonals.
  • The worst case is exponential, but the heuristic makes puzzles fast.

Next: Meet in the Middle