51. N-Queens - Detailed Explanation

Problem Statement

Place N queens on an N × N chessboard so that no two queens threaten each other. Return all distinct solutions to the placement. Each solution should be represented as a list of strings, where 'Q' denotes a queen and '.' denotes an empty square.

Constraints:

• 1 <= N <= 9
• If N < 4 (except N = 1), no solutions exist (queens inevitably attack each other for N=2 or N=3).

Example:

Input:

N = 4

Output:

[[".Q..",   
  "...Q",   
  "Q...",   
  "..Q."],

 ["..Q.",   
  "Q...",   
  "...Q",   
  ".Q.."]]

Explanation:

For a 4×4 board, there are 2 distinct solutions. Each solution is shown as 4 strings, one for each row of the board. Each row contains exactly one 'Q' and the rest '.'. In the first solution above, the queens are at positions (row, col): (0,1), (1,3), (2,0), (3,2). No two queens share a row, column, or diagonal.

Hints:

1. Think backtracking – place queens one row at a time and backtrack when a conflict occurs.
2. Use efficient tracking for attacks: e.g. boolean arrays or bitmasking for columns and diagonals.
3. Prune early – if a partial placement is invalid, cut off that branch immediately.

Approach 1: Brute Force (Permutation Generation)

Idea:

Generate all possible ways to place one queen in each row (or each column) and filter out the arrangements where queens conflict. One straightforward brute force is to consider every permutation of queen positions in rows. Since each of the N queens must go on a different row and column, we can represent a board by a permutation of column indices [c0, c1, ..., c_{N-1}] where c_i is the column of the queen in row i. There are N! such permutations. For each permutation, we check if it’s a valid solution (no diagonal conflicts).

Algorithm:

1. Generate all permutations of size N (each permutation represents queen columns for rows 0 to N-1).
2. For each permutation, check diagonals: no two queens i and j should satisfy abs(i - j) == abs(c_i - c_j) (this is the condition for diagonal attack).
3. If valid, format the permutation into an actual board with 'Q' and '.' and add to results.

This brute force tries all N! possibilities for queen placement (for N=8, that’s 40,320 possibilities after fixing one queen per column ) and checks each for conflicts, so it’s correct but very slow for large N.

Time Complexity:

• O(N! * N) in the worst case. There are N! permutations, and checking each permutation’s diagonals takes up to O(N). This grows factorially and becomes infeasible even for moderate N (e.g. 9! = 362,880 permutations for N=9).

Python Implementation:

Java Implementation:

Explanation: We use cols, main_diag, and anti_diag sets to track attacks. The diagonal indices use row-col and row+col (which remain unique for each diagonal). At each row, only columns not in these sets are tried. This avoids scanning the entire row for conflicts. We modify the board in place and backtrack (undo) the changes after exploring each possibility.

Java Implementation:

This backtracking approach is much more efficient than brute force, but it can still be exponential. It’s sufficient for N up to around 9 (which is within our constraints).

Approach 3: Bitmask Optimization

Idea:

We can further optimize the backtracking approach by using bit masks to represent the columns and diagonals. Bit operations allow us to combine and check conflicts in constant time, and even generate the next valid positions without looping over all columns. The idea is to use an integer’s bits as flags for occupied columns/diagonals: a 1 bit means a column or diagonal is under attack. For an N×N board, we can use an N-bit integer (or larger) for each of the three directions (columns, major diag, minor diag).

At each row, instead of checking each column one by one, we compute a bit mask of all available positions in that row as:

allowed = ~(cols_mask | main_diag_mask | anti_diag_mask) & ((1 << N) - 1)

Here, cols_mask has 1s where columns are occupied, main_diag_mask has 1s where a major diagonal is occupied, and anti_diag_mask for minor diagonals. By OR-ing these masks, we mark all squares that are under attack, then a bitwise NOT gives us 1s for all safe squares. We mask with (1<<N)-1 to ignore bits beyond our board size. Each set bit in allowed now represents a safe column in the current row where we can place a queen without conflict.

Instead of trying columns 0..N-1 in a loop, we can iterate over the set bits of allowed. We pick one set bit (which corresponds to a safe column) and place a queen there, then update the masks for the next row:

• If we place a queen at column c (represented by bit position = 1 << c), we update:
  new_cols_mask = cols_mask | position
new_main_diag_mask = (main_diag_mask | position) << 1 (shift left for next row’s diagonals)
  new_anti_diag_mask = (anti_diag_mask | position) >> 1 (shift right for next row)

Shifting the diagonal masks by 1 moves the attack one column to the left or right for the next row, simulating the diagonal coverage. This way, the masks stay aligned with the current row’s columns at each recursive step.

By using bit arithmetic, we skip over invalid positions efficiently and directly compute the next valid move, rather than checking each column one by one. This yields significant speedups, especially in low-level languages. It’s known to be one of the fastest methods for N-Queens, enabling solving larger boards (N=12, N=13, etc.) that would be very slow with naive backtracking.

Algorithm:

1. Use three integer masks: cols, main_diag, anti_diag, initially all 0 (no attacks).
2. At row r, compute allowed = ~(cols | main_diag | anti_diag) & ((1<<N) - 1). Bits set in allowed correspond to safe columns.
3. While allowed is not 0:
   • Let p = allowed & -allowed pick the lowest-set bit in allowed (a column to try).
   • Set that bit (column) as occupied and place a queen: update cols, main_diag, anti_diag as described above.
   • Recurse to r+1 with the updated masks.
   • Backtrack: unset the chosen bit from allowed (do allowed &= allowed - 1 to remove the lowest-set bit) and continue to try the next position.
4. Each time r == N (placed queens in all rows), record the board configuration. Use bit positions of queens to build the output strings.

This approach still uses recursion to explore different placements, but the operations per position are constant-time bit manipulations. Checking and setting attacks is O(1), and generating all valid positions is also O(1) for each row (since it’s just a few bit ops). The algorithm will examine fewer operations per node in the search tree compared to Approach 2.

Time Complexity:

• O(N!) in the worst case (the search tree doesn’t change its asymptotic size), but the constant factors are greatly reduced. In practice, the bitmask method is the fastest approach for N-Queens on typical hardware. By eliminating loops and using fast bit operations, it can solve N=14 or N=15 in reasonable time in optimized languages. (For example, the number of solutions grows roughly as (0.143N)^N for large N, so this optimization is crucial for exploring those possibilities.)

Python Implementation: