Algorithm X in 30 lines!
algorithm-xexact-coverdancing-linkspythonsudokucombinatorics
Abstraction: Compact Python implementation of Knuth's Algorithm X for exact cover
Key points:
- Exact cover: given set X and subsets Y, find subcollection Y* that partitions X; NP-complete
- Algorithm X invented by Donald Knuth; Dancing Links is his efficient implementation using doubly-linked circular lists
- Python variant replaces linked lists with dicts: X becomes a dict mapping column → set of rows; enables O(1) cover/uncover
- Selects the column with minimum number of rows at each step (minimum remaining values heuristic)
- Input transformation is O(m*n) worst-case but O(N^3) for Sudoku grids of size N because each row has exactly 4 entries
- Full Sudoku solver for any grid size (3x3, 5x5, 2x3) implemented in under 100 lines using this approach
Connections: Donald Knuth · Exact Cover · Dancing Links · Backtracking
Source: http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html