4
$\begingroup$

I was watching this video where he talked about how scientists found the minimum number of numbers a Sudoku can have and still have exactly one solution. This led me to think of the opposite - what is the maximum number of numbers a Sudoku can have still contain multiple solutions?

I found this post on Stack Exchange talking about a similar problem more generally - but the general consensus was that the problem was of NP difficulty. I was wondering, therefore, if my question was also of NP difficulty, or if the digression of Maximization vs Minimization of the amount of numerals makes a difference?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
11
$\begingroup$

The maximum number of entries that a Sudoku can have while still having multiple solutions is

77, i.e all but four squares filled.

One such Sudoku looks like this:

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

The idea here is that

the four blank entries cause two distinct rows, columns, and squares to have blanks in them, and the two missing numbers are the same for each row, column, and square. This leads to a scenario where there are two possible ways to place the missing numbers. In the above example, a 4 and a 5 are missing from rows 8 and 9, columns 2 and 7, and squares 7 and 9 (where 1 = upper left, 2 = middle left, etc.). So the pair (R8C2, R9C2) can be either (4, 5) or (5, 4), and then (R8C7, R9C7) will be the other pair. Thus, there are two solutions to the Sudoku.

Proof that this is optimal:

We will show that it is impossible for a Sudoku with less than 4 blanks (0, 1, 2, or 3 blanks) to have multiple solutions. We will use the fact that if a row or column has exactly one blank, then we can uniquely solve that row or column.

Obviously, a Sudoku with no blanks or only one blank has only one solution. For two blanks, note that whichever two squares we choose to be blank, they have to differ in at least one of the row or column they are in; otherwise, they'd be the same blank. So there exists a row or column with only one blank, which we can fill in by our postulate. This reduces the two blank case to the one blank case, so we conclude that a Sudoku with two blanks has a unique solution.

We treat the three blank case similarly. If the three blanks are not all in the same row, then there exists a blank that is in a row by itself. (This comes from the fact that any non-trivial partition of 3 into positive integers must have a 1.) If they are all in the same row, then two of them must be in different columns, meaning there exists a column with only one blank. In both cases, we can solve the row or column with only one blank and reduce to the two blank case.

Therefore, we cannot have a multi-solution Sudoku with less than 4 blanks. And since a 4 blank multi-solution Sudoku exists, we conclude that a minimum of 4 blanks is necessary for a Sudoku to have multiple solutions.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Just a note - spoilers aren't necessary for an answer to a question about puzzles, as opposed to an answer to a puzzle challenge, There's no mystery here to preserve for future solvers, because there's no puzzle being solved. :) $\endgroup$
    – Rubio ♦
    Commented Feb 2, 2020 at 4:08
2
$\begingroup$

The maximum is at least $81-18=63$, by removing all copies of 1 and 2 from a completed puzzle. The maximum is no more than $81-4=77$ because there must be a row with at least two blanks and then each of those corresponding columns must have at least two blanks. Seems like 77 should be attainable by removing these two 1s and 2s from the top rows of a completed puzzle:

* * 1 2 * * * * *
* * 2 1 * * * * *
* * * * * * * * *
Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.