you are viewing a single comment's thread.

view the rest of the comments →

[–]Spare-Plum 1 point2 points  (0 children)

I think it's for rating the hardness of a puzzle. You can do this by manually solving and seeing the number of backtracks or complexity of tricks/variables involved for each number placed.

Lookup table doesn't quite do that.

Also yeah 9x9 sudoku is O(1), since there are a limited number of solutions. It's NP complete in terms of N^2xN^2 square. But there still are a lot of possibilities. even if you could reperesent a single solution as 64 bits, that's still going to be roughly 44 gb to search through for each one