7
$\begingroup$

I was reading through the following notes regarding solving a 9x9 Sudoku via a binary integer program

https://vanderbei.princeton.edu/tex/talks/INFORMS_19/Sudoku.pdf

The formulation is straightforward but on slide 10 the author claims that if the problem has a unique integer solution then that implies the linear relaxation has the same solution and therefore the binary constraints on the variables is unnecessary.

It's really not clear to me why this would be so. Wouldn't this contradict the fact that Sudoku is known to be NP-complete?

enter image description here

Edit:

The following Sudoku has a unique solution. You can verify that by solving it by logical deduction alone.

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

I adapted the PuLP sudoku example code and the LP relaxation solves with the unique integral solution. However, I introduced auxiliary variable and constraints and changed objective function to make non integral solutions more attractive, and it found a solution where 42 of the variables had a value of 1/2.

So this counts as a counter-example that a unique BIP solution gives rise to a unique LP solution.

$\endgroup$
4
  • $\begingroup$ No, its the other way around. It means that in this specific case, the sudoku is no longer NP-hard. $\endgroup$
    – Kuifje
    Commented Oct 6, 2022 at 10:06
  • $\begingroup$ @Kuifje Are you sure it is referring to this specific case? The last sentence on the slide is "Hence, it is always possible to solve sudoku problems as linear optimization problems" - that seems like a very general statement. $\endgroup$
    – Ram
    Commented Oct 6, 2022 at 10:14
  • 3
    $\begingroup$ I have found Provan (2009) where they say that if the solution of the Sudoku can be found via pigeon-hole rules (i.e. enough non-empty cells are given), then the relaxation solution is integer (Theorem 2). In general, it is NP-complete by reduction to graph colouring or set covering. The claim on unique integer solutions in this talk sounds wrong (otherwise all MIPs with unique integer solutions would be easy peasy). $\endgroup$ Commented Oct 11, 2022 at 11:15
  • $\begingroup$ Great find @David, thanks for sharing! $\endgroup$
    – Ram
    Commented Oct 14, 2022 at 3:48

1 Answer 1

2
$\begingroup$

The creators of the Sudoku puzzles ensure players that there is a unique solution to the puzzle. Hence, the system of integer linear equalities over Boolean variables described in Vanderbei's slides has one and only one solution. This is what Vanderbei calls the "unique integer solution" in slide 10.

EDIT: THE FOLLOWING ARGUMENT IS FALSE BECAUSE THE RANK OF THE MATRIX IS NOT (NECESSARILY) FULL. SORRY FOR THIS WRONG PATH. SEE THE DISCUSSION IN THE COMMENT. Now, consider a relaxation of this system of equalities over the reals. This is what Vanderbei calls "linear relaxation" in slide 10. The unique integer solution discussed above remains a solution to this relaxed system. A system of linear equalities over the reals has no solution, one solution, or an infinite number of solutions (for a proof of this claim, or at least an intuition, please check a linear algebra course on the web). Consequently, the linear relaxation has one solution which is the integer one.

In the case where the initial assertion becomes false - "the creators of the Sudoku puzzles ensure players that there is a unique solution to the puzzle" - then the property above does not hold anymore.

Then, to answer your question, the best is to cite David Eppstein, a renowned computational complexity theorist, who blogged a lot about the complexity of the Sudoku puzzle in the past:

"In the meantime, when one says Sudoku is NP-complete, one should keep in mind that this refers only to an unusual type of Sudoku puzzle in which there might be multiple solutions."

To conclude, may we recall that any KxK Sodoku puzzle with K a fixed parameter in input, that is, with K a constant, is solvable in constant time.

$\endgroup$
15
  • 2
    $\begingroup$ Thanks @LocalSolver. I'm still missing whatever is needed to make the conclusion that "Consequently, the linear relaxation has one solution". Why could it not be the case that we have one integer solution and infinite number of non-integer solutions to the linear relaxation? The simple BIP with two variables and a single constraint 2x_1 + x_2 = 2 has a single integer solution (1,0) but the linear relaxation has an infinite amount of solutions right? $\endgroup$
    – Ram
    Commented Oct 6, 2022 at 22:30
  • $\begingroup$ In the case you mention here, your system has 2 variables but 1 equality. Then it can have an infinity of solutions over the reals. More generally, if your system has N variables and M equalities with M < N, then you will have an infinite number of solutions. If the system has N variables and M equalities with M >= N and no linearly dependent equalities, which is the case here (check the AMPL output: 198 variables, 212 constraints on page 9), then there is one or no solution. $\endgroup$
    – Hexaly
    Commented Oct 7, 2022 at 20:40
  • $\begingroup$ I probably misunderstand this argument. If M>=N then the rank can at most be N. So there must be linear dependent constraints, right? Of course, LP solvers typically work with N+M variables. $\endgroup$ Commented Oct 8, 2022 at 16:51
  • $\begingroup$ You're right @ErwinKalvelagen. The argument is fallacious. Intuitively, I feel the rank to be full because, according to the principle of the game, one can reduce the matrix using simple propagation techniques. Sorry for this. But our exchange leads to interesting thoughts and experiments. Below are the ones. $\endgroup$
    – Hexaly
    Commented Oct 9, 2022 at 21:05
  • 1
    $\begingroup$ Thanks again! I have updated the original question to include an example which has a non-integral solution to the linear relaxation. $\endgroup$
    – Ram
    Commented Oct 10, 2022 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.