The n-queens problem challenges us to place n queens on an n x n chessboard such that no two queens can attack each other. This means no two queens can be in the same row, column, or diagonal. The goal is to find all possible distinct arrangements of queens on the board that satisfy these conditions.

This problem is typically solved using a backtracking algorithm, which explores possible solutions incrementally, abandoning paths that violate the constraints. The efficiency of the algorithm relies on pruning the search space early by identifying conflicts.

Intuition:

Imagine building the solution row by row. For each row, we try placing a queen in each column. If placing a queen in a particular column doesn't lead to a valid solution (i.e., it conflicts with other queens), we backtrack and try a different column. We use sets to keep track of columns and diagonals that are under attack, making conflict detection O(1).

The core idea is to explore all possible placements, but intelligently prune the search space to avoid unnecessary computations. By keeping track of the attacked columns and diagonals, we can quickly determine if a queen placement is valid, significantly reducing the number of branches we need to explore.

Step-by-step thinking:

Initialize an empty board represented as a 2D char array, and create three sets: col to track occupied columns, posDiag to track occupied positive diagonals (row + col), and negDiag to track occupied negative diagonals (row - col).
The backtrack function is the heart of the solution. It takes the current row r as input. If r equals n, it means we've successfully placed a queen in each row, so we add the current board configuration to the result.
For each column c in the current row r, check if placing a queen at (r, c) is valid. This is done by checking if c is in col, r + c is in posDiag, or r - c is in negDiag.
If the placement is valid, add c to col, r + c to posDiag, and r - c to negDiag. Place a queen 'Q' at board[r][c].
Recursively call backtrack(r + 1) to try placing a queen in the next row.
After the recursive call returns, backtrack by removing c from col, r + c from posDiag, and r - c from negDiag. Also, reset board[r][c] back to '.'. This step is crucial for exploring other possible solutions.
The main function initializes the board and calls backtrack(0) to start the process from the first row.

Time Complexity: O(N!)
Space Complexity: O(N^2)

Learn Complexity

45. N-Queens

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Constraints:

Learn

Topics

Companies

Hint

Use Cases