Skip to main content
added 903 characters in body
Source Link
user20
user20

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.

Unfortunately, no such method currently exists. 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.

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.

Unfortunately, no such method currently exists. I don't have a proof for its nonexistence, as there's no mathematical proof that it can't exist (yet), but none haveno 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.

Unfortunately, no such method currently exists. I don't have a proof for its nonexistence, as there's no mathematical proof that can't exist (yet), but none have 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.

Unfortunately, no such method currently exists. 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.

Source Link
user20
user20

Unfortunately, no such method currently exists. I don't have a proof for its nonexistence, as there's no mathematical proof that can't exist (yet), but none have 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.