This repository contains the code for a "human-like" Sudoku solver. This solver does not do any guessing (no backtracking) and only employs solving techniques used by human solvers.
The ultimate goal is to build a high-performance solver that can be used as a tool to help generate interesting Sudoku puzzles.
If you have any questions about the code, join me for one of the streams, every Sat&Sun 14:30 CE(S)T at Youtube or Twitch.
The UI for this solver lives in the sudoku_ui repository and you can test the current build in the sudoku_playground repository.
The video & audio quality improves over time and I'm continually making improvements.
- 2020/05/09 Basic backtracking solver (bad sound quality)
- 2020/05/10 Diagonal sudoku support
- 2020/05/16 Working on pruning support
- 2020/05/17 Backtracking with pruning working
- 2020/05/23 Trying to crack 16x16 Sudokus
- 2020/05/24 Non-backtracking solving: sets, block intersections, fish rules
- 2020/05/30 Integration with CI & code cleanup
- 2020/05/31 Code cleanup
- 2020/06/06 Integrating solver stats, fixing warnings
- 2020/06/07 Debugging & integrating a benchmark dataset
- 2020/06/13 Finned fish rules
- 2020/06/14 Finned fish rules
- 2020/06/20 Looking at performance
- 2020/06/21 Optimizing the solver
- 2020/06/27 Optimizing the solver
- 2020/06/28 Optimizing the solver
- 2020/07/04 Solving the last 1% of puzzles
- 2020/07/05 Solving the last 1% of puzzles (audio missing in first 30 minutes)
- 2020/07/11 Looking at the performance again
- 2020/07/12 UI: Fruitlessly trying to make Emscripten work
- 2020/07/18 UI: First UI results with asm-dom
- 2020/07/19 UI: Connecting the solver with the UI
- 2020/07/25 UI: Storing the puzzle data in the URL
- 2020/07/26 UI: Adding buttons & candidate notation
- 2020/08/01 Initial attempts at Killer Sudoku
- 2020/08/02 Refactoring code for simplicity & C++20 Part 1
- 2020/08/08 Refactoring code for simplicity & C++20 Part 2
- 2020/08/09 Refactoring code for simplicity & C++20 Part 3
- 2020/08/15 Refactoring code for simplicity & C++20 Part 4
- 2020/08/16 Refactoring code for simplicity & C++20 Part 5
- 2020/08/22 Refactoring code for simplicity & C++20 Part 6
- 2020/08/23 Refactoring code for simplicity & C++20 Part 7
- 2020/08/29 Compile time datastructure for Killer Sudoku support
- 2020/08/30 Initial Killer Sudoku support
The following data set is used for the benchmark: https://www.kaggle.com/rohanrao/sudoku
Benchmark results: Solved 8985618 out of 9000001 requested.
Out of the solved 0 were determined to be incorrect
Solver stats {
Groups: (1 : 34489883)(2 : 146932)(3 : 6688)(4 : 116)
Intersections: 95846
XYChains: 85937
Fish rules:
X-Wing : 22540
Swordfish : 2483
Jellyfish : 43
Finned Fish rules:
Finned X-Wing : 5660
Finned Swordfish : 1416
Finned Jellyfish : 314
Finned Squirmbag : 18
XChains rules:
XChain of size 4 : 91131
XChain of size 6 : 6059
XChain of size 8 : 303
XChain of size 10 : 3
};