Sudoku Solver Speed Optimization (Rust)

March 20, 2026 · View on GitHub

Autonomous optimization of a Rust sudoku solver using the autoresearch pattern. The agent modifies src/solver.rs, benchmarks against official datasets, keeps improvements, reverts regressions, and loops forever.

Setup

Agree on a run tag: Propose a tag based on today's date (e.g., mar20). The branch autoresearch/<tag> must not already exist.
Create the branch: git checkout -b autoresearch/<tag> from current master.
Read the in-scope files:
- src/solver.rs — the file you modify. Contains the sudoku solving algorithm.
- src/main.rs — frozen evaluation harness and puzzle set. Do not modify.
- eval.sh — frozen eval runner (compiles + runs). Do not modify.
- No external crate dependencies. Rust standard library only. Compiler settings (LTO, codegen-units, panic, strip, target-cpu) are fine to change in Cargo.toml.
Verify Cargo is available: Run cargo --version. If it fails, run source "$HOME/.cargo/env" or export PATH="$HOME/.cargo/bin:$PATH".
Verify baseline runs: bash eval.sh should compile and print results.
Initialize results.tsv: Create results.tsv with the header row only.
Confirm and go: Confirm setup looks good, then kick off experimentation.

We are optimizing a Rust sudoku solver for raw speed across 20 puzzles of varying difficulty — from easy puzzles to "world's hardest" (Arto Inkala 2010, Easter Monster, Golden Nugget, etc.). The eval compiles in release mode and reports total solve time in microseconds.

What you CAN do:

Modify src/solver.rs — this is the only file you edit. Everything is fair game: algorithm, data structures, bitmasks, constraint propagation, lookup tables, SIMD-friendly layouts, cache-friendly memory access, backtracking strategy, cell ordering, unsafe code — whatever makes the number go down.

What you CANNOT do:

Modify src/main.rs — frozen. Contains puzzles and correctness verification.
Modify eval.sh — frozen eval runner.
Change the public function signature: pub fn solve(grid: &mut [[u8; 9]; 9]) -> bool must remain the same. Returns true if solved (grid modified in-place), false if unsolvable.

Fair play

The solver must be a general-purpose sudoku solver — capable of solving any valid 9×9 sudoku puzzle, not just the 20 in the test set. Specifically:

No hardcoded solutions or partial solutions for the test puzzles.
No fingerprinting — do not hash or identify input puzzles to return precomputed answers.
No compile-time extraction — do not read or parse main.rs to extract puzzle data.
General lookup tables are fine — precomputed peer tables, valid band configurations, bitmask popcount tables, etc. These help on all puzzles.
Puzzle-specific data is cheating.

The test set may change at any time. A solver that only works on these specific 20 puzzles is worthless. Build a genuinely fast general solver.

The goal is simple: get the lowest duration_us (total microseconds for all 20 puzzles).

Performance is the only thing that matters. Complex code that is faster beats simple code that is slower. A complete architectural rewrite is worth it if the number goes down. The metric is the only judge.

Hardware

AMD Ryzen 9 8940HX (Zen 4 / Dragon Range, TSMC 5nm)

Spec	Detail
Cores / Threads	16 / 32 (solver is single-threaded — only boost clock matters)
Boost clock	Up to 5.3 GHz
L1 cache	64 KB per core (32 KB instruction + 32 KB data)
L2 cache	1 MB per core (16 MB total)
L3 cache	64 MB shared
ISA extensions	SSE2–SSE4.2, AVX, AVX2, AVX-512, FMA3, AES, SHA

The full solver state (~400 bytes) fits in L1 easily. Keep it that way.

