A fast Sudoku game solver, it deals with puzzles of any size (e.g. 4x4, 9x9, 16x16, etc.).

It solves 3 million 9x9 puzzles in 5 minutes using single thread. Refer to this kaggle kernel for more details.

Build with size 9 (default):

make target -j SIZE=9

Then run with:

./bin/sudoku solve -i puzzles/1.txt     # solve a puzzle
./bin/sudoku generate -c 24             # generate a puzzle with 24 clues

Run benchmarks on included puzzles (time varies depending on difficulties):

> ./bin/benchmark
Benchmarking 3 puzzles with 100 repeats...
Puzzle 1:    5 [us]
Puzzle 2:   12 [us]
Puzzle 3:   74 [us]

Run on larger datasets.

You can get the datasets from:

1. maxbergmark/sudoku-solver
2. goomii17/16X16-Sudoku-Dataset

Below are some benchmark results on my machine (Mac mini M4):

> ./bin/benchmark ~/repo/sudoku-dataset/hard_sudokus.txt
Finished on 10000 cases
Success rate: 100%
Mean time: 21 [us]
Median time: 19 [us]
1st quartile time: 15 [us]
3rd quartile time: 25 [us]
Average guesses: 1.6563
Median guesses: 2

> ./bin/benchmark ~/repo/sudoku-dataset/all_17_clue_sudokus.txt
Finished on 49151 cases
Success rate: 100%
Mean time: 29 [us]
Median time: 23 [us]
1st quartile time: 19 [us]
3rd quartile time: 31 [us]
Average guesses: 3.91835
Median guesses: 3

> ./bin/benchmark ~/Downloads/16x16Dataset.csv
Finished on 3000 cases
Success rate: 100%
Mean time: 253 [us]
Median time: 120 [us]
1st quartile time: 85 [us]
3rd quartile time: 152 [us]
Average guesses: 19.5367
Median guesses: 0

Build with pybind11:

SIZE=9 pip install ./bindings
python demo.py -c 24    # generate and solve a puzzle with 24 clues

---

Environment variables:

• SOLVER_USE_GUESS enable guessing when solving the puzzle. Default is 1.
• SOLVER_HEURISTIC_GUESS enable heuristic choosing of starting cell when guessing. Default is 1.
• SOLVER_DETERMINISTIC_GUESS enable deterministic solving. Default is 0.
• SOLVER_USE_XWING enable X-Wing solving. Default is 0.
• SOLVER_USE_DOUBLE enable naked/hidden double solving. Default is 0.