16
$\begingroup$

You may have heard that recently it was proven that the smallest number of starting clues for a Sudoku game, guaranteeing a unique solution, is 17.
An example is shown below.

I am interested in the opposite:
What is the largest number of starting clues for a Sudoku game that does not guarantee a unique solution?

I have a lower bound of 63. This is if you take a solved Sudoku and delete every instance of two numbers (i.e., delete all the 1s and 2s). Alternatively, you could delete the top two rows, again yielding two different solutions for 63 starting clues.
Can you do better than 63, or is 63 is the highest?

$\endgroup$

3 Answers 3

Reset to default
26
$\begingroup$

I conclude that the largest number of starting clues for any Sudoku to be ambiguous is 77 (81 - 4), and you can construct it by finding a 'rectangle' with ones on two opposite corners and twos on the other two opposite corners. Remove all four of them. Now you can solve it in two ways: it is ambiguous.

A random Sudoku from the Internet:

enter image description here

$\endgroup$
2
  • 7
    $\begingroup$ And 77 can be proved to be the upper bound, as if you have less than 4 empty cells, at least one of them is alone in its line or in its column, so that its value is not ambiguous. $\endgroup$
    – TonioElGringo
    Commented Mar 29, 2013 at 5:00
  • 1
    $\begingroup$ Is it neccessary that such a rectangle exists ? $\endgroup$
    – entropyfever
    Commented Dec 13, 2022 at 23:49
8
$\begingroup$

77.

Label as a matrix, rows 1 down to 9, columns 1 through 9. Begin with any completely filled in grid such that $$a_{11} = 1,a_{12} = 2,a_{41} = 2,a_{42} = 1. $$ The important thing is that the first pair are in the upper left 3 by 3 box, while the other pair are in the middle left 3 by 3 box.

Now, delete those four entries.

$\endgroup$
1
$\begingroup$
  1. A sudoku that is ambiguous is not a proper sudoku, but whether a sudoku is ambiguous or not depends more on the unique set of clues given rather than the number of clues--17 to 77--given. That is to say, given 17 to 77 clues, whether a sudoku can be solved without guessing (that is, solved "logically") depends on the unique set of clues given.
  2. 17 is the minimum number of clues that can still allow for a "logical" (without guessing) solution to the sudoku.
  3. 77 is the maximum number of clues that can still yield an ambiguous sudoku.
  4. The "rectangle" method--which provides 77 clues but leaves out two pairs of rectangular corner numbers to create an ambiguous sudoku--works not just for 1s and 2s but for any pair of opposite corner numbers.
  5. The "rectangle" involves either two 3x3 adjacent grids or hops over an adjacent grid to involve a third adjacent grid, but a rectangle cannot involve more than three 3x3 grids.
  6. I have just finished a sudoku with three "rectangles" in it--one with a 5 and 2 pair, one with a 1 and 3 pair. and one with a 9 and 2 pair.
  7. Is there a minimum or maximum number of "rectangles" in a sudoku?
$\endgroup$

You must log in to answer this question.

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