Scale Engineer

N-Queens II

Hard
#0052Time: O(N!)Space: O(N)7 companies
Patterns
Backtracking
Companies
AmazonBloombergGoogleMicrosoft

Prompt

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

 

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

 

Constraints:

  • 1 <= n <= 9

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a standard backtracking algorithm to explore all possible placements of queens. We build the solution row by row, ensuring that each new queen placed does not attack any previously placed queens. To efficiently check for attacks, we use helper boolean arrays to keep track of which columns and diagonals are already occupied.

Algorithm

  • Initialize a global or member variable count to store the number of solutions.
  • Create three boolean arrays to keep track of occupied columns and diagonals:
    • cols of size n.
    • diag1 of size 2*n - 1 for main diagonals (row - col).
    • diag2 of size 2*n - 1 for anti-diagonals (row + col).
  • Implement a recursive backtracking function, say backtrack(row).
  • Base Case: If row == n, it means we have successfully placed n queens. Increment count and return.
  • Recursive Step: Iterate through each column col from 0 to n-1 for the current row.
    • Calculate the indices for the two diagonals: d1 = row - col + n - 1 and d2 = row + col.
    • Check if the current position (row, col) is safe by checking if cols[col], diag1[d1], and diag2[d2] are all false.
    • If the position is safe:
      1. Place Queen: Mark cols[col], diag1[d1], and diag2[d2] as true.
      2. Recurse: Call backtrack(row + 1) to solve for the next row.
      3. Backtrack: Un-place the queen by resetting cols[col], diag1[d1], and diag2[d2] to false. This allows exploration of other possibilities.
  • Start the process by calling backtrack(0).
  • Return the final count.

Walkthrough

The core idea is to place one queen in each row, starting from row 0. For each row, we iterate through all columns to find a safe square. A square (row, col) is considered safe if no other queen (in rows 0 to row-1) is in the same column, same main diagonal, or same anti-diagonal.

We use three boolean arrays to maintain the state:

  • cols[c] is true if a queen is already placed in column c.
  • diag1[r-c+n-1] is true if a queen is on the main diagonal identified by r-c. We add n-1 to map the result (which can be negative) to a valid array index.
  • diag2[r+c] is true if a queen is on the anti-diagonal identified by r+c.

When the recursive function backtrack(row) is called, it tries to place a queen in each column of that row. If a safe column is found, it marks the corresponding column and diagonals as occupied, and then makes a recursive call for the next row, backtrack(row + 1). After the recursive call returns, it backtracks by un-marking the column and diagonals, allowing the exploration of placing the queen in other columns of the current row. If the recursion reaches row == n, a valid solution has been found, and we increment a counter.

class Solution {    private int count = 0;    private boolean[] cols;    private boolean[] diag1;    private boolean[] diag2;    private int n;     public int totalNQueens(int n) {        this.n = n;        this.cols = new boolean[n];        this.diag1 = new boolean[2 * n - 1];        this.diag2 = new boolean[2 * n - 1];        backtrack(0);        return count;    }     private void backtrack(int row) {        if (row == n) {            count++;            return;        }         for (int col = 0; col < n; col++) {            int d1_idx = row - col + n - 1;            int d2_idx = row + col;             if (cols[col] || diag1[d1_idx] || diag2[d2_idx]) {                continue;            }             // Place the queen            cols[col] = true;            diag1[d1_idx] = true;            diag2[d2_idx] = true;             // Recurse for the next row            backtrack(row + 1);             // Backtrack (remove the queen)            cols[col] = false;            diag1[d1_idx] = false;            diag2[d2_idx] = false;        }    }}

Complexity

Time

O(N!)

Space

O(N)

Trade-offs

Pros

  • The logic is straightforward and closely follows the definition of the N-Queens problem.

  • It's a general backtracking template that can be adapted to similar constraint satisfaction problems.

Cons

  • Slightly less performant than the bitmasking approach due to the overhead of array indexing and assignments compared to fast bitwise operations.

  • Uses more memory to store the boolean arrays compared to a few integers.

Solutions

public class Solution {    public int TotalNQueens(int n) {        bool[] cols = new bool[10];        bool[] dg = new bool[20];        bool[] udg = new bool[20];        int ans = 0;        void dfs(int i) {            if (i == n) {                ans++;                return;            }            for (int j = 0; j < n; j++) {                int a = i + j, b = i - j + n;                if (cols[j] || dg[a] || udg[b]) {                    continue;                }                cols[j] = dg[a] = udg[b] = true;                dfs(i + 1);                cols[j] = dg[a] = udg[b] = false;            }        }        dfs(0);        return ans;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem