6
$\begingroup$

I was reading McGuire's paper on why the minimum number of clues in a Sudoku puzzle is 17 when I came across a curious comment:

In 2008, a 17-year-old girl submitted a proof of the nonexistence of a 16-clue sudoku puzzle as an entry to Jugend forscht (the German national science competition for high-school students). She later published her work in the journal Junge Wissenschaft (No. 84, pp. 24–31). However, when Sascha Kurz, a mathematician at the University of Bayreuth, Germany, studied the proof closely, he found a gap that is probably very difficult, if not impossible, to fix.

I was able to find the work he was referring to (I think) here. Not knowing German or anyone who speaks German, I had to settle and read a machine translation of the paper, which wasn't very good. By my understanding, the proof went along the lines of this:

We start out by expanding the grid into 3D space with a $9$ by $9$ by $9$ cube, and for each square of the puzzle, we place a 1 in the n'th cube from the front and zeros everywhere else behind the square. So for example if we have a 5 in a square of the puzzle, all cubes behind that specific square of the puzzle will contain the number zero except the 5th one, which will contain a 5. We can then create sets of equations with variables which represent the values inside the cubes, and these equations represent the different constraints of Sudoku. Finally, we consider an "optimal" configuration of 16 clues which will eliminate as many variables as possible and we find that there are not enough equations to solve for every variable, meaning that a solution to the puzzle wouldn't be unique if it had 16 clues.

With all of this being said, I can't seem to find the gap which McGuire mentions. To me, the idea of finding an "optimal" configuration does seem a little bit hand wavy, but at the same time the logic does seem sound. I've looked around to see if Sascha Kurz had published something about the matter, but I can't seem to find anything and not knowing German only worsens my predicament. Is the gap something much more subtle, for example a simple miscount, or is it something else? What is the gap in Papke's proof?

$\endgroup$

1 Answer 1

4
$\begingroup$

The argument

The argument goes essentially this way (reformulated with standard notation):

We model the sudoku by an integer linear program. For all $1\leq i, j, k \leq 9$, we define:

$$x_{i, j, k} = \begin{cases} 1 &\text{ if there is a value } k \text{ in the cell } (i, j)\\ 0 &\text{ else } \end{cases}$$

This gives $9^3=729$ variables.

We define the following families of constraints: $$\sum_{i=1}^9 x_{i, j, k} = 1 ~~~~\forall \;1\leq j, k \leq 9$$ $$\sum_{j=1}^9 x_{i, j, k} = 1 ~~~~\forall \;1\leq i, k \leq 9$$ $$\sum_{k=1}^9 x_{i, j, k} = 1 ~~~~\forall \;1\leq i, j \leq 9$$ $$\sum_{(i, j)\in Q_{p,q}} x_{i, j, k} = 1 ~~~~\forall \;1\leq k \leq 9,\; 1\leq p, q \leq 3$$ where the $Q_{p, q}$ are the nine $3x3$ squares.

This gives $4\times 9^2 = 324$ equations.

Fixing a variable $x_{i, j, k}$ to $1$ (meaning giving a clue) fixes 29 variables corresponding to $9$ variables $x_{i, j, k'}$, $8$ variables $x_{i', j, k}$, $8$ variables $x_{i, j', k}$, $j\neq j'$, $4$ variables $x_{i', j', k}$, $i'\neq i$, $j'\neq j$, $(i', j')$ in the same square as $(i, j)$.

When fixing $16$ clues, we in fact don't fix $29\times 16$ variables, because some variables are counted multiple times. The author shows that we can however upper bound the number of fixed variables by $9\times 29+7\times 23-2 = 420$, leaving at least $729-420 = 309$ non-fixed variables.

Fixing a variable removes the corresponding equation $\sum_{k'=1}^9 x_{i, j, k'}$. by fixing $16$ clues, it leaves us with $324-16 = 308$ equations.

The author then claims that since we have less equations than variables, there can't be a unique solution.

For $17$ clues, the same argument gives $307$ equations against $306$ variables, thus leaving the possibility of a unique solution.

Why this is wrong

The dimensionality argument doesn't work when dealing with integer linear programs. For example, consider $n$ binary variables $y_1, ..., y_n$. Constraints $\sum_{i=1}^n y_i = 1$ and $y_1 = 1$ impose a unique solution, though we have only two equations.

Also, the proposed argument could be turned to make it fail for $17$ clues. This is easy to see that the proposed $324$ equations have redundancies (If we keep all the equations from the first set of equations, we have $9$ redundant equations in each of the three other families).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .