A Sudoku solver that uses human strategies.
- Naked singles, pairs, triples, and quads
- Hidden singles, pairs, triples, and quads
- Unit intersections (a.k.a. pointing pairs and box+line reductions)
- X-wings, swordfish, and jellyfish
- Y-wings (a.k.a. XY-wings) and XYZ-wings
- 3D Medusas (a generalization of simple coloring)
- Dual Medusas (3D Medusas that start with a bi-location candidate in a unit instead of a bi-value cell)
- Bi-value cell forcing chains
- Dual unit forcing chains
- Nishio forcing chains
- Anti-Nishio forcing chains (Nishio forcing chains that start with a candidate digit off instead of on)
- Subset exclusion (incomplete)
- Guessing individual cells (with the
-g
flag enabled)
These strategies are insufficient to solve all boards without guessing. My intention is to automate the strategies that I fully understand, since at that point doing them myself is just busy work.
So far it can solve 99.5% of these 49,151 17-hint Sudoku (only 266 are unsolvable). With the puzzles chosen by Peter Norvig, it can solve all 50 of the easy ones, 64 of the 95 hard ones, and 9 of the 11 hardest ones. However, all of the AI Sudoku Top 10 are unsolvable. (With guessing, all boards are solvable.)
./sudoku.py BOARD
Solves the given board and shows steps.
e.g../sudoku.py 000000001000000020000003000000040500006000300007810000010020004030000070950000000
./sudoku.py -f FILE
Solves each board in the given file and outputs a TSV summary.
e.g.stdbuf -oL ./sudoku.py -f boards.txt > solutions.tsv
./sudoku.py -q BOARD
Solves the given board without printing anything. Useful for measuring performance.
e.g.time ./sudoku.py -q 000000001000000020000003000000040500006000300007810000010020004030000070950000000
./sudoku.py -g BOARD
or./sudoku.py -g -f FILE
Solves the given board or file with guessing enabled.
e.g../sudoku.py -g 000000001000000020003004000000003500010060000720000080000108000000720000900000600