⚡ Autoresearch Sudoku Solver

An AI agent beat the world's #1 and #2 sudoku solvers — in 312 experiments, ~24 hours, with zero human-written solver code.

Results • Journey • How It Works • program.md • Reproduce • Full Writeup

---

What is this?

An AI coding agent (Claude Code), running an enhanced version of Andrej Karpathy's autoresearch pattern, autonomously built a sudoku solver in Rust that beats both Tdoku (#1 since 2019) and rust_sudoku (#2) on 4 out of 6 standard benchmark datasets.

Same hardware. Same compiler flags. 748,767 puzzles. 5 runs each. No tricks. The entire autonomous process was driven by a single file — src/program.md — which defined the rules, targets, and strategies the agent followed.

---

📊 Results

Head-to-head benchmark (same hardware, same flags)

Dataset	Puzzles	RKCR7 (AI)	Tdoku	rust_sudoku	Winner
Kaggle (easy)	100,000	0.81 µs	0.80 µs	1.11 µs	Tdoku by 1%
17-clue (medium)	49,158	1.60 µs	2.30 µs	1.85 µs	RKCR7 by 16%
MagicTour (hard)	1,465	5.14 µs	6.70 µs	8.11 µs	RKCR7 by 30%
Hard 11+ (main)	48,766	24.92 µs	37.10 µs	45.34 µs	RKCR7 by 49%
Hard 1106 (hardest)	375	30.35 µs	58.70 µs	82.26 µs	RKCR7 by 93%
Generated (trivial)	500,003	0.32 µs	0.20 µs	0.59 µs	Tdoku by 60%

Scorecard: RKCR7 4/6 · Tdoku 2/6 · rust_sudoku 0/6

Key takeaways

• The harder the puzzle, the bigger the margin. On the main leaderboard dataset (Hard 11+), RKCR7 is 49% faster than Tdoku and 82% faster than rust_sudoku. On the hardest puzzles known to humanity (1106), the gap widens to 93% and 171%.
• Kaggle is essentially tied (0.81 vs 0.80 µs — within measurement noise on 100K puzzles).
• Tdoku wins only trivial puzzles where its SIMD triad propagation solves without any backtracking.
• rust_sudoku wins zero datasets despite being compiled with identical flags plus unchecked_indexing.

Test conditions

Parameter	Detail
CPU	AMD Ryzen 9 8940HX (Zen 4, AVX-512, 5.3GHz boost)
Laptop	ASUS TUF Gaming A16 FA608PP (2025)
RAM	16 GB DDR5
OS	Windows 11
RKCR7 flags	Rust, lto=true, codegen-units=1, panic=abort, strip=true, target-cpu=znver4
rust_sudoku flags	Same as RKCR7 + features=["unchecked_indexing"]
Tdoku flags	MSYS2 GCC (ucrt64), -O3 -march=znver4, CMake Release
Runs	5 per solver per dataset, sequential blocks, best of 5 reported
Verification	Hardware verified via wmic and Get-CimInstance — see log

---

🚀 The Journey

312 experiments. 65,275x speedup. Two phases.

Phase 1: 20-puzzle autoresearch (255 experiments, ~24 hours)

The agent started from a naive recursive backtracker (6.4 seconds for 20 puzzles) and, through 255 autonomous experiments, discovered increasingly sophisticated techniques:

Exp	µs (20 puz)	Speedup	What changed
#1	6,462,257	1x	Baseline: naive backtracking
#2	187,820	34x	Bitmask constraints + MRV + naked singles
#3	2,113	3,059x	Hidden singles in rows/cols/boxes
#25	524	12,333x	OR-accumulation hidden singles
#100	205	31,523x	Constraint-density MRV tie-breaking
#143	192	33,657x	REWRITE: single struct, contiguous memcpy
#184	170	38,013x	AVX2 batch naked singles
#189	161	40,139x	AVX-512 popcnt + SIMD MRV
#233	104	62,137x	REWRITE: JCZSolve band solver (46% speedup!)
#243	99	65,275x	Unsafe unchecked + loop restructure — SUB-100!!!

