148. N-Queens - Count Solutions

Given an integer n, find the number of distinct ways to place n queens on an n x n chessboard such that no two queens attack each other (no two share a row, column, or diagonal). Print that count.

Input: A single line containing the integer n. Output: Print a single integer - the number of distinct ways to place n non-attacking queens on an n x n board.

1 <= n <= 12

Tracking the two diagonal directions requires a clever indexing trick: (row - column) is constant along one diagonal direction, and (row + column) is constant along the other - both can be tracked with simple boolean arrays indexed by these computed values.

Count the number of ways to place n queens on an n x n chessboard so that no two attack each other. Brute force: Try every possible way to place n queens anywhere on the board (choosing n cells out of n² total) and check each combination for attacks - this is combinatorially enormous, completely impractical beyond tiny boards. Optimised: Placing exactly ONE queen per row (since no valid solution can ever have two queens in the same row anyway) immediately reduces the search space from 'choose n cells out of n²' down to 'choose one column per row' - combined with tracking attacked columns/diagonals in O(1)-checkable sets, invalid branches are pruned the instant they'd conflict, long before a full placement is attempted.

Place one queen per row, and before recursing into the next row, check the candidate column directly against every previously placed queen's column and both diagonals by comparing indices, only recursing if no conflict is found and backtracking otherwise. This prunes invalid placements immediately instead of completing them first, but each placement's validity check costs O(n) since it scans all previously placed queens. Time: O(n!) Space: O(n)

Keep three bitmasks, or boolean arrays, tracking which columns, which 'row + col' diagonals, and which 'row - col' diagonals are currently occupied. Placing or removing a queen updates all three in O(1), and checking whether a candidate column or diagonal is free is also O(1), a single bit test, instead of scanning every previously placed queen. This doesn't shrink the fundamental size of the N-Queens search tree, but it shrinks the cost of each placement decision from O(n) down to O(1). Time: O(n!) Space: O(n)

Generate every way to place n queens on the board, for example every choice of n cells out of n^2, with no conflict checking during placement, and only after a complete placement is formed, scan all pairs of placed queens to check whether any two share a row, column, or diagonal, counting the placements with no conflicts. This checks validity far too late, after wastefully building enormous numbers of placements that were already doomed from an early conflict. Time: O(n^n * n^2) Space: O(n)

1. Place queens one ROW at a time. 2. For each row, try every column, skipping any that's attacked by a previously placed queen (same column, or either diagonal). 3. Track attacked columns and both diagonal directions using simple sets/arrays so each placement check is instant; backtrack (remove the queen, unmark the sets) after fully exploring a branch, and count every time all n rows are successfully filled.

Time: O(n!) in the worst case (still exponential, but with heavy pruning from the attacked-set checks, in practice far fewer branches are actually explored). Space: O(n) for the attacked-columns/diagonals tracking sets and the recursion depth.

Test n = 1 (trivially 1 solution), n = 2 or n = 3 (0 solutions), and n = 12 (largest case, for performance).

Be ready to explain why 'one queen per row' is a safe simplifying assumption (never loses any valid solution) - this reduction from a 2D placement search down to a 1D column-choice-per-row search is the entire key insight behind an efficient N-Queens solution.