Working Notes: a commonplace notebook for recording & exploring ideas.
Home. Site Map. Subscribe. More at expLog. — Kunal

Dancing Links & Algorithm X

Dancing Links came up while I was reading for real solutions to AoC'25 Day 12: if I actually wanted to solve the solutions. It's always a pleasure to read anything by Knuth.

The idea behind dancing links is that information for being able to backtrack is just maintained on the node that was removed instead of having to maintain it externally.
Exact cover is referenced as a problem of choosing rows in a matrix such that each row/column has exacly one 1 value, this is surprisingly powerful
- The way to represent pentominos as matrices is pretty cool: one set of columns to identify the shape, one set of columns to identify the squares occupied by the shape -- as long as all pentominos are used up and they cover all the possible cells, the exact cover problem as state above gets the solution
Algorithm with backtracking
- for a matrix A of 0s and 1s
- if A is empty, problem is solved
- Choose a column c deterministically
- Choose a row r such that A[r, c] = 1 (non deterministically)
- Include r in the partial solution
- For each j, such that A[r, j] = 1, delete column j from matrix A for each i such that A[i, j] = 1, delete row i from matrix A
- Repeat recursively on reduced matrix
In my words
- the matrix represents all possible states to explore
- we keep eliminating values from the matrix as we make guesses
- as the guesses are made, constraints corresponding to those guesses are deleted
  - by deleting that column from the matrix
  - and also deleting any other rows that would clash with the current row choice
- then backtrack
- if any column is all zeros, there's no way to cover it -- and the current attempt is invalid
- choosing a column can be in many ways
  - one way is to choose the column with the least possible branches total number of 1s

While chatting with Gemini about the implementation of dancing links, I learned that Prof Knuth has covered the topic in Vol 4 Fascicle 5: which I happen to have.

It's fascinating to compare the paper (which feels very approachable and easy to understand) against the book: 500 problems on dancing links, with a 30 page description covering much more ground and types of problems.

The biggest change is that the book goes into a cache efficient implementation of dancing links for the linked list, to make it much easier to work with and explore; this is what I should try.

Follow up project ideas for later:

a full dlx implementation that handles the array based implementation
visualizing the implementation with animations to see the dance / plot graphs of the exploration
parallel programming / gpu friendly version of dancing links?

A very naive implementation of algorithm X, just because I was fascinated by the extremely clean description of backtracking (without any dancing links):

import logging
import sys

from logging import getLogger, basicConfig
from typing import NamedTuple


nl = logging.getLogger("naive")


def _pm(mat: list[list[int]]):
	if nl.isEnabledFor(logging.DEBUG):
		for i, row in enumerate(mat):
			print(" ".join(map(str, row)))


def _naive_soln_impl(amat: list[list[int]], soln: list[int]) -> list[int] | None:
	assert len(amat) > 0, "Must have annotation row/col"

	nl.debug(f"{soln=}")
	_pm(amat)

	#> If A is empty, the problem is solved; terminate successfully.
	if len(amat) == 1 and len(amat[0]) == 1:  # Just the corner
		return soln

	arows = len(amat)
	acols = len(amat[0])

	#> Otherwise choose a column, c (deterministically).
	min_branches: None | tuple[int, int] = None
	for j in range(1, acols):
		col_branches = sum(amat[i][j] for i in range(1, arows))
		if min_branches is None or col_branches < min_branches[1]:
			min_branches = (j, col_branches)

	nl.debug(f"{min_branches=}")
	if not min_branches or min_branches[1] == 0:
		return None
	c = min_branches[0]

	#> Choose a row, r, such that A[r, c] = 1 (nondeterministically).
	for r in range(1, arows):
		if amat[r][c] != 1:
			continue

		#> Include r in the partial solution.
		r_soln = [*soln, amat[r][0]]

		del_cols = set()
		del_rows = set()

		#> For each j such that A[r, j] = 1,
		for j in range(1, acols):
			if amat[r][j] != 1:
				continue

			#> delete column j from matrix A;
			del_cols.add(j)

			#> for each i such that A[i, j] = 1, delete row i from matrix A.
			for i in range(1, arows):
				if amat[i][j] == 1:
					del_rows.add(i)

		next_mat = []
		for i in range(0, arows):
			if i in del_rows:
				continue

			next_row = []
			for j in range(0, acols):
				if j in del_cols:
					continue
				next_row.append(amat[i][j])

			next_mat.append(next_row)

		#> Repeat this algorithm recursively on the reduced matrix A.
		if result := _naive_soln_impl(next_mat, r_soln):
			return result

	return None


def naive_soln(mat: list[list[int]]) -> list[int] | None:
	"""
	First attempt at implementing algorithm X without dancing links.
	"""

	# Add labels ot the matrix
	rows = len(mat)
	cols = len(mat[0])
	amat = [
		list(range(cols + 1)),
		*([i + 1, *row] for i, row in enumerate(mat)),
	]

	result = _naive_soln_impl(amat, list())
	return result