51. N-Queens - Solution & Explanation

The problem

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.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

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

Constraints:

1 <= n <= 9

Approach overview

Problem Overview: Place n queens on an n x n chessboard so that no two queens attack each other. A queen attacks horizontally, vertically, and diagonally, so every placement must avoid conflicts in the same column or diagonal.

Approach 1: Backtracking with Row-wise Construction (Time: O(N!), Space: O(N) to O(N²))

This approach builds the board one row at a time using backtracking. For each row, try placing a queen in every column and check whether that column or either diagonal already contains a queen. Validity checks typically use three structures: a column set, a major diagonal set (row - col), and a minor diagonal set (row + col). If a position is safe, place the queen, recurse to the next row, and backtrack if the placement leads to no valid continuation.

The key insight: once you place exactly one queen per row, you eliminate horizontal conflicts entirely. The algorithm only needs to track columns and diagonals. The recursion explores a decision tree with branching factor up to N, leading to worst‑case time complexity of about O(N!). Space complexity is O(N) for recursion and tracking structures, or O(N²) if you store the entire board explicitly. This is the standard solution used in most explanations of the classic N‑Queens puzzle.

Backtracking works well here because the constraints prune the search tree early. As soon as a queen conflicts with an existing one, the branch stops expanding. Problems involving placement and constraint satisfaction often use arrays to represent board state combined with recursive exploration.

Approach 2: Bit Manipulation Optimization (Time: O(N!), Space: O(N))

This version replaces sets or arrays with integer bitmasks to represent occupied columns and diagonals. Each bit in an integer corresponds to a column. Three masks track constraints: cols, diag1 (major diagonal), and diag2 (minor diagonal). At each row, compute available positions using bit operations such as ~(cols | diag1 | diag2), then extract the lowest set bit to place a queen.

After placing a queen, update masks using shifts: (diag1 | pos) << 1 and (diag2 | pos) >> 1. Bit operations make conflict checks constant time and eliminate hash structures. The theoretical complexity remains O(N!), but the constant factors are significantly smaller. This technique is common in optimized competitive programming solutions and scales better for larger n.

Recommended for interviews: Interviewers typically expect the row‑wise backtracking solution. It clearly demonstrates recursive search, pruning logic, and constraint tracking. The bitmask version shows deeper optimization skills and strong understanding of state compression. Starting with classic backtracking and then discussing bitmask improvements signals strong problem‑solving depth.

Approach 1: Backtracking with Row-wise Construction

This approach involves using backtracking to place queens row by row, exploring valid positions recursively. Each queen placement is validated based on column and diagonal restrictions. If a valid placement is found, the algorithm progresses to the next row, otherwise it backtracks and attempts alternative placements.

Python

from typing import List

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def backtrack(row = 0, cols = 0, d1 = 0, d2 = 0, solution = []):
            if row == n:
                results.append(solution)
            else:
                for col in range(n):
                    if not (cols & (1 << col)) and not (d1 & (1 << (row - col + n - 1))) and not (d2 & (1 << (row + col))):
                        backtrack(row + 1, 
                                  cols | (1 << col), 
                                  d1 | (1 << (row - col + n - 1)),
                                  d2 | (1 << (row + col)),
                                  solution + [col])

        results = []
        backtrack()
        return [["." * i + "Q" + "." * (n - i - 1) for i in solution] for solution in results]

s = Solution()
print(s.solveNQueens(4))

Java

import java.util.*;

public class NQueens {
    private List<List<String>> solutions = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        boolean[] cols = new boolean[n];
        boolean[] d1 = new boolean[2 * n];
        boolean[] d2 = new boolean[2 * n];
        backtrack(board, 0, cols, d1, d2);
        return solutions;
    }

    private void backtrack(char[][] board, int row, boolean[] cols, boolean[] d1, boolean[] d2) {
        int n = board.length;
        if (row == n) {
            solutions.add(transform(board));
            return;
        }

        for (int col = 0; col < n; col++) {
            int id1 = col - row + n;
            int id2 = col + row;
            if (!cols[col] && !d1[id1] && !d2[id2]) {
                board[row][col] = 'Q';
                cols[col] = d1[id1] = d2[id2] = true;
                backtrack(board, row + 1, cols, d1, d2);
                board[row][col] = '.';
                cols[col] = d1[id1] = d2[id2] = false;
            }
        }
    }

    private List<String> transform(char[][] board) {
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            ret.add(new String(board[i]));
        }
        return ret;
    }

    public static void main(String[] args) {
        NQueens nQueens = new NQueens();
        List<List<String>> solutions = nQueens.solveNQueens(4);
        for (List<String> solution : solutions) {
            for (String row : solution) {
                System.out.println(row);
            }
            System.out.println();
        }
    }
}

C++

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

void backtrack(vector<vector<string>>& solutions, vector<string>& board, vector<bool>& cols, vector<bool>& d1, vector<bool>& d2, int row, int n) {
    if (row == n) {
        solutions.push_back(board);
        return;
    }

    for (int col = 0; col < n; col++) {
        int id1 = col - row + n;
        int id2 = col + row;
        if (!cols[col] && !d1[id1] && !d2[id2]) {
            board[row][col] = 'Q';
            cols[col] = d1[id1] = d2[id2] = true;
            backtrack(solutions, board, cols, d1, d2, row + 1, n);
            board[row][col] = '.';
            cols[col] = d1[id1] = d2[id2] = false;
        }
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> solutions;
    vector<string> board(n, string(n, '.'));
    vector<bool> cols(n, false), d1(2 * n, false), d2(2 * n, false);
    backtrack(solutions, board, cols, d1, d2, 0, n);
    return solutions;
}

int main() {
    int n = 4;
    vector<vector<string>> solutions = solveNQueens(n);
    for (auto& solution : solutions) {
        for (string& row : solution) {
            cout << row << endl;
        }
        cout << endl;
    }
    return 0;
}

JavaScript

function solveNQueens(n) {
    const solutions = [];

    function isSafe(board, row, col) {
        for (let i = 0; i < row; i++) {
            if (board[i] === col ||
                board[i] - i === col - row ||
                board[i] + i === col + row) {
                return false;
            }
        }
        return true;
    }

    function placeQueens(row, board) {
        if (row === n) {
            solutions.push(board.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)));
            return;
        }
        for (let col = 0; col < n; col++) {
            if (isSafe(board, row, col)) {
                board[row] = col;
                placeQueens(row + 1, board);
            }
        }
    }

    placeQueens(0, []);
    return solutions;
}

const solutions = solveNQueens(4);
console.log(solutions);

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool isValid(int row, int col, int* queens) {
    for (int i = 0; i < row; ++i) {
        int placedQueenCol = queens[i];
        if (placedQueenCol == col || 
            placedQueenCol - col == row - i || 
            placedQueenCol - col == i - row) {
            return false;
        }
    }
    return true;
}

void solve(int n, int row, int* queens, char** board, int* resultCount, char**** results) {
    if (row == n) {
        *results = realloc(*results, sizeof(char**) * (*resultCount + 1));
        char** newSolution = (char**)malloc(sizeof(char*) * n);
        for (int i = 0; i < n; ++i) {
            newSolution[i] = (char*)malloc(sizeof(char) * (n + 1));
            for (int j = 0; j < n; ++j) {
                newSolution[i][j] = board[i][j];
            }
            newSolution[i][n] = '\0';
        }
        (*results)[*resultCount] = newSolution;
        (*resultCount)++;
        return;
    }

    for (int col = 0; col < n; ++col) {
        if (isValid(row, col, queens)) {
            queens[row] = col;
            board[row][col] = 'Q';
            solve(n, row + 1, queens, board, resultCount, results);
            board[row][col] = '.';  // backtrack
        }
    }
}

char*** solveNQueens(int n, int* returnSize) {
    char*** results = (char***)malloc(sizeof(char**));
    *returnSize = 0;
    int* queens = malloc(sizeof(int) * n);
    char** board = malloc(sizeof(char*) * n);
    for (int i = 0; i < n; ++i) {
        board[i] = malloc(sizeof(char) * (n));
        for (int j = 0; j < n; ++j) {
            board[i][j] = '.';
        }
    }
    solve(n, 0, queens, board, returnSize, &results);
    for (int i = 0; i < n; ++i) {
        free(board[i]);
    }
    free(board);
    free(queens);
    return results;
}

int main() {
    int n = 4;
    int returnSize;
    char*** results = solveNQueens(n, &returnSize);
    for (int i = 0; i < returnSize; ++i) {
        for (int j = 0; j < n; ++j) {
            printf("%s\n", results[i][j]);
        }
        printf("\n");
    }
    return 0;
}

using System;
using System.Collections.Generic;

public class NQueens {
    private List<IList<string>> result = new List<IList<string>>();

    public IList<IList<string>> SolveNQueens(int n) {
        char[][] board = new char[n][];
        for (int i = 0; i < n; i++) {
            board[i] = new char[n];
            Array.Fill(board[i], '.');
        }
        bool[] cols = new bool[n];
        bool[] d1 = new bool[2 * n];
        bool[] d2 = new bool[2 * n];
        Backtrack(board, 0, n, cols, d1, d2);
        return result;
    }

