Dancing Links Sudoku: How Computers Solve the Grid Fast

How a solver searches

Every Sudoku solver has to search: it places a candidate, checks whether the grid still obeys the rules, and either continues or backs up. Plain backtracking does this cell by cell, which works but can be slow on the hardest puzzles. Dancing links sudoku solving speeds this up by changing how the search remembers what is still possible, so undoing a bad guess costs almost nothing. That last part, cheap undoing, is the secret. It is a technique published by Donald Knuth to implement his Algorithm X, a general method for solving exact cover problems, and Sudoku happens to be a perfect fit for it once the puzzle is rewritten in the right form.

What dancing links sudoku actually does

A dancing links sudoku solver first turns the puzzle into a big table of yes-or-no choices, then repeatedly picks the constraint that is hardest to satisfy, tries each option for it, and covers the rows and columns that the option rules out. The name comes from the way pointers in a doubly linked list seem to dance as items are removed and put back. Imagine every item holding a pointer to its left and right neighbor. To remove an item you tell its neighbors to point past it, and the clever part is that the removed item still remembers where it belonged, so restoring it means telling the same neighbors to point back. No searching, no copying, just a couple of pointer updates out and back.

Cover, uncover, repeat

In Algorithm X the two moves are cover and uncover. Cover removes a constraint that has been satisfied along with every option that conflicts with the current choice; uncover reverses it exactly. Because the reversal is perfect and cheap, the solver can dive deep down a wrong path and then rewind instantly to try another. This is why dancing links sudoku handles even fiendish grids without slowing to a crawl: the search space is enormous, but each step in and out of it is tiny. To feed Sudoku in, you list every placement, one symbol in one cell, as a choice, and four kinds of constraint as columns: each cell holds one symbol, and each row, column, and box holds each symbol once. Solving becomes choosing placements that cover every constraint exactly once.

Same trick under a colorful grid

The digits are incidental. Shapedoku uses nine shapes instead of one through nine, and the free solver on shapedoku.com runs the very same kind of exact cover logic under a friendly surface. You never need to code any of this to enjoy the game, but knowing it exists changes how you see difficulty: when an app promises a puzzle has exactly one solution, a dancing links sudoku routine likely verified it in milliseconds, and when Shapedoku validates an Extreme board before you see it, similar machinery guarantees the grid is fair. If you enjoy watching structured systems flow and rewind into place, you might also like Rune Flow from the same studio, where pieces slot along connected paths. Both scratch the same itch of order emerging from a tangle of choices.