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