DLX Exact Cover Solver

A Python implementation of Donald Knuth's Dancing Links (DLX) algorithm for solving Exact Cover problems, inspired by the test cases described in his foundational paper Dancing Links.

Overview

This project demonstrates how to solve these highly constrained logic puzzles (finding a perfect selection of subsets) using the exquisite "dance" of the doubly linked lists data structure.

Note: Some computationally intensive examples are not included here. For performance reasons, certain examples find only the first solution by default. To find all solutions, you can set find_all=True when creating the solver.

Installation

git clone https://github.com/yiz-bit/dlx-exact-cover.git
cd dlx-exact-cover

Python 3.12+ is required.

Basic Usage

See test/abstract_matrix.py for a simple example of defining and solving an Exact Cover problem.

To solve your own problem:

from dlx import DLXSolver, ExactCoverProblem

# Define a binary matrix where rows are options and columns are constraints
matrix = [[1, 0, 0], [0, 1, 1], [1, 0, 1]]
row_info = ["option_A", "option_B", "option_C"]

problem = ExactCoverProblem(matrix=matrix, row_info=row_info)
solver = DLXSolver(problem, find_all=True)
solver.solve()

solutions = solver.get_solutions()
stats = solver.get_statistics()
print(f"Found {len(solutions)} solution(s)")

API

ExactCoverProblem(matrix, row_info) - Defines a problem

• matrix: List of binary lists (rows are options, columns are constraints)
• row_info: Metadata for each row

DLXSolver(problem, find_all=False, num_primary=None) - The solver

• find_all: If True, find all solutions; otherwise stop at first
• num_primary: Number of mandatory columns (default: all)

Methods:

• solve() - Execute the algorithm
• get_solution(index) - Get solution by index
• get_solutions() - Get all solutions
• get_statistics() - Return statistics (nodes_expanded, updates, computation_time)

Core Features

• Pure DLX Engine: Faithfully implements the cover and uncover operations using matrix abstraction
• S-Heuristic Optimization: Automatically chooses the column with the fewest 1s to dramatically minimize the branching factor of the search tree
• Secondary Columns Support: Handles optional constraints seamlessly (vital for solving the N-Queens diagonals)
• Organ-Pipe Ordering: Implements Knuth's specific central-first column ordering for the N-Queens problem to prune dead ends faster
• Detailed Statistics: Accurately counts search tree nodes and pointer updates just as defined in Knuth's paper

Examples

The examples/ directory contains applications of the DLX algorithm:

Sudoku Solver

Solve 9×9 Sudoku puzzles

python3 -m examples.sudoku

Puzzle files sudoku_easy.txt, sudoku_medium.txt, and sudoku_hard.txt contain sample puzzles with increasing difficulty.

N-Queens Problem

Place N non-attacking queens on an N×N board from N=1 to N=13. You can extend this range by modifying the main function.

python3 -m examples.nqueens

Pentomino Puzzles

The pentomino modules have been generalized to share common components from scott_pentomino.py:

Scott's Pentomino Problem - Classic 8×8 board with 2×2 center removed (Dana Scott's formulation)

python3 -m examples.scott_pentomino

6×10 Rectangle Pentomino - Tile a 6×10 rectangle with 12 standard pentominoes

python3 -m examples.pentomino

One-Sided Pentominoes - Tile a 3×30 rectangle with 18 one-sided pentominoes (rotations only, no flips)

python3 -m examples.onesided_pentomino

Dudeney's Pentomino Problem - Place 12 pentominoes on an 8×8 board with a movable 2×2 hole

python3 -m examples.dudeney_pentomino               # hole at center (default)
python3 -m examples.dudeney_pentomino --hole 0 0    # hole at custom position (0,0)
python3 -m examples.dudeney_pentomino --all         # scan all canonical hole positions
python3 -m examples.dudeney_pentomino --full --all  # scan all 49 valid positions
python3 -m examples.dudeney_pentomino --show 2      # display up to 2 solutions per position

Other Problems

Mutilated Chessboard Problem - Determine if a chessboard with two opposite corners removed can be tiled with dominoes

python3 -m examples.mutilated_chessboard

Your Problem - Define your specific problem by constructing the binary matrix that represents it, then simply invoke the DLXSolver class.

Project Structure

dlx-exact-cover/
├── dlx.py                          # Main solver implementation
├── README.md                        # This file
├── examples/                        # Application examples
│   ├── scott_pentomino.py          # Shared pentomino utilities & Scott's solver
│   ├── pentomino.py                # 6×10 rectangle (imports from scott_pentomino)
│   ├── onesided_pentomino.py       # 3×30 rectangle with one-sided pieces
│   ├── dudeney_pentomino.py        # 8×8 board with movable hole
│   ├── sudoku.py                   # Sudoku solver
│   ├── nqueens.py                  # N-Queens problem solver
│   ├── mutilated_chessboard.py     # Domino tiling problem
│   ├── sudoku_easy.txt             # Sample puzzles (increasing difficulty)
│   ├── sudoku_medium.txt
│   └── sudoku_hard.txt
└── test/
    └── abstract_matrix.py          # Basic usage example

References

• Donald Knuth's original paper on Dancing Links (http://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/0011047.pdf)