34 ms·
The solver doesn't obviously negate the puzzle's NP-completeness. It first reduces the solution space, then starts brute-forcing what's left. I don't have a pro
by matchu 12y ago
The solver doesn't obviously negate the puzzle's NP-completeness. It first reduces the solution space, then starts brute-forcing what's left. I don't have a proof on hand, but that just smells nonpolynomial.
You could argue that, if we consider "Sudoku" to be the instance of the puzzle where n=9, then the puzzle isn't NP-hard because it has the constant-time solution of trying all 6.67e21 solutions, but the result is so uninteresting that it's understood that the author means the more general problem.
- jimmaswell 12y agoDepends on the initial state of the puzzle. Sometimes there's always a deterministic set of correct next moves to make. I guess this refers to cases that aren't like that?
- pjscott 12y agoRight; we're talking about upper bounds here. Assume that the boards are chosen by some kind of wily, malevolent demon with an obsessive desire to embed tricky 3SAT problems in everything.
- matchu 12y agoSimilarly, sometimes your sorting algorithm takes linear time because the input was a sorted list. That's the lower bound, but lower bounds usually aren't as interesting as upper bounds.