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.
Best Answer
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.
Or if you want something that looks like the puzzles that get published, here's another one that uses the same mechanism: