Do actual Sudoku puzzles have a unique rational solution? - MathOverflow

Do actual Sudoku puzzles have a unique rational solution?

2010-06-07T15:28:02Z

Here is a question in the intersection of mathematics and sociology. There is a standard way to encode a Sudoku puzzle as an integer programming problem. The problem has a 0-1-valued variable $a_{i,j,k}$ for each triple $1 \le i,j,k \le 9$, expressing that the entry in position $(i,j)$ has value $k$. The Sudoku rules say that four types of 9-sets of the variables sum to 1, to express that each cell is filled with exactly one number, and that each number appears exactly once in each row, column, and $3 \times 3$ box. And in a Sudoku puzzle, some of these variables (traditionally 27 of them) are preset to 1.

It is known that generalized Sudoku, like general integer programming, is NP-hard. However, is that the right model for Sudoku in practice? I noticed that many human Sudokus can all be solved by certain standard tricks, many of which imply a unique rational solution to the integer programming problem. You can find rational solutions with linear programming, and if the rational solution is unique, that type of integer programming problem is not NP-hard, it's in P. Traditionally Sudoku puzzles have a unique solution. All that is meant is a unique integer solution, but maybe the Sudoku community has not explored reasons for uniqueness that would not also imply a unique rational solution.

Are there published human Sudoku puzzles with a unique solution, but more than one rational solution? Is there a practical way to find out? I guess one experiment would be to make such a Sudoku (although I don't know how difficult that is), and then see what happens when you give it to people.

Answer by Will Jagy for Do actual Sudoku puzzles have a unique rational solution?

2010-06-07T17:25:05Z

Not an answer, just wanted to point to some references. David Eppstein has an arXiv piece on a clever "human-type" trick, I imagine he will post something for this question. He also produced random puzzles and counted the effect of his method on ability to solve, and there were still enough unsolvable when including his method. Eppstein's method made it into the puzzle book "Mensa Guide to solving Sudoku" by Peter Gordon and Frank Longo, one of the few books I found with any difficult puzzles at all. The method I am curious about, though, and I saved the issue, is in the April 2009 A.M.S. Notices, J. F. Crook, "A pencil-and-paper algorithm for solving sudoku puzzles," pages 460-468, pdf at http://www.ams.org/notices/200904/index.html

Answer by bramcohen for Do actual Sudoku puzzles have a unique rational solution?

2010-06-08T05:37:58Z

A good explanation of how humans solve sudoku is here -

http://onigame.livejournal.com/20626.html

Answer by David Eppstein for Do actual Sudoku puzzles have a unique rational solution?

2010-06-08T15:19:32Z

I wasn't planning on answering here but since someone mentioned my paper in the long comment thread above maybe I should anyway.

When I'm solving problems by hand one of the sets of patterns I frequently use involve uniqueness: something can't happen because it would lead to a puzzle with more than one solution, but a well-posed Sudoku puzzle has only one solution, so it's safe to assume that whatever it is doesn't happen. For instance, it's not possible to have four initially-empty cells in a rectangle of the same two rows, the same two columns, and the same two 3x3 squares, and also for these four cells to all contain one of the same two values, because then the two values they contain could be placed in two different ways and the rest of the puzzle wouldn't notice the change. So if there's only one way to prevent a rectangle like this from forming then the solution has to use that one way.

I have the sense (though I could be wrong) that this sort of inference does not imply a unique rational solution. But of course a puzzle could have a unique rational solution anyway — my computer solver knows these rules too, but uses them less frequently than I do by hand.

ETA: It does indeed seem to be true that these rules don't imply unique rational solutions. With them, my solver easily solves the following puzzle, which has a unique integer solution but does not have a unique fractional solution. Without them, my solver can still solve the same puzzle, but only by using rules that are (in my experience) much more difficult to apply by hand.

 ----------------------------------- 
| 3   7   8 | 6   4   5 | 1   2   9 |
|           |           |           |
| 6   9   . | .   7   . | 4   8   5 |
|           |           |           |
| 4   .   5 | 9   .   8 | 3   7   6 |
|-----------------------------------|
| 7   .   9 | 5   3   . | 8   6   4 |
|           |           |           |
| 8   4   . | 7   .   . | 5   9   3 |
|           |           |           |
| 5   3   6 | 8   9   4 | 2   1   7 |
|-----------------------------------|
| 1   6   3 | 2   5   7 | 9   4   8 |
|           |           |           |
| 9   8   4 | .   .   . | 7   5   2 |
|           |           |           |
| 2   5   7 | 4   8   9 | 6   3   1 |
 -----------------------------------

Or if you want something that looks like the puzzles that get published, here's another one that uses the same mechanism:

 ----------------------------------- 
| 1   .   . | 8   .   7 | 5   .   . |
|           |           |           |
| .   5   . | 6   .   . | 9   7   . |
|           |           |           |
| .   6   . | .   4   . | .   .   . |
|-----------------------------------|
| .   .   2 | .   .   . | .   6   . |
|           |           |           |
| 6   .   . | 4   .   3 | .   .   . |
|           |           |           |
| .   4   . | .   .   . | 1   .   . |
|-----------------------------------|
| .   .   . | .   1   . | .   5   . |
|           |           |           |
| .   1   3 | .   .   6 | .   9   . |
|           |           |           |
| .   .   7 | 5   .   4 | .   .   1 |
 -----------------------------------

Answer by Gerhard Paseman for Do actual Sudoku puzzles have a unique rational solution?

2010-06-08T20:34:26Z

Towards a weak proof of existence, I would go through Gordon Royle's database of Sudoku with a minimum number of givens, and (program a computer to) check for multiple rational solutions on any of the puzzles. If all of them had unique rational solutions, I would take that as strong evidence that all proper Sudoku have unique rational solutions. If one had multiple rational solutions, add some givens until you have a maximal desired puzzle, and publish it (or send it to Nick Baxter et. al. for the sociological answer).

Gerhard "Ask Me About System Design" Paseman, 2010.06.08