Sudoku is a combinatorial number placement puzzle. The objective is to fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 sub-grids that compose the grid contains all of the digits from 1 to 9.
The puzzle setter provides a partially completed grid.
- A Sudoku puzzle is proper if it has exactly one solution.
- A Sudoku puzzle is irreducible if no clue can be removed leaving it a proper Sudoku.
- Two Sudokus puzzles are equivalent if one can be converted into the other through rotation, reflection, permutation, and relabelling
- A Sudoku puzzle is normal if it is the lexiographic smalest among all equivalent Sudoku puzzles
- There are 6.67e21 different solved Sudokus generated by 5.47e9 normal solved Sudokus.
- There are about 3.10e37 proper irreducible Sudoku puzzles generated by about 2.55e25 proper irreducible normal Sudoku puzzles.
- The fewest clues possible for a proper Sudoku is 17.
- The maximum clues possible for am irreducible Sudoku is not known, irreducible instances with 40 clues have been found.
In principle the Sudoku puzzles can be solved by iteratively filling the grid and backtracking whenever violating one of the constraints.
To achieve a useful solution speed, the constraints have to be considered while filling the grid, using constraint programming.
Sudoku is an exact cover problem which can be solved with the Algorithm X.
There is a well-established format for Sudokus (both puzzles and solutions): The rows are written as a continuous string of ASCII digits, resulting in 82 characters per Sudoku (including the end-of-line character), e.g.:
.......1..32....7.9.1.7...6.....5..81.8.9..6..4......9........1...2.....8.7.1.6..
(Sometimes empty cells are represented by 0 rather than .)
sudoku-5000000-normal contains 5000000 proper irreducible normalised Sudoku
puzzles collected from various sources, as well as generated instances. It
contains 50693 puzzles with 17 clues, 2684 puzzles with 39 clues, 4 puzzles with
40 clues, and many extremely difficult puzzles. The instances are sorted by
solving time with 2 different implementations, in descending order.
To build a testset of 100000000 instances, every puzzle from the above file is replaced with 20 different permutations, which are then equally distributed, by issuing:
make sudoku-1000000
Solvers can be build with
make solver-x-pt solver-a-pt
The fastest solver, solver-x-pt, can solve these Sudoku puzzles in on average
- 2155ns on an Intel Core i7-9700K
- 835ns on an Intel Xenon Gold 5118