What happens if you not checking diagonal conflicts correctly?

Invalid solutions with attacking queens are included Fix: Check both diagonals using row-col and row+col indices

What happens if you modifying board without backtracking (not resetting)?

Subsequent recursive calls see corrupted board state Fix: Reset board cell to '.' after recursive call returns

What happens if you using global variables without resetting between test cases?

Solutions accumulate incorrectly or cause errors Fix: Initialize all data structures inside the main function or reset before each run

What happens if you incorrect bitmask operations (e.g., wrong shifts)?

Missed or extra attacks cause wrong pruning and wrong answers Fix: Use correct left shift for one diagonal and right shift for the other

Interview PrepbacktrackinghardAmazonFacebookGoogleMicrosoft

N-Queens

Choose your preparation mode3 modes available

Try It Solution Trace

🎯

N-Queens

hardBACKTRACKINGAmazonFacebookGoogle

Imagine you are organizing a chess tournament and need to place n queens on an n×n chessboard so that no two queens threaten each other. How can you arrange them safely?

💡 This is a classic backtracking problem where you try to place queens row by row, checking constraints. Beginners struggle because the search space is huge and pruning invalid positions efficiently is key.

📋

Problem Statement

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' and '.' both indicate a queen and an empty space respectively. No two queens can attack each other horizontally, vertically, or diagonally.

1 ≤ n ≤ 10Output all distinct solutions in any order

💡

Example

Input"4"

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

There are two distinct ways to place 4 queens so that none attack each other.

n = 1 → [['Q']]
n = 2 → [] (no solutions)
n = 3 → [] (no solutions)
n = 8 → multiple solutions (classic chessboard size)

⚠️

Common Mistakes

Not checking diagonal conflicts correctly

Invalid solutions with attacking queens are included

✅ Check both diagonals using row-col and row+col indices

Modifying board without backtracking (not resetting)

Subsequent recursive calls see corrupted board state

✅ Reset board cell to '.' after recursive call returns

Using global variables without resetting between test cases

Solutions accumulate incorrectly or cause errors

✅ Initialize all data structures inside the main function or reset before each run

Incorrect bitmask operations (e.g., wrong shifts)

Missed or extra attacks cause wrong pruning and wrong answers

✅ Use correct left shift for one diagonal and right shift for the other

Not handling n < 1 or trivial cases

Code may crash or return incorrect results

✅ Add base case checks for n=1 or invalid inputs

🧠

Brute Force (Pure Recursion with Board Validation)

💡 This approach tries every possible placement of queens on the board and checks if the board is valid after each placement. It is slow but helps understand the problem deeply.

Intuition

Place queens row by row, and for each row try every column. After placing a queen, check if the board is still valid by scanning all previously placed queens.

Algorithm

Start from the first row.
Try placing a queen in each column of the current row.
After placing, check if the board is valid (no two queens attack).
If valid, recurse to the next row; if all rows are placed, record the solution.

💡 The main challenge is the validation step after each placement, which is costly and repeated many times.

</>

Code

def solveNQueens(n):
    def is_valid(board, row, col):
        for i in range(row):
            for j in range(n):
                if board[i][j] == 'Q':
                    if j == col or abs(row - i) == abs(col - j):
                        return False
        return True

    def backtrack(row, board, solutions):
        if row == n:
            solutions.append([''.join(r) for r in board])
            return
        for col in range(n):
            board[row][col] = 'Q'
            if is_valid(board, row, col):
                backtrack(row + 1, board, solutions)
            board[row][col] = '.'

    board = [['.' for _ in range(n)] for _ in range(n)]
    solutions = []
    backtrack(0, board, solutions)
    return solutions

# Example usage:
if __name__ == '__main__':
    print(solveNQueens(4))

Line Notes

def is_valid(board, row, col):Defines a helper to check if placing a queen at (row, col) is safe

for i in range(row):Check all previously placed queens in rows above current row

if j == col or abs(row - i) == abs(col - j):Check same column or diagonal conflicts

if row == n:Base case: all rows have queens placed, record solution

