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.

4more comments