The agent independently re-derived every major sudoku solving technique — constraint propagation, hidden singles, locked candidates, OR-accumulation, SIMD vectorization, and band-oriented data structures — techniques the human sudoku community developed over decades.

Phase 2: Real benchmark optimization (57 experiments, ongoing)

Switched evaluation from 20-puzzle toy set to the official tdoku benchmark suite (748,767 puzzles across 6 difficulty levels). The agent continued optimizing with a much lower keep rate (18%) — expected at this performance level.

Notable Phase 2 moments:

• Exp #14: Attempted FSSS2-style digit bitboard — 6x slower, reverted (brave attempt!)
• Exp #38: Attempted Tdoku SIMD port — crashed due to shuffle table bug (fearless!)
• Exp #41: inline(always) on guess_bivalue — current best on hard puzzles
• Exp #47: Novel hidden bivalue ordering — discovered a new technique

Statistics

Metric	Phase 1	Phase 2	Total
Experiments	255	57	312
Kept	66 (26%)	10 (18%)	76 (24%)
Discarded	180	42	222
Crashed	9	5	14
Architecture rewrites	4	2 attempted	6
Duration	~24 hours	~3 hours	~24 hours

---

🧠 How It Works

The autoresearch pattern (enhanced)

Karpathy's autoresearch is a pattern where an AI agent gets a measurable objective and iterates autonomously: hypothesize → edit code → benchmark → keep or revert → repeat.

Before touching any solver code, I (Ritik) enhanced this pattern by:

1. Building a 3,000+ line autoresearch guide through multiple rounds of deep research — a domain-agnostic operating manual that teaches AI agents how to autonomously optimize anything with a measurable metric. The guide auto-generates src/program.md, the single most important file in this project — it defines the optimization rules, evaluation methodology, hardware specs, strategy hints, fair-play constraints, and the autonomous experiment loop the agent follows. This file was updated 8–10 times throughout the journey as the process evolved.
2. Designing a two-phase evaluation system — fast 20-puzzle iteration for Phase 1, real benchmark datasets for Phase 2.
3. Setting deliberately unreachable targets (written into program.md) to prevent the agent from settling into local optima.

Human involvement: light guidance, not hand-holding

The human role was closer to a research advisor than a programmer:

• Built the 3,000+ line autoresearch guide which auto-initialized program.md, solver template, and datasets
• Checked in periodically on progress
• Updated program.md 8–10 times throughout the process — adding new benchmark datasets, setting harder targets, tweaking strategy hints, and transitioning from Phase 1 to Phase 2 evaluation
• Nudged the agent when it got conservative ("be fearless, rewrite everything")
• Set up benchmark infrastructure (bench.sh, bench.rs)

Every line of solver code was written by the agent. Every architectural decision, every experiment, every rewrite.

The solver architecture

The final solver (src/solver.rs) is 709 lines of Rust:

• Data representation: 27 × u32 subband masks (9 digits × 3 bands), 240-byte struct fitting in 4 cache lines
• Propagation: Locked candidates via precomputed 512-entry LUTs, OR-accumulation naked singles, column-based cross-band elimination
• Change detection: prev_poss_cells[27] skips unchanged subbands — eliminates redundant work
• Search: Bivalue-first guessing (cells with exactly 2 candidates), MRV fallback
• Optimizations: unsafe get_unchecked, macro-unrolled 27-subband loop, BMI1/BMI2 target features, careful inline(always) vs inline(never)

Why it wins

Advantage	Effect
Change detection via prev_poss_cells	Skips unchanged subbands — huge on easy puzzles
Band-level data layout	27 cells per bitwise operation instead of 1
Bivalue guessing + MRV fallback	Minimizes search tree size
240-byte state struct	Fast copy on branch, fits in cache
Manual unrolling + inline control	Better icache behavior than library-based iteration

Tdoku wins trivial puzzles because its SIMD triad propagation has lower per-puzzle overhead when zero backtracking is needed. RKCR7 wins everything else because its lighter state representation and change detection make search more efficient.

---

🔬 Reproduce

Quick start

# Clone
git clone https://github.com/Rkcr7/autoresearch-sudoku
cd autoresearch-sudoku

# Build (requires Rust nightly for target-cpu)
cargo build --release

# Run against a puzzle file (one puzzle per line, 81 chars)
cat your_puzzles.txt | ./target/release/bench

Get the benchmark datasets

The bench_data/ folder ships empty — you need to download the official datasets from the tdoku benchmark suite. See bench_data/README.md for full details, or run:

# Clone tdoku (only need the data/ folder)
git clone --depth 1 https://github.com/t-dillon/tdoku.git /tmp/tdoku

# Copy the 6 datasets
cp /tmp/tdoku/data/puzzles0_kaggle                    bench_data/
cp /tmp/tdoku/data/puzzles2_17_clue                   bench_data/
cp /tmp/tdoku/data/puzzles3_magictour_top1465          bench_data/
cp /tmp/tdoku/data/puzzles5_forum_hardest_1905_11+     bench_data/
cp /tmp/tdoku/data/puzzles6_forum_hardest_1106         bench_data/
cp /tmp/tdoku/data/puzzles8_gen_puzzles                bench_data/

Each file contains one puzzle per line (81 characters, 0 or . for empty cells):

File	Puzzles	Difficulty	What it tests
puzzles0_kaggle	100,000	Easy	Pure propagation, zero backtracking
puzzles2_17_clue	49,158	Medium	Minimal-clue, propagation efficiency
puzzles3_magictour_top1465	1,465	Hard	Classic benchmark since 2006
puzzles5_forum_hardest_1905_11+	48,766	Extreme (SE 11+)	THE main leaderboard dataset
puzzles6_forum_hardest_1106	375	Hardest known	Hardest puzzles known to humanity
puzzles8_gen_puzzles	500,003	Trivial	Generated, trivial difficulty

Run the benchmark

# Run against all 6 datasets
bash bench.sh

# Or run against a single dataset
cat bench_data/puzzles5_forum_hardest_1905_11+ | ./target/release/bench

# Or point to a custom data directory
bash bench.sh /path/to/your/data

Benchmark against Tdoku and rust_sudoku

To reproduce the full head-to-head comparison:

1. Build rust_sudoku — git clone https://github.com/Emerentius/sudoku.git and build with cargo build --release --features unchecked_indexing plus matching flags (lto, codegen-units=1, panic=abort, target-cpu=native)
2. Build Tdoku — git clone https://github.com/t-dillon/tdoku.git, then mkdir build && cd build && cmake .. -DCMAKE_BUILD_TYPE=Release && make. For fair comparison, add -march=native to CMAKE_CXX_FLAGS.
3. Run all three against the same datasets, 5 runs each, take best of 5.

See the benchmark log for the exact commands and hardware verification used in our benchmark.

Run autoresearch yourself

The autoresearch framework is designed to work on any optimization task — not just sudoku. See the autoresearch-guide repo for the complete 3,000+ line methodology, universal templates, and 5 ready-to-use examples (Python perf, LLM prompts, Docker images, Nginx configs, and more).

1. Create a git repo with your code + evaluation script
2. Write a program.md — this is the file that drives everything. Study our src/program.md as a reference; it defines the experiment loop, targets, constraints, and strategy hints
3. Point Claude Code at it: "Read program.md and start the experiment loop. Don't stop."
4. Walk away. Check in periodically, update program.md as the process evolves (we updated ours 8–10 times)

---

📁 Repository Structure

