Skip to main content
Talentd

N-Queens - Solution & Explanation

HardArrayBacktracking22 min readAsked at: Amazon, Microsoft, Goldman Sachs +13
Practice this problem

Problem Statement

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.

This C solution uses a backtracking approach to place queens row by row, ensuring each placement is valid by checking current column and diagonal conflicts. The recursive function solve advances to next row if a queen is placed, or backtracks if a conflict arises. Valid solutions are stored in a dynamically resized list of boards.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N!), because we are trying N possible positions for each row for N queens.
Space Complexity: O(N^2), due to the storage of the board states and recursion stack.

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.

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.

Code

PythonJava

Python

Java

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.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking with Row-wise Construction

Time Complexity: O(N!), because we are trying N possible positions for each row for N queens.
Space Complexity: O(N^2), due to the storage of the board states and recursion stack.

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)—

Detailed Complexity Analysis

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

Video Solution

N-Queens - Backtracking - Leetcode 51 - Python • NeetCode • 269,310 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice N-Queens with our built-in code editor and test cases.

Practice on FleetCode
Previous

Grid Illumination

Next

N-Queens II