    private void Backtrack(char[][] board, int row, int n, bool[] cols, bool[] d1, bool[] d2) {
        if (row == n) {
            List<string> solution = new List<string>();
            foreach (var rowArray in board) {
                solution.Add(new string(rowArray));
            }
            result.Add(solution);
            return;
        }

        for (int col = 0; col < n; col++) {
            int id1 = col - row + n;
            int id2 = col + row;
            if (!cols[col] && !d1[id1] && !d2[id2]) {
                board[row][col] = 'Q';
                cols[col] = d1[id1] = d2[id2] = true;
                Backtrack(board, row + 1, n, cols, d1, d2);
                board[row][col] = '.';
                cols[col] = d1[id1] = d2[id2] = false;
            }
        }
    }

    static void Main() {
        NQueens nq = new NQueens();
        var solutions = nq.SolveNQueens(4);
        foreach (var board in solutions) {
            foreach (string row in board) {
                Console.WriteLine(row);
            }
            Console.WriteLine();
        }
    }
}

This Python solution employs a bit manipulation technique for efficient bitmask checking of column and diagonal occupation. The goal is to reduce overhead by leveraging bitwise operations. The backtrack function tries possibilities recursively, assembling string results once a complete solution is identified.

Complexity

Time Complexity: O(N!), as we have potential N placements per row.
Space Complexity: O(N^2), from solutions storage and recursion factoring.

Try this approach in the editor

Approach 2: Bit Manipulation Optimization

This approach optimizes the placement verification using bit manipulation, reducing the auxiliary space by managing columns and diagonals in integer bitmasks. This permits efficient bitwise operations for placing queens and checking potential attacks.

Python

from typing import List

def solveNQueens(n: int) -> List[List[str]]:
    def dfs(queens, xy_diff, xy_sum):
        p = len(queens)
        if p == n:
            result.append(queens)
            return None
        for q in range(n):
            if q not in queens and p-q not in xy_diff and p+q not in xy_sum:  
                dfs(queens+[q], xy_diff+[p-q], xy_sum+[p+q])
    result = []
    dfs([], [], [])
    return [["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]

solutions = solveNQueens(4)
print(solutions)

Java

import java.util.*;

public class NQueensBitManipulation {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>();
        solve(solutions, new ArrayList<>(), 0, 0, 0, n);
        return solutions;
    }

    private void solve(List<List<String>> solutions, List<Integer> queens, int cols, int diags1, int diags2, int n) {
        int row = queens.size();
        if (row == n) {
            solutions.add(generateSolution(queens, n));
        } else {
            for (int col = 0; col < n; col++) {
                int d1 = row - col + n;
                int d2 = row + col;
                if ((cols & (1 << col)) == 0 && (diags1 & (1 << d1)) == 0 && (diags2 & (1 << d2)) == 0) {
                    queens.add(col);
                    solve(solutions, queens, cols | (1 << col), diags1 | (1 << d1), diags2 | (1 << d2), n);
                    queens.remove(queens.size() - 1);
                }
            }
        }
    }

    private List<String> generateSolution(List<Integer> queens, int n) {
        List<String> solution = new ArrayList<>();
        for (int i : queens) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[i] = 'Q';
            solution.add(new String(row));
        }
        return solution;
    }

    public static void main(String[] args) {
        NQueensBitManipulation nQueens = new NQueensBitManipulation();
        List<List<String>> solutions = nQueens.solveNQueens(4);
        for (List<String> solution : solutions) {
            for (String row : solution) {
                System.out.println(row);
            }
            System.out.println();
        }
    }
}

This Python implementation enhances the typical backtracking with bit positioning. The current column and diagonals are represented with list-formed negative and positive differential tracking to accommodate queen positions and check constraints efficiently.

Complexity

Time Complexity: O(N!), each row considers N placements, simplified by binary check.
Space Complexity: O(N), due to condensed state tracking via differential lists.

Try this approach in the editor

Approach 3: DFS (Backtracking)

We define three arrays col, dg, and udg to represent whether there is a queen in the column, the main diagonal, and the anti-diagonal, respectively. If there is a queen at position (i, j), then col[j], dg[i + j], and udg[n - i + j] are all 1. In addition, we use an array g to record the current state of the chessboard, where all elements in g are initially '.'.

Next, we define a function dfs(i), which represents placing queens starting from the ith row.

In dfs(i), if i = n, it means that we have completed the placement of all queens. We put the current g into the answer array and end the recursion.

Otherwise, we enumerate each column j of the current row. If there is no queen at position (i, j), that is, col[j], dg[i + j], and udg[n - i + j] are all 0, then we can place a queen, that is, change g[i][j] to 'Q', and set col[j], dg[i + j], and udg[n - i + j] to 1. Then we continue to search the next row, that is, call dfs(i + 1). After the recursion ends, we need to change g[i][j] back to '.' and set col[j], dg[i + j], and udg[n - i + j] to 0.

In the main function, we call dfs(0) to start recursion, and finally return the answer array.

