24
$\begingroup$

Yesterday, I tried to solve a regular Sudoku puzzle. Of course, the Sudoku puzzle had a unique solution. But, I was feeling a little lazy, so, rather than solve the puzzle properly, I made guesses! At every step, I put a random number in one of the empty cells, as long as it didn't contradict any rules!

Feeling lucky, I decided to continue solving the puzzle in that way. So far so good: I hadn't found any contradictions yet! The puzzle was almost complete; I grinned...

...

And yes... as you could have guessed... the final empty cell... I just couldn't put any number! Every other number followed the rules, yet, in this single cell, any number I put would break the rules of Sudoku!

Thus, I decided to leave this puzzle... Until today! This morning, I saw the solution for yesterday's Sudoku puzzle. And I was badly shocked. If I compare my (incorrect) solution to this, every number I put is wrong! I felt that bad karma happened to me.


Question: Do you believe my story?

  • If yes, could you construct an example of what puzzle I was working on? What were my guesses and what was the intended solution?
    Bonus: Could you construct such a puzzle with the minimum number of initial given clues as possible?
  • If no, could you prove that I was wrong?
    Bonus: What is the minimum number of empty cells in the end such that every other cell follows the rules but any number we put in any empty cells will break the rules?

This is a fictional story btw if you are curious...

$\endgroup$
1
  • 4
    $\begingroup$ I have encountered this before! $\endgroup$ Commented May 18, 2020 at 8:52

2 Answers 2

26
$\begingroup$

You're

wrong; since all other cells have been filled according to the rules, you'll have eight completely filled rows with a sum of 45 (1+2+..+9), and eight completely filled columns with a sum of 45. The remaining row has eight different numbers (otherwise you would have already broken a rule), so you can find the number $x$ that belongs in the last cell. That must also make the sum of the remaining column 45; otherwise you would get a different sum if you sum by row than if you sum by column. Therefore, since the other 8 cells in the last column are unique, and there's no way to write 45 as a sum of 9 numbers from 1-9 with exactly two duplicates, your final number must be different from the others in that column as well, and there is no contradiction, i.e. the number is valid as well (because the same idea holds for the 3x3 square).

$\endgroup$
1
  • $\begingroup$ Nicely done, this is a correct proof! :) $\endgroup$
    – athin
    Commented May 19, 2020 at 2:38
19
$\begingroup$

Glorfindel's answer is sufficient for the main question.

To answer the bonus question:

I find that 2 empty cells are sufficient.

Here is an example:

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

To construct this example,

I searched a completed sudoku puzzle for two pairs of numbers aligned in such a way that one pair can be swapped safely if the other also is. I then swapped just one of those pairs, and erased one number from each of the two conflicts that arose as a result.

As for a starting position,

erasing one other number within those two pairs suffices:
2 3 9 8 6 7 5 4 1
4 6 1 3 5 9 7 2 8
7 5 8 _ _ 2 9 3 6
5 9 3 6 7 4 1 8 2
8 1 4 9 2 3 6 7 5
6 7 2 5 8 1 4 9 3
1 2 5 7 9 8 3 6 4
9 4 6 2 3 5 8 1 7
3 8 7 _ 1 6 2 5 9
Your random guess produced a 4 in row 3, column 4, and we arrive at the final position.

$\endgroup$
5
  • $\begingroup$ Hold on. If they can be swapped safely, then either the puzzle had multiple solutions or one of those four cells was a starting clue. $\endgroup$
    – mckeed
    Commented May 18, 2020 at 21:29
  • 2
    $\begingroup$ @mckeed One of those four cells was a starting clue, in the puzzle I used. $\endgroup$
    – Brilliand
    Commented May 18, 2020 at 21:34
  • 1
    $\begingroup$ @Brilliand could you perhaps insert the starting clues and the intended solution, that would be great :) (btw, I'm giving the checkmark to Glorfindel as it proves the main question, anyway +1 for your bonus answer!) $\endgroup$
    – athin
    Commented May 19, 2020 at 2:37
  • $\begingroup$ @athin I'm afraid I don't have the original puzzle I used (I just found an online sudoku generator and clicked "view solution"). I'm pretty sure the original puzzle had two starting clues among the numbers I erased, in fact. For all intents and purposes, there are no "original" starting clues, though it's easy enough to invent new ones (as Glorfindel demonstrated in his edit). $\endgroup$
    – Brilliand
    Commented May 19, 2020 at 17:55
  • $\begingroup$ @Brilliand no problem! The one by Glorfindel is actually enough to justify the solution :) $\endgroup$
    – athin
    Commented May 19, 2020 at 21:11

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