Sudoku puzzles consist of a $9 \times 9$ grid of cells in which some cells contain integers from the set $\{ 1, \ldots, 9 \}$ and the task is to fill in the remaining cells such that the numbers $1$ through $9$ appear in each row, in each column, and in each of the nine $3 \times 3$ boxes, as shown in this puzzle and its solution:

The solutions are also called Latin squares, and one estimate of the number of distinct $9 \times 9$ such Latin squares is $N = 6,670,903,752,021,072,936,960$.

I am interested in finding the minimum-information description of such a solution by describing the minimal puzzle that leads to that unique solution. Of course such a solution has a very large number of constraints, which reduces the information needed to describe its source puzzle. In information theoretic terms, one need merely describe (or transmit) the minimal puzzle; the receiver can then solve the puzzle to fill in the full Latin square.

In a tour de force simulation taking the equivalent of $7.3M$ hours on a supercomputer, Gary McGraw, Bastian Tugemann and Giles Civario solved a long-outstanding problem: finding that the minimal number of puzzle cells needed to be filled to ensure a unique sudoku solution was 17 (as exemplified in the figure above). No $16$-clue puzzles exist.

A lower-bound on the information needed to describe such a puzzle would assume that the grid locations for the $17$ clues are fixed (and hence contribute zero bits to the description), and that all one need do is fill in the $17$ puzzle cell values. One might assume the maximum entropy set such as ${\cal S} = \{ 1,1,2,2,3,3,\ldots,8,8,9 \}$, i.e., one instance of a single digit, and two copies of each remaining digit. Thus it takes $\log_2 9 = 3.16993$ bits to describe which is the "lone" or "singleton" digit. Then the creation of the puzzle corresponds to placing the 17 digits of ${\cal S}$ in the $17$ (assumed fixed) cells, thus requiring $\log_2 \left({{17 \choose 9} \over (2!)^8} \right) = 6.56926$ bits, so the total number of bits is: $3.16993 + 6.56926 = 9.73919$ bits. (Note that this is much lower than the naive estimate of $\log_2 N = 72.4984$ bits.)

I suspect this estimate is a loose lower bound because (perhaps) not all puzzles can be described by $17$ cell values, that even if one could use just $17$ such values the cell locations might need to differ (and hence require information to describe these locations), and other factors.

I don't expect someone to solve this problem fully on this site--it simply requires too much analysis and likely massive computer simulations. What I would appreciate are comments/criticisms on the casting of this problem and its assumptions, and a clear methodological approach toward solving it rigorously.