dedoku 0.7.0

A pure-Python Sudoku solver that uses only human-style logical deduction techniques (no backtracking).

Dedoku

A pure-Python Sudoku solving library that relies exclusively on human-style logical deduction — 20 named technique families, from naked singles to alternating inference chains, and not a single guess.

About the project

Most Sudoku solvers brute-force the board: try a digit, propagate, undo on contradiction. This library takes the opposite stance. Every digit placed and every candidate eliminated is the conclusion of a named, explainable technique, applied exactly the way a strong human solver would reason. The full solving path is recorded step by step, so any solution can be replayed and audited.

• Zero external dependencies — Python 3.10+ standard library only, tests included (unittest).
• Fully typed and documented — modern type hints and Sphinx-style reStructuredText docstrings on every module, class, and method.
• Explainable solving — each Step reports the technique, a human-readable description, the placements, and the eliminations.
• Honestly benchmarked — a reproducible 500-puzzle benchmark against a reference backtracking solver ships with the repo (below).

Solving philosophy

Logic first. Guessing only if you ask for it. By default the solver never backtracks: if the pipeline of logical techniques cannot finish a puzzle, it stops and says so (11 puzzles out of 100 on the benchmark's hardest tier). When you just need the answer, two explicit opt-in modes exist — method="hybrid" completes the remainder by brute force after the techniques stall, method="backtracking" skips logic entirely — and anything brute-forced is recorded as an explicit "Backtracking" step: the solving path never lies about how a cell was filled.

Installation

pip install dedoku

Or from source:

git clone https://github.com/n36l3c7/dedoku.git
cd dedoku
pip install -e .

Either way, no dependencies come with it — the package is pure standard library.

Usage

The one-liner:

import dedoku

result = dedoku.solve("530070000600195000098000060800060003400803001"
                      "700020006060000280000419005000080079")
print(result.solved)   # True
print(result.grid)     # pretty-printed solved board
for step in result.steps:
    print(f"[{step.technique}] {step.description}")

# When you just need the answer, even beyond the logical pipeline:
dedoku.solve(puzzle, method="hybrid")         # logic first, brute force finishes
dedoku.solve(puzzle, method="backtracking")   # brute force directly

Or with full control over the board and the pipeline:

from dedoku import Grid, SudokuSolver

puzzle = (
    "530070000"
    "600195000"
    "098000060"
    "800060003"
    "400803001"
    "700020006"
    "060000280"
    "000419005"
    "000080079"
)

grid = Grid.from_string(puzzle)
result = SudokuSolver().solve(grid)

print(result.solved)          # True
print(grid)                   # pretty-printed solved board
print(grid.to_string())       # 81-character string

for step in result.steps:     # the full, explainable solving path
    print(f"[{step.technique}] {step.description}")
print(result.techniques_used) # distinct techniques, in first-use order

Puzzle strings are 81 characters, read left to right, top to bottom: digits 1–9 are givens, 0 or . mark empty cells; whitespace and the decoration characters |, -, + are ignored, so pretty-printed boards parse back.

Need a custom pipeline? Pass any sequence of techniques, tried in order:

from dedoku import SudokuSolver
from dedoku.techniques import HiddenSingle, NakedSingle, XYChain

solver = SudokuSolver(techniques=[NakedSingle(), HiddenSingle(), XYChain()])

The board model is fully navigable if you want to build your own techniques: each Cell knows its row, column, subgrid, candidates, and peers; the Grid exposes all 27 houses via rows, columns, subgrids, units. Full guides and API reference: n36l3c7.github.io/dedoku.

Command line

Installing the package also installs the dedoku command. Add --explain to watch the whole reasoning, cell by cell:

$ dedoku 530070000600195000098000060800060003400803001700020006060000280000419005000080079 --explain
   1. R5C5 = 5               [Naked Single] R5C5 has 5 as its only candidate
   2. R5C2 = 2               [Naked Single] R5C2 has 2 as its only candidate
   ...
Solved in 51 steps using: Naked Single

Options: puzzle from argument or stdin, --method {logic,hybrid,backtracking} (logic is the default; the other two finish any puzzle by explicit brute force), --multi for puzzles without a guaranteed unique solution, exit codes 0/1/2 (solved / stalled / invalid).

Implemented techniques

The default pipeline applies 28 technique instances from 20 families, always restarting from the simplest after every deduction.

#	Family	Classes	Module
1	Naked Candidates	NakedSingle, NakedPair, NakedTriple, NakedQuad	naked.py
2	Hidden Candidates	HiddenSingle, HiddenPair, HiddenTriple, HiddenQuad	hidden.py
3	Intersection Removal	PointingCandidates, ClaimingCandidates	intersections.py
4	X-Wing	XWing	fish.py
5	Chute Remote Pairs	ChuteRemotePairs	chute.py
6	Simple Colouring	SimpleColouring	colouring.py
7	W-Wing	WWing	wwing.py
8	Y-Wing (XY-Wing)	YWing	wings.py
9	Unique Rectangles	UniqueRectangle (Type 1)	rectangles.py
10	Swordfish	Swordfish	fish.py
11	XYZ-Wing	XYZWing	wings.py
12	BUG (Bivalue Universal Grave)	BivalueUniversalGrave	bug.py
13	Avoidable Rectangles	AvoidableRectangle	rectangles.py
14	Unique Rectangles Type 2	UniqueRectangleType2	rectangles.py
15	Finned Fish	FinnedXWing, FinnedSwordfish	fish.py
16	X-Chain (basic X-Cycles)	XChain	chains.py
17	XY-Chain	XYChain	chains.py
18	3D Medusa	Medusa3D	medusa.py
19	ALS-XZ (Almost Locked Sets)	AlsXz	als.py
20	AIC (Alternating Inference Chains)	AIC	aic.py

Uniqueness-based techniques (9, 12, 13, 14) assume the puzzle has exactly one solution — the standard convention for published Sudokus. Solving a puzzle that might have multiple solutions? Pass assume_unique=False to dedoku.solve() or SudokuSolver() and they are excluded, keeping every deduction sound.

Benchmark

500 unique-solution puzzles (seed 42), 100 for each of five difficulty levels, timed against the lightest classic backtracking solver (bitmask, sequential cells, no heuristics). Same protocol for both solvers: puzzle string in, board out, minimum of 3 runs, parsing included. Python 3.13, Windows 11. Levels are graded by the hardest technique the original 13-family pipeline needs: singles → subsets → intersections → advanced → extreme (beyond that base pipeline).

Solve-time distribution

Level	Solved by library	BT median	BT p95	BT max	Library median	Library p95	Library max
1 · Singles	100/100	15.9 ms	481 ms	1,757 ms	1.1 ms	1.6 ms	1.8 ms
2 · Subsets	100/100	13.1 ms	218 ms	2,172 ms	1.6 ms	2.4 ms	2.9 ms
3 · Intersections	100/100	5.0 ms	126 ms	2,026 ms	3.1 ms	7.8 ms	12.1 ms
4 · Advanced	100/100	15.6 ms	225 ms	551 ms	7.5 ms	17.7 ms	31.2 ms
5 · Extreme	89/100 †	16.7 ms	229 ms	684 ms	65.4 ms	306 ms	720 ms
Overall	489/500	12.6 ms	279 ms	2,172 ms	3.0 ms	158 ms	720 ms

† On the 11 extreme puzzles the library cannot crack, its reported time is the time to exhaust every technique and stop — never a guess.

Key findings:

• The logic library wins on the median at every human-graded level up to Advanced (3.0 ms vs 12.6 ms overall) and is far more predictable: naive backtracking's worst case is 2.2 s when the cell order is unlucky, versus 0.72 s for the library's hardest chain solve.
• Brute-force time is uncorrelated with human difficulty — backtracking is fastest on level 3 and slowest on level 1, while the library's times grow monotonically with the level. The two solvers measure different notions of "hard".
• Level 5 is chain territory: the advanced techniques added in v0.2.0 raised the library's extreme-tier solve rate from 0/100 to 89/100.

Which techniques crack the extreme tier

Reproduce it

python benchmark/generate_puzzles.py   # optional: regenerate the dataset (seeded)
python benchmark/run_benchmark.py      # times both solvers, writes benchmark/results.csv
python benchmark/make_charts.py        # renders the SVG charts into docs/

Architecture

Class	Responsibility
Cell	A single cell: value, candidates, position, given flag, and references to its row, column, and subgrid.
Unit → Row, Column, Subgrid	The 27 houses of nine cells, sharing bookkeeping logic.
Grid	The full 9×9 board: wiring, parsing, serialisation, validity.
Technique / Step	One logical strategy and the immutable record of one applied deduction.
SudokuSolver / SolveResult	The engine that chains techniques and the outcome of a session.

Development

python -m unittest discover -s tests -v   # 100 tests, includes the step oracle
python -m ruff check dedoku tests benchmark
python -m mypy dedoku
python -m coverage run -m unittest discover -s tests && python -m coverage report

CI runs the suite on Linux, Windows, and macOS across Python 3.10–3.14, with ruff, mypy, and a 95% coverage gate. Beyond unit tests, an oracle check verifies that every placement matches an independent backtracking solution and that no elimination ever removes a true digit — the library's core contract, tested directly.

Soundness validation

python benchmark/validate.py --count 5000 --seed 7

Latest run: 5,000 generated puzzles, every single deduction verified — 4,933 solved, 67 stalled (extreme chain territory), 0 unsound steps.

Versioning and stability

The project follows Semantic Versioning. The public API is everything importable from dedoku and dedoku.techniques and documented in this README; underscore-prefixed names are internal. Until 1.0.0, breaking changes may still occur in minor releases and are always listed in the changelog; from 1.0.0 on they will only happen in major releases, preceded by a deprecation period. Note that SudokuSolver.solve(grid) mutates the grid it receives — use dedoku.solve(puzzle) if you prefer a fresh board per call.

License

Released under the MIT License.