Note: This is about the standard 9x9 sudoku puzzle. The solution only has to support solved, legal puzzles. So a solution doesn't need to support empty cells and can rely on the properties of a solved sudoku puzzle.I was wondering this, but I couldn't think of an answer that I was content with. A naive solution would use one byte for each cell (81 cells), totalling 648 bits. A more sophisticated solution would store the entire sudoku puzzle in a base-9 number (one digit per cell) and require $\lceil\log_2(9^{81}))\rceil = 257$ bits.But it can still be improved, for example, if you know 8 of the 9 numbers in a 3x3 subgrid you can trivially deduce the 9th. You can continue these thoughts to the point where this question boils down to What is the amount of unique solved sudokus? Now you can use a huge lookup table that maps each binary number to a sudoku puzzle, but that wouldn't be an usable solution.So, my question:Without using a lookup table, what is the minimum amount of bits required to store a sudoku puzzle and with what algorithm?
What is the minimum number of bits required to store a sudoku puzzle?
co.combinatorics;puzzles