N-Queens

Hardbacktrackingmatrix
Category: Backtracking
Companies that ask this question:
AmazonGoogleFacebookMicrosoft
LeetCode →NeetCode →

Approach

N-Queens

Problem Statement

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 all distinct solutions to the n-queens puzzle. You may return the answer in any order.

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

Examples

Example 1

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Example 2

Input: n = 1
Output: [["Q"]]

Intuition

Constraint: No two queens in same row, column, or diagonal.

Strategy: Place one queen per row, checking if position is safe.

For each row:

  • Try each column
  • Check if safe (no conflicts with previous queens)
  • If safe, place queen and recurse to next row
  • Backtrack if no solution found

Pattern Recognition

This is a Constraint Satisfaction backtracking problem:

  • Row-by-row placement
  • Validation at each step
  • Multiple solutions exist

Approach

def backtrack(row):
  if row == n:
    result.append(build_board())
    return

  for col in range(n):
    if is_safe(row, col):
      place_queen(row, col)
      backtrack(row + 1)
      remove_queen(row, col)

def is_safe(row, col):
  # Check column
  # Check diagonal (top-left to bottom-right)
  # Check anti-diagonal (top-right to bottom-left)

Optimization: Use sets to track columns and diagonals in O(1).

Complexity Analysis

  • Time: O(n!)

    • First row: n choices
    • Second row: at most n-2 choices
    • Factorial growth

  • Space: O(n²) for board

    • O(n) recursion depth

Solution

java
1import java.util.*;
2
3class Solution {
4    public List<List<String>> solveNQueens(int n) {
5        List<List<String>> result = new ArrayList<>();
6        char[][] board = new char[n][n];
7
8        for (int i = 0; i < n; i++) {
9            Arrays.fill(board[i], '.');
10        }
11
12        Set<Integer> cols = new HashSet<>();
13        Set<Integer> diags = new HashSet<>();
14        Set<Integer> antiDiags = new HashSet<>();
15
16        backtrack(0, n, board, cols, diags, antiDiags, result);
17        return result;
18    }
19
20    private void backtrack(int row, int n, char[][] board,
21                          Set<Integer> cols, Set<Integer> diags,
22                          Set<Integer> antiDiags, List<List<String>> result) {
23        if (row == n) {
24            result.add(buildBoard(board));
25            return;
26        }
27
28        for (int col = 0; col < n; col++) {
29            if (cols.contains(col) ||
30                diags.contains(row - col) ||
31                antiDiags.contains(row + col)) {
32                continue;
33            }
34
35            // Place queen
36            board[row][col] = 'Q';
37            cols.add(col);
38            diags.add(row - col);
39            antiDiags.add(row + col);
40
41            backtrack(row + 1, n, board, cols, diags, antiDiags, result);
42
43            // Remove queen (backtrack)
44            board[row][col] = '.';
45            cols.remove(col);
46            diags.remove(row - col);
47            antiDiags.remove(row + col);
48        }
49    }
50
51    private List<String> buildBoard(char[][] board) {
52        List<String> result = new ArrayList<>();
53        for (char[] row : board) {
54            result.add(new String(row));
55        }
56        return result;
57    }
58}
59
Loading visualizer...