Course4all
Join us on telegram
Home/dsa/Backtracking/N-Queens

N-Queens

Master this topic with zero to advance depth.

N-Queens

The Constraint Logic

The N-Queens puzzle is about placing NN chess queens on an N×NN \times N chessboard so that no two queens threaten each other. A queen can attack in 3 ways: Row, Column, and Diagonal.

Efficient Collision Detection

Instead of checking every cell on the board (which is O(N)O(N)), we can use boolean arrays to mark occupied lanes:

  1. Column: Index c
  2. Main Diagonal: Index r - c (constant along the diagonal)
  3. Anti-Diagonal: Index r + c (constant along the diagonal)

Place N queens on an N x N board without conflicts. Includes visual 4-Queens solution.

Hard

Examples

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

Level I: Backtracking with Validation Function

Intuition

Place queens row by row. For each valid column in a row, move to the next row.

For each row r, try placing a queen at (r, c) where c from 00 to N−1N-1. Check if (r, c) is safe by scanning all previously placed queens.

⏱ O(N!)💾 O(N^2) to store the board.

Detailed Dry Run

Dry Run: N=4 | Row | Action | Collision Check | | :-- | :--------------- | :-------------- | | 0 | Place (0,0) | Valid | | 1 | Try (1,0), (1,1) | ❌ Col/Diag | | 1 | Place (1,2) | Valid | | 2 | Try (2,0)..(2,3) | ❌ ALL COLLIDE | | 1 | Backtrack (1,2) | Try (1,3)... |
java
class Solution {
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(board[i], '.');
        List<List<String>> res = new ArrayList<>();
        backtrack(0, board, res);
        return res;
    }
    private void backtrack(int r, char[][] board, List<List<String>> res) {
        if (r == board.length) {
            res.add(construct(board));
            return;
        }
        for (int c = 0; c < board.length; c++) {
            if (isSafe(r, c, board)) {
                board[r][c] = 'Q';
                backtrack(r + 1, board, res);
                board[r][c] = '.';
            }
        }
    }
    private boolean isSafe(int r, int c, char[][] board) {
        for (int i = 0; i < r; i++) {
            for (int k = 0; k < board.length; k++) {
                if (board[i][k] == 'Q' && (k == c || Math.abs(r-i) == Math.abs(c-k))) return false;
            }
        }
        return true;
    }
    private List<String> construct(char[][] board) {
        List<String> path = new ArrayList<>();
        for (int i = 0; i < board.length; i++) path.add(new String(board[i]));
        return path;
    }
}
Approach 2

Level II: Optimized Backtracking (Hashing O(1) Checks)

Intuition

Use boolean arrays/sets to track occupied columns and diagonals for immediate collision detection.

Maintain cols, diag1 (r−cr-c), and diag2 (r+cr+c) sets. Before placing a queen at (r,c)(r, c), check if cc, r−cr-c, or r+cr+c are in the sets.

⏱ O(N!)💾 O(N) to store sets.

Detailed Dry Run

Place (0,0): cols={0}, d1={0}, d2={0} Row 1: (1,1) fails (d1), (1,2) ok (c=2, d1=-1, d2=3).

java
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(0, new HashSet<>(), new HashSet<>(), new HashSet<>(), board, res);
        return res;
    }
    private void backtrack(int r, Set<Integer> cols, Set<Integer> d1, Set<Integer> d2, char[][] board, List<List<String>> res) {
        if (r == board.length) {
            List<String> sol = new ArrayList<>();
            for (char[] row : board) sol.add(new String(row));
            res.add(sol); return;
        }
        for (int c = 0; c < board.length; c++) {
            if (cols.contains(c) || d1.contains(r - c) || d2.contains(r + c)) continue;
            board[r][c] = 'Q';
            cols.add(c); d1.add(r - c); d2.add(r + c);
            backtrack(r + 1, cols, d1, d2, board, res);
            board[r][c] = '.';
            cols.remove(c); d1.remove(r - c); d2.remove(r + c);
        }
    }
}
Approach 3

Level III: Bit Manipulation (Ultimate Speed)

Intuition

Use integers as bitmasks to represent occupied columns and diagonals. This is the fastest way because bitwise operations are extremely cheap.

Let cols, ld (left-diagonal), and rd (right-diagonal) be integers. For each row, the available slots are ~(cols | ld | rd) & mask. Placing a queen update masks: cols | p, (ld | p) << 1, (rd | p) >> 1.

⏱ O(N!)💾 O(N)

Detailed Dry Run

N=4, mask=1111 Row 0: Try p=0001. New cols=0001, ld=0010, rd=0000 Row 1: Try p=0100...

← Previous QuestionWord Search
Next Question →Combinations