Specifying any arbitrary 9x9 grid requires giving the position and value of each square. A nave encoding for this might give 81 (x, y, value) triplets, requiring 4 bits for each x, y, and value (1-9 = 9 values = 4 bits) for a total of 81x4x3 = 972 bits. By numbering each square, one can reduce the positional information to 7 bits, dropping a bit for each square and a total of 891 bits. By specifying a predetermined order, one can reduce this more drastically to just the 4 bits for each value for a total of 324 bits. However, a sudoku can have missing numbers. This provides the potential for reducing the number of numbers that have to be specified, but may require additional bits for indicating positions.  Using our 11-bit encoding of (position, value), we can specify a puzzle with $n$ clues with $11n$ bits, e.g. a minimal (17) puzzle requires 187 bits.  The best encoding I've thought of so far is to use one bit for each space to indicate whether it's filled and, if so, the following 4 bits encode the number. This requires $81+4n$ bits, 149 for a minimal puzzle ($n=17$). Is there a more efficient encoding, preferably without a database of each valid sudoku setup? (Bonus points for addressing a general $n$ from $N \times N$ puzzle)It just occurred to me that many puzzles will be a rotation of another, or have a simple permutation of digits.  Perhaps that could help reduce the bits required.  According to Wikipedia, The number of classic 99 Sudoku solution grids is 6,670,903,752,021,072,936,960 (sequence A107739 in OEIS), or approximately $6.67×10^{21}$.If I did my math right ($\frac{ln{(6,670,903,752,021,072,936,960)}}{ln{(2)}}$), that comes out to 73 (72.498) bits of information for a lookup table.But:The number of essentially different solutions, when symmetries such as rotation, reflection, permutation and relabelling are taken into account, was shown to be just 5,472,730,538[15] (sequence A109741 in OEIS).That gives 33 (32.35) bits, so it's possible that a clever method of indicating which permutation to use could get below the full 73 bits.
Efficient encoding of sudoku puzzles
combinatorics;modelling;information theory;sudoku