How to check a partial sudoku solution

Question

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?

Answer 1

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.

Answer 2

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:

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."

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.

Answer 3

From a purely practical perspective, https://www.sudoku-solutions.com/ allows you to check if a puzzle is solvable in a given state and with a unique solution, however unfortunately I don't know how it functions under the hood.