This project helps to solve sudoku in the fastest way. It takes about 20us = 0.00002s (on intel i7 3rd gen x86_64) to solve the world hardest sudoku (According to the British newspaper The Telegraph) Article Description
- Create SudokuField structure
SudokuField<9> field;
- Insert each known numbers using
insert_number()
method or callparse()
forwarding the entire schema
// "0" is invalid number and means no data
static constexpr auto sudoku = []() {
return std::array{
std::array<value_type, 9>{ 8 },
std::array<value_type, 9>{ 0, 0, 3, 6 },
std::array<value_type, 9>{ 0, 7, 0, 0, 9, 0, 2 },
std::array<value_type, 9>{ 0, 5, 0, 0, 0, 7 },
std::array<value_type, 9>{ 0, 0, 0, 0, 4, 5, 7 },
std::array<value_type, 9>{ 0, 0, 0, 1, 0, 0, 0, 3 },
std::array<value_type, 9>{ 0, 0, 1, 0, 0, 0, 0, 6, 8 },
std::array<value_type, 9>{ 0, 0, 8, 5, 0, 0, 0, 1 },
std::array<value_type, 9>{ 0, 9, 0, 0, 0, 0, 4 }
};
}();
field.parse(sudoku);
- Call
solve()
method
field.solve();
- Print the result as table
field.print_as_table();
It prints:
8 6 4 | 2 7 1 | 9 5 3
9 2 3 | 6 5 4 | 8 7 1
1 7 5 | 8 9 3 | 2 4 6
----------------------
2 5 2 | 3 8 7 | 1 9 4
6 1 9 | 3 4 5 | 7 8 2
4 8 7 | 1 2 9 | 6 3 5
----------------------
7 4 1 | 9 3 2 | 5 6 8
7 4 8 | 5 6 2 | 3 1 9
5 9 6 | 8 3 1 | 4 2 7
field_type
is the array of bitset which represents which numbers can be writen in that cell. (Ex: 0b011100010
= [1, 5, 6, 7, 8], 0b0100000000
= only "8").
insert_number insert the number in the specific cell and clears that number from all other cells in the same row, same column and the same square. solve()
tries to find the cell with minimum contended number. Then tries to insert sequentially each of numbers and tries to solve sudoku (recursively). When the correct combination found, it stops.
To check if a cell is complete (only one bit is 1) the function calls c++20 std::popcount
which is likely translated in assembly instruction avoiding loops. The same approach is used to determine the position of bit one, in this case is called std::countr_zero
.