[tomxor]

Pruning is an optimisation though, not a computational reduction... the remaining computation is still brute force. While it may be effective with low n, the complexity will still grow in roughly the same way as n increases - for this reason I would still call it brute force.

Isn't this why sudoku is still considered NP hard? (unless there has been a recent breakthrough).