Metadata-Version: 2.4
Name: dedoku
Version: 1.1.0
Summary: A pure-Python Sudoku solver that uses only human-style logical deduction techniques (no backtracking).
Author-email: n36l3c7 <gervasio.samu@gmail.com>
License: MIT
Project-URL: Repository, https://github.com/n36l3c7/Dedoku
Project-URL: Documentation, https://n36l3c7.github.io/Dedoku/
Project-URL: Changelog, https://github.com/n36l3c7/Dedoku/blob/main/CHANGELOG.md
Keywords: sudoku,solver,puzzle,logic,deduction
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Topic :: Games/Entertainment :: Puzzle Games
Classifier: Typing :: Typed
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Dynamic: license-file

<div align="center">

<picture>
  <source media="(prefers-color-scheme: dark)" srcset="https://raw.githubusercontent.com/n36l3c7/Dedoku/main/docs/_static/banner-dark.svg">
  <img alt="dedoku — sudoku, solved by pure logic" width="640" src="https://raw.githubusercontent.com/n36l3c7/Dedoku/main/docs/_static/banner-light.svg">
</picture>

</div>

[![PyPI](https://img.shields.io/pypi/v/dedoku?color=2a78d6)](https://pypi.org/project/dedoku/)
[![Python versions](https://img.shields.io/pypi/pyversions/dedoku?logo=python&logoColor=white)](https://pypi.org/project/dedoku/)
[![License: MIT](https://img.shields.io/badge/license-MIT-green)](LICENSE)
[![Dependencies](https://img.shields.io/badge/dependencies-zero-brightgreen)](pyproject.toml)
[![Tests](https://github.com/n36l3c7/Dedoku/actions/workflows/tests.yml/badge.svg)](https://github.com/n36l3c7/Dedoku/actions/workflows/tests.yml)
[![Backtracking](https://img.shields.io/badge/backtracking-opt--in%20only-red)](#solving-philosophy)
[![Docs](https://img.shields.io/badge/docs-online-2a78d6)](https://n36l3c7.github.io/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](#benchmark)).

### 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

```bash
pip install dedoku
```

Or from source:

```bash
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:

```python
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:

```python
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:

```python
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](https://n36l3c7.github.io/Dedoku/)**.

### Command line

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

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

<picture>
  <source media="(prefers-color-scheme: dark)" srcset="https://raw.githubusercontent.com/n36l3c7/Dedoku/main/docs/benchmark-distribution-dark.svg">
  <img alt="Solve-time distribution by difficulty level: one dot per puzzle on a logarithmic ms scale, backtracking vs logic library, with medians marked" src="https://raw.githubusercontent.com/n36l3c7/Dedoku/main/docs/benchmark-distribution-light.svg">
</picture>

| Level | Solved by library | BT median | BT p95 | BT max | Library median | Library p95 | Library max |
|---|---|---|---|---|---|---|---|
| 1 · Singles | 100/100 | 18.3 ms | 526 ms | 1,913 ms | **1.3 ms** | 2.1 ms | 2.7 ms |
| 2 · Subsets | 100/100 | 14.0 ms | 218 ms | 2,314 ms | **1.6 ms** | 2.6 ms | 2.8 ms |
| 3 · Intersections | 100/100 | 5.4 ms | 134 ms | 2,165 ms | **3.4 ms** | 8.8 ms | 12.9 ms |
| 4 · Advanced | 100/100 | 11.2 ms | 144 ms | 353 ms | **5.0 ms** | 12.1 ms | 23.2 ms |
| 5 · Extreme | 89/100 † | **17.0 ms** | 241 ms | 721 ms | 60.1 ms | 215 ms | 495 ms |
| **Overall** | **489/500** | 12.0 ms | 239 ms | 2,314 ms | **2.8 ms** | 104 ms | 495 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** (2.8 ms vs 12.0 ms overall) and is far more predictable: naive
  backtracking's worst case is 2.3 s when the cell order is unlucky, versus
  0.50 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

<picture>
  <source media="(prefers-color-scheme: dark)" srcset="https://raw.githubusercontent.com/n36l3c7/Dedoku/main/docs/benchmark-techniques-dark.svg">
  <img alt="Number of solved extreme puzzles in which each advanced technique fired, XY-Chain leading with 55 of 89" src="https://raw.githubusercontent.com/n36l3c7/Dedoku/main/docs/benchmark-techniques-light.svg">
</picture>

### Reproduce it

```bash
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

```bash
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

```bash
python benchmark/validate.py --count 100000 --seed 100 --jobs 8
```

The 1.0.0 release run: **100,000 generated puzzles, every single deduction
verified — 98,687 solved by pure logic (98.7%), 1,313 stalled (extreme
chain territory), 0 unsound steps.**

## Versioning and stability

The project follows [Semantic Versioning](https://semver.org/) and is
**stable as of 1.0.0**. The public API is everything importable from
`dedoku` and `dedoku.techniques` and documented in this README;
underscore-prefixed names are internal. Breaking changes only happen in
major releases, preceded by a deprecation period, and every change is
listed in the [changelog](CHANGELOG.md). 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](LICENSE).