import java.util.*;
public class NQueensBrute {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(board[i], '.');
        backtrack(0, board, solutions, n);
        return solutions;
    }

    private void backtrack(int row, char[][] board, List<List<String>> solutions, int n) {
        if (row == n) {
            List<String> solution = new ArrayList<>();
            for (char[] r : board) solution.add(new String(r));
            solutions.add(solution);
            return;
        }
        for (int col = 0; col < n; col++) {
            board[row][col] = 'Q';
            if (isValid(board, row, col, n)) {
                backtrack(row + 1, board, solutions, n);
            }
            board[row][col] = '.';
        }
    }

    private boolean isValid(char[][] board, int row, int col, int n) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'Q') {
                    if (j == col || Math.abs(row - i) == Math.abs(col - j)) return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        NQueensBrute solver = new NQueensBrute();
        System.out.println(solver.solveNQueens(4));
    }
}

Line Notes

public List<List<String>> solveNQueens(int n)Entry point to solve the problem and store solutions

for (int col = 0; col < n; col++)Try placing queen in each column of current row

if (isValid(board, row, col, n))Check if current placement is safe before recursing

if (row == n)All queens placed, add current board to solutions

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> solutions;
        vector<string> board(n, string(n, '.'));
        backtrack(0, board, solutions, n);
        return solutions;
    }

private:
    void backtrack(int row, vector<string>& board, vector<vector<string>>& solutions, int n) {
        if (row == n) {
            solutions.push_back(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            board[row][col] = 'Q';
            if (isValid(board, row, col, n)) {
                backtrack(row + 1, board, solutions, n);
            }
            board[row][col] = '.';
        }
    }

    bool isValid(const vector<string>& board, int row, int col, int n) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'Q') {
                    if (j == col || abs(row - i) == abs(col - j)) return false;
                }
            }
        }
        return true;
    }
};

int main() {
    Solution sol;
    auto res = sol.solveNQueens(4);
    for (auto& board : res) {
        for (auto& row : board) cout << row << endl;
        cout << endl;
    }
    return 0;
}

Line Notes

vector<string> board(n, string(n, '.'))Initialize board with '.' indicating empty cells

for (int col = 0; col < n; col++)Try placing queen in each column of current row

if (isValid(board, row, col, n))Validate placement before deeper recursion

if (row == n)All queens placed, add current board to solutions

function solveNQueens(n) {
    const solutions = [];
    const board = Array.from({ length: n }, () => '.'.repeat(n).split(''));

    function isValid(row, col) {
        for (let i = 0; i < row; i++) {
            for (let j = 0; j < n; j++) {
                if (board[i][j] === 'Q') {
                    if (j === col || Math.abs(row - i) === Math.abs(col - j)) return false;
                }
            }
        }
        return true;
    }

    function backtrack(row) {
        if (row === n) {
            solutions.push(board.map(r => r.join('')));
            return;
        }
        for (let col = 0; col < n; col++) {
            board[row][col] = 'Q';
            if (isValid(row, col)) {
                backtrack(row + 1);
            }
            board[row][col] = '.';
        }
    }

    backtrack(0);
    return solutions;
}

// Example usage:
console.log(solveNQueens(4));

Line Notes

const board = Array.from({ length: n }, () => '.'.repeat(n).split(''))Initialize 2D board with '.' for empty cells

for (let col = 0; col < n; col++)Try placing queen in each column of current row

if (isValid(row, col))Check if current placement is safe before recursing

if (row === n)All queens placed, add current board to solutions

⏱

Complexity

TimeO(n! * n)

SpaceO(n^2)

We try placing queens row by row, each row has up to n columns. Checking validity takes O(n) per placement, leading to factorial time in worst case.

💡 For n=4, this means roughly 4! * 4 = 96 operations, which is manageable, but for n=10 it explodes to millions.

Interview Verdict: TLE for large n, but good for understanding

This approach is too slow for big boards but is essential to grasp the problem and backtracking basics.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n! * n)`	`O(n^2)`	Yes (deep recursion)	Yes	Mention only - never code
2. Backtracking with Column and Diagonal Pruning	`O(n!)`	`O(n)`	Yes (deep recursion)	Yes	Code this approach in interviews
3. Bitmask Optimization	`O(n!)`	`O(n)`	Yes (deep recursion)	Yes	Mention or code if comfortable with bitwise ops

N-Queens

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems