Suppose you have a sudoku puzzle that you will want to solve using logic.

Furthermore suppose you solve the puzzle until you reach a point where a single cell can have two possible values ($a$ or $b$ and you cannot solve the value for any other cell using logic). Let's also suppose that if you pick value $a$ you eventually would realize that you would end up with two valid end-point solutions which could not be disambiguated from each other through logic. (name these solved sudoku $X$ and $Y$) On the other hand, if you originally choose $b$ you would find that you are able to finish the puzzle with logical steps reaching the end solution $Z$

Is this a valid sudoku puzzle?

Here are my thoughts. Initially this is an invalid sudoku puzzle because it admits multiple solutions ($X$, $Y$, and $Z$). But if you initially assume that the puzzle is valid then you cannot pick $a$ thus excluding both $X$ and $Y$ end-positions and thus you solve the original puzzle with an unique solution. So it would be considered valid.

So you have an invalid Sudoku puzzle that becomes valid when you assume its validity!

My questions are: Is such a puzzle considered a valid Sudoku? What are the formal definitions of a valid Sudoku puzzle?

I have further questions such as: If you allow this recursive definition of validity how deep can you go by creating several layers where you eliminate options because there would be no way to disambiguate in the end

  • 1
    $\begingroup$ Assume a false premise, and you can prove a false conclusion. If you assume it is valid, then you can conclude it is valid. That does not make it true. Your assumption does not make the other solutions magically disappear. $\endgroup$ – Jaap Scherphuis Oct 18 '18 at 11:28

This assumption of validity, a unique solution from the starting grid, is in fact a convention in Sudoku. As such, the original puzzle is invalid, regardless of what or how many choices you have to make, because it can be completed non-uniquely.

This assumption can be turned into a tool for solving valid puzzles. If a choice leads to a part of the puzzle that by itself cannot be filled uniquely, that choice can be eliminated, and it saves the trouble of having to continue only to realise that the choice was wrong. See Bram's answer here.

  • 2
    $\begingroup$ Of course, in any valid Sudoku puzzle, if you try the choice that lets part of the puzzle be filled in more than one way, eventually it will lead to a contradiction somewhere else in the grid. It's never actually necessary to assume the puzzle's solution is unique. $\endgroup$ – David K Oct 18 '18 at 12:56
  • $\begingroup$ I agree! This agrees with my intuition. The problem is that I specifically remember a while ago when I was learning to solve hard sudokus that some software had rules to solve sudoku such as those: "Here we must choose $b$ because if not we would have multiple solutions"! I remembered feeling uncomfortable with that rule $\endgroup$ – gota Oct 18 '18 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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