1
$\begingroup$

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:

Minimal sudoku puzzle and 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.

$\endgroup$
  • 3
    $\begingroup$ You might enjoy reading this old question and its answers: mathoverflow.net/questions/129143 $\endgroup$ – j.c. Oct 23 '18 at 22:23
  • $\begingroup$ Suppose I give you k bits of information to represent a Sudoku solution. If k is less than log_2 N, how would I use k bits or fewer to distinguish each of the other N-1 solutions? Are you asking about equivalence classes of solutions instead? Gerhard "Finds The Question Itself Puzzling" Paseman, 2018.10.24. $\endgroup$ – Gerhard Paseman Oct 24 '18 at 17:59
  • $\begingroup$ 1. Can you please explain where $\binom{17}{9}/(2!)^8$ comes from? The number of ways to put $1,1,2,2,\dotsc,8,8,9$ into $17$ squares is $17!/(2!)^8$. If you allow a choice of which digit is the "odd" one ($9$) then you get $9 \cdot 17!/(2!)^8$. Have I misunderstood what you are counting? 2. Presumably the large majority of placements into those $17$ squares fail to uniquely determine a puzzle solution. Either they admit more than one solution (failure of uniqueness) or they admit no solutions — e.g., if the $17$ clue squares have a duplicated digit in a row, column, or region. ... $\endgroup$ – Zach Teitler Oct 24 '18 at 18:53
  • $\begingroup$ ... counting these seems like a challenge, to put it mildly. It will certainly depend on which $17$ squares are chosen for the clue locations. E.g., if the $17$ squares are the first row and first column, then very, very few clue fillings will uniquely determine puzzle solutions! $\endgroup$ – Zach Teitler Oct 24 '18 at 18:54
  • $\begingroup$ @ZachTeitler: My guess/ansatz was that a unique selection of 17 cell locations might uniquely determine all sudoku puzzles, but that set would be arranged like the set in my example, certainly not a row and a column. (Frankly, that would be one of the least constraining arrangements. $\endgroup$ – David G. Stork Oct 24 '18 at 19:07

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.