ddidderr
8db952dcd4
Add a seven-page visual PDF that explains how the Sudoku solver parses input, builds row/column/block constraints, stores candidates as bit masks, applies naked and hidden singles, and orders recursive search branches. The guide is authored as plain HTML/CSS/SVG so the diagrams stay reviewable and can be regenerated without a separate design tool. The README now links to the PDF artifact for quick discovery. Test Plan: - cargo test - pdfinfo docs/solver-visual-guide.pdf - Raster-inspected exported PDF pages with pdftoppm Refs: none
63 lines
1.9 KiB
Markdown
63 lines
1.9 KiB
Markdown
# sudoku-ai
|
|
|
|
`sudoku-ai` solves plain-text Sudoku files from the command line:
|
|
|
|
```sh
|
|
./sudoku-ai <sudoku_file>
|
|
```
|
|
|
|
Input is a whitespace-separated grid. Use `0` for empty cells and decimal
|
|
values for filled cells:
|
|
|
|
```text
|
|
0 2 3 0 0 0 4 5 0
|
|
0 0 0 0 0 0 0 0 0
|
|
0 0 0 0 0 0 0 0 0
|
|
0 0 0 0 0 0 0 0 0
|
|
0 0 0 0 0 0 0 0 0
|
|
0 0 0 0 0 0 0 0 0
|
|
0 0 0 0 0 0 0 0 0
|
|
0 0 0 0 0 0 0 0 0
|
|
0 0 0 0 0 0 0 0 0
|
|
```
|
|
|
|
The grid width must equal the grid height, and the size must have square
|
|
blocks. That supports layouts such as 4x4 with 2x2 blocks, 9x9 with 3x3
|
|
blocks, and 16x16 with 4x4 blocks.
|
|
|
|
Example puzzles live in `sudoku-examples/`. For instance:
|
|
|
|
```sh
|
|
cargo run -- sudoku-examples/hard.sudoku
|
|
cargo run -- sudoku-examples/extreme.sudoku
|
|
```
|
|
|
|
A visual explanation of the solver is available in
|
|
[`docs/solver-visual-guide.pdf`](docs/solver-visual-guide.pdf).
|
|
|
|
## Project Decomposition
|
|
|
|
- Command-line interface: `src/main.rs`
|
|
- Parses the `./sudoku-ai <sudoku_file>` argument shape.
|
|
- Reads puzzle text from disk.
|
|
- Prints the solved grid or a user-facing error.
|
|
- Example puzzles: `sudoku-examples/`
|
|
- Stores reusable plain-text Sudoku inputs for manual solver checks.
|
|
- Solver library: `src/lib.rs`
|
|
- Plain-text parser
|
|
- Ignores blank lines.
|
|
- Validates square dimensions, block shape, and value ranges.
|
|
- Constraint model
|
|
- Stores each candidate set in a `u128` bit mask.
|
|
- Precomputes row, column, and block units for each cell.
|
|
- Precomputes peer cells for fast candidate elimination.
|
|
- Deduction engine
|
|
- Propagates placed values to all peers.
|
|
- Fills naked singles when a cell has one candidate.
|
|
- Fills hidden singles when a unit has one possible place for a value.
|
|
- Search engine
|
|
- Runs deduction until it stalls.
|
|
- Chooses the unsolved cell with the fewest candidates.
|
|
- Tries high-impact candidates first, then resumes deduction after each
|
|
assumption.
|