The time complexity is O(n^2 times n!), and the space complexity is O(n). Here, n is the integer given in the problem.

TypeScript

function solveNQueens(n: number): string[][] {
    const col: number[] = Array(n).fill(0);
    const dg: number[] = Array(n << 1).fill(0);
    const udg: number[] = Array(n << 1).fill(0);
    const ans: string[][] = [];
    const t: string[][] = Array.from({ length: n }, () => Array(n).fill('.'));
    const dfs = (i: number) => {
        if (i === n) {
            ans.push(t.map(x => x.join('')));
            return;
        }
        for (let j = 0; j < n; ++j) {
            if (col[j] + dg[i + j] + udg[n - i + j] === 0) {
                t[i][j] = 'Q';
                col[j] = dg[i + j] = udg[n - i + j] = 1;
                dfs(i + 1);
                col[j] = dg[i + j] = udg[n - i + j] = 0;
                t[i][j] = '.';
            }
        }
    };
    dfs(0);
    return ans;
}

func solveNQueens(n int) (ans [][]string) {
	col := make([]int, n)
	dg := make([]int, n<<1)
	udg := make([]int, n<<1)
	t := make([][]byte, n)
	for i := range t {
		t[i] = make([]byte, n)
		for j := range t[i] {
			t[i][j] = '.'
		}
	}
	var dfs func(int)
	dfs = func(i int) {
		if i == n {
			tmp := make([]string, n)
			for i := range tmp {
				tmp[i] = string(t[i])
			}
			ans = append(ans, tmp)
			return
		}
		for j := 0; j < n; j++ {
			if col[j]+dg[i+j]+udg[n-i+j] == 0 {
				col[j], dg[i+j], udg[n-i+j] = 1, 1, 1
				t[i][j] = 'Q'
				dfs(i + 1)
				t[i][j] = '.'
				col[j], dg[i+j], udg[n-i+j] = 0, 0, 0
			}
		}
	}
	dfs(0)
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Backtracking with Row-wise Construction	Time Complexity: O(N!), as we have potential N placements per row. Space Complexity: O(N^2), from solutions storage and recursion factoring.
Bit Manipulation Optimization	Time Complexity: O(N!), each row considers N placements, simplified by binary check. Space Complexity: O(N), due to condensed state tracking via differential lists.
DFS (Backtracking)	–

Complexity analysis

Approach	Time	Space	When to Use
Backtracking with Row-wise Construction	O(N!)	O(N) to O(N²)	Standard interview solution. Clear logic and easy to explain constraint checking.
Bit Manipulation Optimization	O(N!)	O(N)	Performance‑optimized version using bitmasks. Preferred in competitive programming or large N.

Frequently asked questions

Is N-Queens easy or hard?

N-Queens is considered a hard problem because it requires recursive search with pruning and careful state tracking. The challenge comes from efficiently eliminating invalid placements while exploring all valid board configurations.

How to solve N-Queens in O(n)?

N-Queens cannot be solved in O(N) time when generating all valid board configurations. The search space grows factorially, leading to about O(N!) complexity. Optimizations like bitmasking reduce constant overhead but do not change the overall factorial growth.

What is the best approach for N-Queens?

Backtracking with row-wise construction is the most common and interview-friendly approach. It places one queen per row and tracks used columns and diagonals to prune invalid states. The algorithm explores placements recursively with about O(N!) time complexity and O(N) extra space for tracking constraints.

What data structure is used in N-Queens?

Typical implementations use arrays or sets to track occupied columns and diagonals. Optimized versions replace these structures with integer bitmasks, allowing constant-time checks using bit operations and reducing memory overhead.

What is the time complexity of N-Queens?

The typical N-Queens backtracking solution runs in approximately O(N!) time because each row can branch into multiple column choices while pruning invalid placements. Space complexity is O(N) for recursion depth and tracking columns and diagonals, or O(N²) if the board is stored explicitly.

N-Queens Python or Java solution approach?

Python and Java solutions usually implement recursive backtracking. Track used columns, major diagonals (row - col), and minor diagonals (row + col) using sets or boolean arrays, then recursively place queens row by row until a full board configuration is built.

Is N-Queens asked at Google, Amazon, or Meta?

N-Queens is a classic backtracking problem commonly used in interviews at companies like Amazon, Google, and Meta to evaluate recursion, pruning strategies, and constraint satisfaction reasoning. Variants may appear that focus on counting solutions or validating queen placements.

N-Queens solution and explanation

The problem

Approach overview

Approach 1: Backtracking with Row-wise Construction

Approach 2: Bit Manipulation Optimization

Approach 3: DFS (Backtracking)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

N-Queens solution and explanation

The problem

Approach overview

Approach 1: Backtracking with Row-wise Construction

Approach 2: Bit Manipulation Optimization

Approach 3: DFS (Backtracking)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems