36
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ I've certainly encountered published Sudoku problems that can't be solved using the "standard tricks" and that "require branching" (I deliberately leave the term "require branching" undefined because it's a notoriously slippery concept, but we all know it when we see it). Such Sudoku problems tend to be unpopular but they do exist. Many computer-generated Sudoku puzzles proceed by randomly eliminating entries from a filled grid until the original grid can no longer be uniquely reconstructed. It would be surprising to me if all such puzzles had unique rational solutions. $\endgroup$
    – Timothy Chow
    Commented Jun 7, 2010 at 15:46
  • $\begingroup$ We have 729 variables $a_{i,j,k}$. Also we have $4\times81=324$ automatic linear constraints. Then we set a handful of variables to equal $1$ corresponding to the given entries. This is clearly not going to give us enough conditions for a unique solution. But suppose we are more generous: if we are given say $a_{1,1,1}=1$ suppose we are also given $a_{1,1,k}=0$ for $k>1$ and $a_{i,j,1}=0$ when $(i,j)\ne(1,1)$ but is in the same row, column or $3\times 3$ box as $(1,1)$. This gives us $28$ further conditions for each entry, which might be enough. $\endgroup$
    – Robin Chapman
    Commented Jun 7, 2010 at 15:53
  • $\begingroup$ I thought of this question when I wrote a Sudoku solver in Python. (I only enjoyed Sudoku for a little while; at some point I decided to try meta-Sudoku.) What I learned was: (1) The solver generally didn't need to "branch" as much as you might think; it actually takes a lot of practice to spot every forced entry. (2) As you suggest, when I added more non-branching inferences, the amount of branching dropped sharply. I think that every inference in my fairly primitive program is of the unique rational type. $\endgroup$
    – Greg Kuperberg
    Commented Jun 7, 2010 at 15:56
  • 1
    $\begingroup$ Vow - quantum sudoku! $\endgroup$
    – Thomas Kragh
    Commented Jun 7, 2010 at 16:25
  • 14
    $\begingroup$ "The theory of Sudoku with $\textit{rational}$ number of rows is well known. Now..." $\endgroup$
    – Victor Protsak
    Commented Jun 7, 2010 at 17:19

4 Answers 4

Reset to default
16
$\begingroup$

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 |
 -----------------------------------
Improve this answer
$\endgroup$
3
  • $\begingroup$ So I gather that there is no particular reason to believe that this wouldn't occur in an ordinary newspaper Sudoku? If so, would such a puzzle be likely to be labeled "diabolical", or not necessarily all that likely? $\endgroup$
    – Greg Kuperberg
    Commented Jun 10, 2010 at 4:35
  • $\begingroup$ I don't think this one is as hard as the newspaper "diabolical" puzzles. $\endgroup$
    – David Eppstein
    Commented Jun 10, 2010 at 6:48
  • $\begingroup$ One could dig deeper into the sociology, but your discovery is already one answer to the question. Fractional Sudoku is a different game than integer Sudoku, not just in principle but at least occasionally in practice. $\endgroup$
    – Greg Kuperberg
    Commented Jun 10, 2010 at 14:09
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ I'll look at Eppstein's article ( arxiv.org/abs/cs/0507053 ), and of course his attention her could be very interesting. As for the Notices article, Crook's Occupancy Theorem, Theorem 1, creates linear equalities that must hold for rational solutions. Moreover, the theorem is stated for three pairs of types of conditions, (cell,column), (cell,row), (cell,box); but it also applies to (row,column), and in a weaker form to (row,box) and (column,box). This phenomenon is exactly what led me to the posted question. $\endgroup$
    – Greg Kuperberg
    Commented Jun 7, 2010 at 18:17
  • $\begingroup$ Dear Greg, the most interesting techniques I found came up first in British computer programmer forums. The best of these is the B.U.G. principle for puzzles with unique solutions. I've never been entirely sure I believed it, as the programmers were so very unmathematical in discussing it. However it worked every time, and usually reduced to situations where I could recover the choice it described by other means: sudocue.net/guide.php#BUG $\endgroup$
    – Will Jagy
    Commented Jun 7, 2010 at 18:50
  • $\begingroup$ This "BUG" principle, the "Bivalue Universal Grave", can also be interpreted in terms of linear programming. The basic idea is that when a linear equality only has two surviving variables, then the variables are equivalent and you can remove one of them in the system of equations without sacrificing sparseness. If you diagram this as an edge between two variables, then in Sudoku the edges often make even-length cycles. So this by itself also won't create any difference between integer programming and linear programming. $\endgroup$
    – Greg Kuperberg
    Commented Jun 7, 2010 at 19:01
  • $\begingroup$ I think you are onto something. For a similar problem that should be easier to decide, consider removing the constraints that involve the 3 by 3 boxes, back to the Latin square with some presets, which was historically the first version of the puzzles. The possible gap between rational and integral uniqueness may be wider this way, it may be narrower, but it should be easier to think about, and easier to program random problems that do have at least one integral solution. And one can start with 2 by 2 and 3 by 3 Latin squares first, see what happens on paper. $\endgroup$
    – Will Jagy
    Commented Jun 7, 2010 at 19:49
  • $\begingroup$ Like Sudoku, the Latin square completion problem is known to be NP-complete. The proof of that almost certainly lets you construct non-trivial polytopes with only one integer point. My question is not strictly mathematics, it's sociological. $\endgroup$
    – Greg Kuperberg
    Commented Jun 7, 2010 at 20:44
1
$\begingroup$

A good explanation of how humans solve sudoku is here -

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Here as well, the "Sledgehammer" that this author describes also applies to rational solutions. $\endgroup$
    – Greg Kuperberg
    Commented Jun 8, 2010 at 6:23

You must log in to answer this question.

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