Crate sudoku 

zero-alloc-sudoku

A zero-heap-allocation, sub-microsecond Sudoku solver for Rust.

Algorithm

The solver combines two techniques:

• 9-bit bitboard constraint propagation — each of the 27 constraint groups (9 rows + 9 columns + 9 boxes) is represented as a u16 bitmask where bit k is set when digit k+1 has been placed. The available digits for any empty cell are computed with a single bitwise NOT and AND in O(1).

• MRV (Minimum Remaining Values) heuristic backtracking — at each recursive step the empty cell with the fewest legal digits is chosen first. This prunes the search tree dramatically on hard puzzles.

The entire solver state is a single #[repr(C, align(64))] struct (~216 bytes) that fits within two cache lines, eliminating cache misses during search.

Quick start

use sudoku::Sudoku;

let mut sudoku: Sudoku = "800000000003600000070090200050007000\
                          000045700000100030001000068008500010\
                          090000400"
    .parse()
    .expect("valid puzzle");

assert!(sudoku.solve());
println!("{}", sudoku);

Performance

On a modern x86-64 CPU with --release and target-cpu=native:

Puzzle	Average (ns)	Throughput
Al Escargot	~400 ns	~2 500 000 /s
Hardest 2012	~600 ns	~1 600 000 /s
Platinum Blonde	~350 ns	~2 800 000 /s

Structs

Sudoku

A zero-allocation Sudoku board and solver.

Enums

ParseError

Error returned when a puzzle string cannot be parsed into a valid Sudoku.