N Queens | Backtracking

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.

Enter fullscreen mode Exit fullscreen mode

For each column:

Try every row.

Enter fullscreen mode Exit fullscreen mode

Before placing a queen:

Check if the position is safe.

Enter fullscreen mode Exit fullscreen mode

If safe:

Place Queen
Recurse
Backtrack

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

If current cell is safe:

Place Queen

Enter fullscreen mode Exit fullscreen mode

Otherwise:

Skip

Enter fullscreen mode Exit fullscreen mode

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;
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

n = 4

Enter fullscreen mode Exit fullscreen mode

Column 0 → Place Queen

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

Enter fullscreen mode Exit fullscreen mode

Column 1 → Try safe rows

Enter fullscreen mode Exit fullscreen mode

Continue until:

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode