2 ms·

How do know if a certain puzzle is impossible (ie malformed)?

• matsemann 6y ago
  That is a "decision problem": Does this puzzle have a solution? For Sudoku, that's easy to verify. That makes it an NP-problem. But for Sudoku, finding a solution is very difficult, so difficult that we say it's NP-Complete. So the only way to verify that a Sudoku can be solved, is really to try a bruteforce (potensially sped up with guesses/backtracking) and then find out if you cannot continue because of a broken constraint somewhere.
  • matsemann 6y ago
    > For Sudoku, that's easy to verify. I meant: For Sudoku, it's s easy to verify that a given solution is correct. (cannot edit) Of course, being given the solution first in order to even try, can be a bit boring. For that, there exists "zero-knowledge proof" where one can reveal one knows an answer, without actually divulging it. Here is a writeup about someone doing that for Sudoku: https://manishearth.github.io/blog/2016/08/10/interactive-sudoku-zero-knowledge-proof/ https://manishearth.github.io/blog/2016/08/10/interactive-su...