N Queens | Backtracking

leetcode.com

Problem Statement

Place N queens on an N x N chessboard such that:

• No two queens attack each other.
• Queens cannot share:
  • Row
  • Column
  • Diagonal

Return all possible valid board configurations.

---

Brute Force Intuition

Try placing queens in every possible cell.

After placing all queens, check whether the board is valid.

Most configurations are invalid, making brute force extremely expensive.

Complexity

• Time Complexity: O(N^N)
• Space Complexity: O(N²)

---

Moving Towards the Optimal Approach

Instead of placing queens randomly:

Place one queen per column.

For each column:

Try every row.

Before placing a queen:

Check if the position is safe.

If safe:

Place Queen
Recurse
Backtrack

---

Pattern Recognition

Whenever you see:

• Generate all valid arrangements
• Constraints while placing elements
• Chessboard problems

Think:

Backtracking + Constraint Checking

---

Key Observation

For each column:

Try all rows

If current cell is safe:

Place Queen

Otherwise:

Skip

---

Optimal Java Solution

class Solution {

    public List<List<String>> solveNQueens(int n) {

        List<List<String>> ans = new ArrayList<>();

        char[][] board = new char[n][n];

        for (char[] row : board) {
            Arrays.fill(row, '.');
        }

        solve(0, board, ans);

        return ans;
    }

    private void solve(int col,
                       char[][] board,
                       List<List<String>> ans) {

        if (col == board.length) {

            List<String> temp = new ArrayList<>();

            for (char[] row : board) {
                temp.add(new String(row));
            }

            ans.add(temp);
            return;
        }

        for (int row = 0; row < board.length; row++) {

            if (isSafe(row, col, board)) {

                board[row][col] = 'Q';

                solve(col + 1, board, ans);

                board[row][col] = '.';
            }
        }
    }

    private boolean isSafe(int row,
                           int col,
                           char[][] board) {

        int r = row;
        int c = col;

        while (c >= 0) {
            if (board[r][c] == 'Q')
                return false;
            c--;
        }

        r = row;
        c = col;

        while (r >= 0 && c >= 0) {
            if (board[r][c] == 'Q')
                return false;
            r--;
            c--;
        }

        r = row;
        c = col;

        while (r < board.length && c >= 0) {
            if (board[r][c] == 'Q')
                return false;
            r++;
            c--;
        }

        return true;
    }
}

---

Dry Run

n = 4

Column 0 → Place Queen

Q . . .
. . . .
. . . .
. . . .

Column 1 → Try safe rows

Continue until:

. . Q .
Q . . .
. . . Q
. Q . .

Valid Solution

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(N!)
Space Complexity	O(N²)

---

Interview One-Liner

Place one queen column by column, checking whether the current position is safe. Backtrack whenever a conflict occurs.

---

Memory Trick

Column Wise Placement

Try Row
↓
Safe?
↓
Place Queen
↓
Recurse
↓
Backtrack