N-Queens II
hardTime: O(n!)Space: O(n)
Recognize the pattern
count N-Queens solutionssame as N-Queens I but count onlyno board construction needed
Brute force idea
Same backtracking as N-Queens I.
Better approach
Same backtracking but increment counter instead of building boards. Slightly faster — no string construction. O(n!).
Key invariant
Same constraint checking: columns, positive diag, negative diag. Just count valid complete placements.
Watch out for
Building board strings — unnecessary for counting. Just count.