Logic-based Sudoku Solver

sudoku

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.

Stream archive

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

Current Benchmark results

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
};