The NP criteria applies to the general case and not a special case, at least that is my understanding. For example the NP criteria is silent if we are talking about the standard 9x9 board with say 17 clues. It may be very hard to solve but it has a fixed number of enumerations. The NP criteria is about how the enumerations grow exponentially with problem size (N), and that there may not be an algorithm that can overcome this "explosion" in enumerations.
Discussions
Become a Hackaday.io Member
Create an account to leave a comment. Already have an account? Log In.
The NP criteria applies to the general case and not a special case, at least that is my understanding. For example the NP criteria is silent if we are talking about the standard 9x9 board with say 17 clues. It may be very hard to solve but it has a fixed number of enumerations. The NP criteria is about how the enumerations grow exponentially with problem size (N), and that there may not be an algorithm that can overcome this "explosion" in enumerations.
Are you sure? yes | no
@agp.cooper It's magic Sudoku that can be solved in O(n^3) time! A version of Sudoku that is in P.
Are you sure? yes | no
I think it called a "magic square" see https://en.wikipedia.org/wiki/Magic_square
Are you sure? yes | no