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! \over (2!)^8} \right) = 40.3376$ bits, so the total number of bits is: $3.16993 + 40.3376 = 43.5075$ 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. Moreover, as @ZachTeitler pointed out, many of the assignments of digits to cells will lead to unsolvable puzzles (because, for example, there will be two equal digits in the same row, or column, or $3 \times 3$ box).
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.