autoresearch-sudoku/
├── README.md                          ← You are here
├── LICENSE
├── bench_data/
│   └── README.md                      ← Put tdoku dataset files here (ships empty)
├── src/
│   ├── solver.rs                      ← The 709-line solver (all AI-written)
│   └── program.md                     ← Autoresearch prompt & rules for the AI agent (updated 8–10× during experiments)
├── images/
│   ├── benchmark_chart.png            ← Bar chart: 3 solvers × 5 datasets
│   ├── comparison_table.png           ← Head-to-head results table
│   ├── headline_numbers.png           ← Key numbers summary
│   ├── phase1_journey.png             ← Phase 1 milestone progression
│   └── phase2_optimization.png        ← Phase 2 experiment highlights
├── results/
│   ├── benchmark_definitive.tsv       ← Raw data: 90 runs (3×6×5)
│   ├── benchmark_6datasets_90runs.log ← Full benchmark log with HW verification
│   ├── phase1_255_experiments.tsv     ← All 255 Phase 1 experiments
│   └── phase2_57_experiments.tsv      ← All 57 Phase 2 experiments
├── spreadsheets/
│   ├── sudoku_benchmark_definitive.xlsx ← Formatted benchmark results
│   └── sudoku_full_story.xlsx         ← Complete journey + all 312 experiments
└── docs/
    ├── FULL_WRITEUP.md                ← Detailed technical writeup

src/program.md is the living "brain" of the autoresearch loop — it defines the optimization rules, targets, strategy hints, and hardware specs that the AI agent follows autonomously. This file was iteratively refined 8–10 times during the 312-experiment journey as evaluation methodology evolved (e.g., switching from 20-puzzle eval to real benchmark datasets) and new targets were set.

---

🔗 References

Resource	Link
The Autoresearch Guide (3,000+ line methodology)	github.com/Rkcr7/autoresearch-guide
Tdoku (the #1 solver we beat)	github.com/t-dillon/tdoku
rust_sudoku (the #2 solver we beat)	github.com/Emerentius/sudoku
Tdoku benchmark datasets	tdoku/data
Karpathy's autoresearch concept	REPO
Claude Code	docs.anthropic.com
JCZSolve (algorithm family)	Enjoy Sudoku Forum
Tdoku published benchmarks (i5-8600K)	tdoku/benchmarks

---

📈 Detailed Data

Raw experiment data

• Phase 1: 255 experiments — 20-puzzle eval, ~24 hours. Tab-separated: commit, duration_us, status, description.
• Phase 2: 57 experiments — Real benchmarks, ongoing. Tab-separated: commit, hard11, magic, hard1106, 17clue, kaggle, status, description.
• Final benchmark: 90 runs — 3 solvers × 6 datasets × 5 runs. Tab-separated: solver, dataset, label, run, usec_per_puzzle, puzzles_per_sec.

Spreadsheets

• sudoku_benchmark_definitive.xlsx — Formatted leaderboard, raw data, statistics, methodology
• sudoku_full_story.xlsx — Complete journey: leaderboard + Phase 1 milestones + Phase 2 experiments + all 90 benchmark runs + methodology

Benchmark log

The benchmark log includes:

• Hardware verification commands (wmic computersystem, Get-CimInstance Win32_Processor)
• All 90 individual run outputs
• Exact solver binaries and paths used

---

🏆 Summary

Metric	Value
Total experiments	312
Total speedup (Phase 1)	65,275x
Datasets won (vs Tdoku + rust_sudoku)	4 / 6
Main leaderboard (Hard 11+)	24.92 µs — 49% faster than #1
Hardest puzzles (1106)	30.35 µs — 93% faster than #1
Solver size	709 lines of Rust
Human-written solver code	0 lines
Duration	~24 hours

---

Built by Ritik using Claude Code and an enhanced autoresearch framework. March 2026.

The human built the framework and guided the process. The AI wrote every line of code.