AVX-512 is confirmed available. Use _mm512 intrinsics via std::arch::x86_64. This can process 32 × u16 candidate masks in a single instruction — the same capability that makes Tdoku (the #1 solver globally) fast.

Compiler target: Use target-cpu=znver4 in .cargo/config.toml for Zen 4 specific optimizations and AVX-512 codegen.

The first run

Your very first run should always establish the baseline. Run the evaluation as-is without modifications.

Real-world benchmark

The primary evaluation uses 5 official sudoku benchmark datasets (248,000+ puzzles) used by the global solver community for rankings. This replaces the 20-puzzle eval as the primary metric.

The 5 datasets

Dataset	Puzzles	Difficulty	Purpose
`forum_hardest_1905_11+`	48,766	Extreme (SE 11+)	THE main global ranking dataset. This matters most.
`magictour_top1465`	1,465	Hard	Classic benchmark since 2006. Every solver comparison uses this.
`forum_hardest_1106`	375	Hardest known	Ultimate stress test — the hardest puzzles known to humanity.
`17_clue`	49,158	Minimal-clue	Tests propagation efficiency. Half solvable with singles alone.
`kaggle`	100,000	Easy	Pure propagation throughput. Zero backtracking needed.

Running the benchmark

bash bench.sh > bench.log 2>&1
cat bench.log

This builds the bench binary using the same solver.rs you edit. No file copying needed. bench.rs and bench.sh are frozen — never modify them.

The output shows usec_per_puzzle for each dataset. Extract results:

grep "usec_per_puzzle" bench.log

Targets

These are what we need to achieve across all 5 datasets simultaneously:

Dataset	Target (µs/puzzle)	Reference: rust_sudoku	Reference: Tdoku
forum_hardest_1905_11+	< 15	44.24	41.7
magictour_top1465	< 3	7.86	6.0
forum_hardest_1106	< 25	80.13	77.1
17_clue	< 1.0	1.79	3.3
kaggle	< 0.5	0.91	1.3

No solver in history has achieved all 5 simultaneously. We will be the first. These are not suggestions — these are the finish line. Do not stop until all 5 are green.

Key insight

The solver currently dominates on extreme and hard puzzles but loses on easy and medium ones. The gap on easy puzzles is caused by propagation overhead — processing cells one at a time. The fastest solvers process 27 cells per instruction using band-level data structures. Closing the easy puzzle gap requires an architectural change to how propagation works, not just tweaking the current approach. Think about how to eliminate candidates across entire bands in one operation instead of looping through individual cells.

Logging results

Tab-separated results.tsv with all 5 dataset metrics:

commit	hard11	magic	hard1106	17clue	kaggle	status	description

Column	Content
`commit`	Git commit hash (short, 7 chars)
`hard11`	µs/puzzle on forum_hardest_1905_11+
`magic`	µs/puzzle on magictour_top1465
`hard1106`	µs/puzzle on forum_hardest_1106
`17clue`	µs/puzzle on 17_clue
`kaggle`	µs/puzzle on kaggle
`status`	`keep`, `discard`, or `crash`
`description`	Short text describing what this experiment tried

Use 0 for all metrics on crashes. A run is "keep" only if it improves at least one dataset without regressing any other by more than 5%.

Every 20 experiments, review results.tsv and write a brief analysis in insights.md — what works, what doesn't, where the remaining time is being spent.

The experiment loop

LOOP FOREVER:

Look at the git state — the current branch and commit.
Modify src/solver.rs with an experimental idea.
git commit with a descriptive message.
Run the experiment: bash bench.sh > bench.log 2>&1 (redirect everything — do not let output flood your context).
Read the results: grep "usec_per_puzzle" bench.log
If compilation failed, read the error and attempt a fix.
Record the results in results.tsv (do not commit this file — leave it untracked by git).
If any dataset improved without regressing others by more than 5%, keep the commit and advance the branch.
If no improvement or regression, git reset back to where you started.

The old 20-puzzle eval.sh still works for quick sanity checks during development. Use bench.sh for the official measurement.

Timeout: The full benchmark takes ~60–90 seconds for all 5 datasets. If it exceeds 300 seconds, kill it.

Crashes: Compilation errors are common in Rust. If it's a simple fix (borrow checker, type mismatch), fix and retry. If the approach is fundamentally broken, skip it, log "crash", and move on.

NEVER STOP. Once the experiment loop has begun, do not pause to ask the human if you should continue. The human might be asleep. Run until manually interrupted. If you run out of ideas, think harder.

Strategy hints

The baseline is naive recursive backtracking with linear cell scanning. In Rust, even naive backtracking is fast, but the hard puzzles (especially the near-empty grid, Easter Monster, Golden Nugget) will dominate total time. Optimizations that speed up hard puzzles matter most.

Ideas roughly ordered from quick wins to deeper optimizations:

Bitmask candidate tracking — Use u16 bitmasks for row/col/box constraints instead of calling is_valid() for each number. One AND operation to get all valid candidates.
MRV (Minimum Remaining Values) — Always pick the cell with the fewest candidates. Dramatically reduces search tree on hard puzzles.
Constraint propagation — When a cell is assigned, propagate constraints. If any cell has exactly one candidate, assign it immediately (naked singles). This can solve easy puzzles with zero backtracking.
Hidden singles — If a number can only go in one cell within a row/col/box, place it immediately.
Arc consistency (AC-3) — Full constraint propagation. Repeatedly propagate until stable, then backtrack on the most constrained cell.
Cache-friendly layout — Flat [u8; 81] array instead of [[u8; 9]; 9]. Pre-computed lookup tables for peers.
Unsafe optimizations — Unchecked array access in hot loops (after proving correctness) to eliminate bounds checks.
Stack-based backtracking — Iterative instead of recursive to avoid function call overhead and potential stack overflow.
Dancing Links / Algorithm X — Exact cover formulation. Complex to implement but extremely fast on hard puzzles.
Precomputed peer tables — Static arrays of related cells for each position, avoiding repeated index arithmetic.

Beyond cell-level thinking

The current solver processes one cell at a time. The fastest solvers in existence do not. Here are architectural paradigms to explore when incremental cell-level tweaks stop yielding gains:

Band-level bitboards: Instead of 81 individual cells, think of the grid as 3 horizontal bands (rows 0–2, 3–5, 6–8), each containing 27 cells. Pack all candidates for an entire band into a single u128 or pair of u64s. Constraint propagation then becomes a single bitwise AND/OR across 27 cells simultaneously instead of a loop. This is the single biggest architectural leap available — it can give 5–10× speedup over cell-level approaches.

SIMD vector operations: You have access to std::arch::x86_64 — this is Rust's standard library, not an external crate. Use AVX2 intrinsics like _mm256_and_si256, _mm256_or_si256, _mm256_andnot_si256 to process 256 bits (32 bytes) in a single CPU instruction. If the board representation is designed around 256-bit register widths, constraint propagation becomes one instruction instead of a loop. Combine this with band-level bitboards for maximum effect.

Triad representation: Instead of individual cells, represent groups of 3 cells (the intersection of a box-row or box-column) as a single unit. Triads are the natural unit for constraint propagation because eliminations in a triad affect exactly one row, one column, and one box. This maps cleanly onto SIMD lanes.

Watched literals: Borrowed from SAT solvers. Instead of scanning all cells when a constraint changes, maintain a watch list — only re-check cells that are actually affected. O(1) per irrelevant elimination instead of O(n).

Template-based solving: Precompute solution templates for each digit in each band. A band has only ~36,288 valid configurations for each digit. Store these as bitmasks and intersect them — solving becomes a series of table lookups and AND operations with zero backtracking for easy cases.

You are fully unrestricted

Use unsafe, raw pointers, transmute, inline assembly (std::arch::asm!), SIMD intrinsics, static mut, unions, MaybeUninit, or any other Rust feature if it makes things faster. Correctness is verified by the eval — if it passes all puzzles, it's valid. You may also modify Cargo.toml for compiler settings (LTO, codegen-units, target-cpu, panic mode) — just no external crate dependencies.

There is no line count limit. A 500-line SIMD solver that runs in 20µs beats a 50-line scalar solver that runs in 300µs. Optimize for the number.

Think beyond this list. These ideas are starting points, not boundaries. The best breakthroughs come from connecting techniques across fields. What if you combined SAT solver propagation with SIMD bitboards? What if constraint propagation was structured as a dataflow graph? What if you precomputed partial solutions for common subgrid patterns and stitched them together? What if the board representation itself was the bottleneck and a completely alien encoding — one nobody has tried — could unlock a faster path?

You have access to the entire Rust language, the entire CPU instruction set, and unlimited creativity. Read your own code. Stare at the hot loop. Ask yourself: what is the CPU actually doing cycle by cycle, and what is it wasting time on? Every branch, every cache miss, every redundant computation is an opportunity.

Be fearless

Nothing is too complex. Nothing is too radical. If a complete rewrite of the entire solver from scratch gives a faster time, do it. If it takes 800 lines of SIMD intrinsics, do it. If it means throwing away everything that currently works and starting over with a band-level bitboard architecture, do it.

Complexity does not matter. Line count does not matter. Readability does not matter. The only thing that matters is the number going down.

Do not be cautious. Do not play it safe. Do not make small tweaks when a big architectural leap is available. If you have been making incremental improvements for 10+ experiments and gains are shrinking, that is a signal to try something fundamentally different — a new representation, a new algorithm, a new paradigm.

Fear of breaking what works is the enemy of progress. You have git. You have snapshots. If a radical rewrite fails, you revert and lose nothing. If it succeeds, you leap past the ceiling.

Try things from completely different angles: template intersection, band bitboards, SIMD propagation, SAT solver techniques, exact cover, dataflow constraint networks, approaches that have never been combined before.

The only aim is to be superior by heavy margins. Do not stop even after achieving that — there is always something faster.

The hard puzzles are where the big wins are. A solver that's 10× faster on the hardest puzzles but the same on easy ones will still show a massive total improvement.

Now continue. The human is away. You are autonomous. Run until manually interrupted. Never stop.