Coding Interview PatternsN-Queens
HardBacktracking

N-Queens

Explanation & Solution

Practice Problem

Description

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

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' indicates a queen and '.' indicates an empty space.

Examples

Example 1

Input: n = 4

Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Explanation: There are two distinct solutions to the 4-queens puzzle.

Example 2

Input: n = 1

Output: [["Q"]]

Explanation: There is only one solution for a 1Ɨ1 board.

Constraints

  • 1 <= n <= 9

Approach

Backtracking pattern

1. Set Up the Board and Tracking Sets

  • Create an n Ɨ n board filled with '.'
  • Use three sets to track which columns and diagonals are under attack: cols, diag1 (row - col), and diag2 (row + col)

2. Backtrack Row by Row

  • Place queens one row at a time starting from row 0
  • For each column in the current row, check if placing a queen is safe by checking all three sets

3. Place and Recurse

  • If a position is safe, place the queen ('Q'), add the column and both diagonals to the tracking sets
  • Recurse to the next row

4. Backtrack

  • After recursion returns, remove the queen and delete the column and diagonals from the tracking sets
  • This allows trying other positions in the same row

5. Collect Solutions

  • When row === n, all queens are placed successfully ā€” snapshot the board as an array of strings and push to results

šŸ§  Key Insight

  • Using sets for columns and both diagonals gives O(1) conflict checking per position. The diagonal trick row - col and row + col uniquely identifies each diagonal direction.
Time
O(n!)at most n choices in row 0, n-1 in row 1, etc.
Space
O(nĀ²) for the board plus **O(n)** for the tracking sets

Solution Code

Next
Word Search