3
$\begingroup$

John has started a sudoku puzzle and shows me his completed work, asking whether he's made any errors. There are no obvious errors (a number repeated in a row or subgrid). I know of two ways to determine whether he's erred:

  1. Continue solving the puzzle (without error) where John has left off, and see whether I arrive at an impossible state. If so, John erred. If not, I'll complete the puzzle, and John hasn't erred.
  2. Start the puzzle over again and solve it (without error) until either (a) I have filled in every square John has, and with the same numbers, in which case John hasn't erred; or (b) I have filled in some square John has, but with a different number, in which case John has erred (assuming that the puzzle has a unique solution).

Is there another way to determine whether John has erred? Specifically, is there a way that doesn't involve redoing or continuing the solution, but, rather, involves merely examining what John has done?

$\endgroup$
  • $\begingroup$ I'm a little confused - is this a challenge question, or a genuine request to know if there's a better way to see if there's an error? $\endgroup$ – Aza Jul 2 '15 at 5:47
  • $\begingroup$ @Emrakul I don't know what you mean by "challenge question", but this is a genuine request for a way to see if there's an error. $\endgroup$ – msh210 Jul 2 '15 at 5:47
  • $\begingroup$ @Emrakul I believe he's asking to know if there's a way to double-check your current (not-finished) soduko and know if it's correct (so far) without completing it, or backtracking your steps. So I think that this is a genuine question, not a challenge question, the type of question I think you and Doorknob aimed to fill the site with. As for a solution, I don't think so, but I'm no expert on Soduko. $\endgroup$ – warspyking Jul 2 '15 at 6:02
6
$\begingroup$

Unfortunately, no such (computationally reasonable) method currently exists that could make a 100% guarantee. I don't have a proof for its nonexistence, as there's no mathematical proof that it can't exist (yet), but no such method has yet been discovered. The only way we currently know to verify a Sudoku has no errors is by solving it and checking for impossibilities.

To reason why, consider that if such a method existed, Sudoku solvers wouldn't implement the deductive methods that they currently employ - they would simply need to guess a number then check to see if it's right.


(Slightly) more formally, the proposition you'd be trying to prove is: "The sudoku is solvable." There are really only two approaches you could take to prove that it's solvable:

  • Proof by contradiction: "The sudoku can't be solvable because it leads to an impossible state."
  • Direct proof: "By [some mathematical process], the Sudoku can be classified as "solvable" or 'unsolvable.'"

The first can always be executed - it's just guess and check until you exhaust all possibilities or encounter a valid solution. The second is a yet-unsolved unsolved mathematical problem.

The reason I add computationally feasible above is because there exist methods that effectively read "generate all possible Sudoku puzzles, then check to see if this one matches any of them." Obviously, this isn't reasonable to do.


There are, however, a couple trivial checks you could make to possibly find errors. They're not guaranteed to work, but they have the potential to pick up errors.

  1. You can check to make sure that there are no immediate row/column/box conflicts. If there are, you know there's an error immediately.
  2. You can check the possibilities for each cell. If there's any cell without any open possibilities, then there's an error somewhere.

These two can occasionally catch errors quickly, or require only a few deductive steps for you to spot an error. That being said, they're not guaranteed.

$\endgroup$
  • $\begingroup$ No problem, glad to help! $\endgroup$ – Aza Jul 2 '15 at 6:02
  • $\begingroup$ +1, and I might add that, as a seasoned Sudoku puzzler myself, the only way to know is if the site or book you are using has a way to distinguish numbers John plugged in from the ones given. If so, you can try to use only those numbers and check his logic, but in this case it'd be far easier to simply start over. $\endgroup$ – Nyk 232 Jul 2 '15 at 13:08
0
$\begingroup$

I would like to point that you are suppossing that there is only ONE solution for that sudoku. I know it is supposed that there is only one way to solve a sudoku but there is a chance that changing some numbers you can get into another valid solution (And I said that because I used to do a lot of sudokus and it happened to me too). You said:

  1. Start the puzzle over again and solve it (without error) until either (a) I have filled in every square John has, and with the same numbers, in which case John hasn't erred; or (b) I have filled in some square John has, but with a different number, in which case John has erred."

So I think that getting another solution does not mean that John was erred. It means that maybe he was erred but maybe you just found another valid solution so the only way to know if John was erred with HIS start, is finishing John's sudoku start.

Having said this, as a sudoku is a mathematical/logic problem, if there is a way to find the solution without having to solve it, it has to be with probability but I can't tell the way as I don't have that knowledge.

$\endgroup$
  • $\begingroup$ I agree. Maybe for clarification, a sudoku grid with only one number entered in the upper left corner is also a valid starting grid - and it has multiple solutions. $\endgroup$ – Nejc Jul 2 '15 at 8:42
  • $\begingroup$ Thanks for pointing out the weakness in my question. I'll edit it presently to clarify. However, I don't see that this answers the question. $\endgroup$ – msh210 Jul 2 '15 at 12:45
  • $\begingroup$ It doesn't full answer your question with a method but helps guiding you to the solution pointing the omitted point I mentioned. So I posted it as I see it helpful. As I said, if there is any solution, it has to be a probabilistic one but I can't get it, sorry. $\endgroup$ – Megasa3 Jul 2 '15 at 13:53

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.