Unfortunately no. The question is a simplification of the P versus NP problem.
The problem lies in having to prove that no method exists that is easy. How do you prove that no matter what method you use to solve the sudoku, it can never be done easily? You’ll need to somehow prove that no such method exists, but that is rather hard. In principle, it could be that there is some undiscovered easy way to solve sudokus that we don’t know about yet.
I’m using sudokus as an example here, but it could be a generic problem. There’s also a certain formalism about what “easy” means but I won’t get into it further, it is a rather complicated area.
Interestingly, it involves formal languages a lot, which is funny as you wouldn’t think computer science and linguistics have a lot in common, but they do in a lot of ways actually.
Well it just so happens that the definition of “easy” in the actual problem is essentially “fast”. So under that definition, checking every single possible solution is not an “easy” method.
What if the sudoku is 1 milllion lines by 1 million lines? How about a trillion by a trillion? The answer is still easy to check, but it takes exponentially longer to solve the board as the board gets larger. That’s the jist of the problem: Is there a universal solution to a problem like this that can solve any size sudoku before the heat death of the universe?
Unfortunately no. The question is a simplification of the P versus NP problem.
The problem lies in having to prove that no method exists that is easy. How do you prove that no matter what method you use to solve the sudoku, it can never be done easily? You’ll need to somehow prove that no such method exists, but that is rather hard. In principle, it could be that there is some undiscovered easy way to solve sudokus that we don’t know about yet.
I’m using sudokus as an example here, but it could be a generic problem. There’s also a certain formalism about what “easy” means but I won’t get into it further, it is a rather complicated area.
Interestingly, it involves formal languages a lot, which is funny as you wouldn’t think computer science and linguistics have a lot in common, but they do in a lot of ways actually.
You can solve any sudoku easily by trying every possible combination and seeing if they are correct. It’ll take a long time, but it’s fairly easy.
Well it just so happens that the definition of “easy” in the actual problem is essentially “fast”. So under that definition, checking every single possible solution is not an “easy” method.
What if the sudoku is 1 milllion lines by 1 million lines? How about a trillion by a trillion? The answer is still easy to check, but it takes exponentially longer to solve the board as the board gets larger. That’s the jist of the problem: Is there a universal solution to a problem like this that can solve any size sudoku before the heat death of the universe?