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 <= 9Problem Overview: Place n queens on an n x n chessboard so that no two queens attack each other. Queens attack along rows, columns, and diagonals. The task is to return every valid board configuration.
The key constraint: each row must contain exactly one queen, and no two queens can share the same column or diagonal. That naturally leads to exploring placements row by row while rejecting invalid states early.
Approach 1: Backtracking with Row-wise Construction (Time: ~O(N!), Space: O(N))
This is the classic solution used in most interviews. Build the board one row at a time and try placing a queen in every column of the current row. Before placing, check whether the column or either diagonal already contains a queen. Efficient implementations track conflicts using three structures: a columns set, a diag1 set for row - col, and a diag2 set for row + col. If a position is safe, place the queen, recurse to the next row, and backtrack afterward. The search space is roughly factorial because each row branches across remaining valid columns, but pruning invalid placements early keeps it manageable.
Backtracking works well because the constraints are local and easy to validate in O(1). You only store the column index for each row and generate the board representation when a valid solution is found. This approach directly demonstrates recursive state exploration, a core technique in backtracking problems.
Approach 2: Bit Manipulation Optimization (Time: ~O(N!), Space: O(N))
This version replaces sets or arrays with bit masks to track used columns and diagonals. Three integers represent occupied positions: cols, diag1, and diag2. For each row, compute available positions using bit operations like ~(cols | diag1 | diag2). Extract the lowest available bit with pos & -pos, place a queen there, and recurse with updated masks. Diagonal masks shift left or right when moving to the next row.
Bit operations make conflict checks extremely fast and reduce memory overhead. This approach is common in competitive programming and scales better for larger n. It also demonstrates how arrays and bitsets can represent board states compactly. Many optimized solutions for constraint problems use similar masking techniques, which are often categorized under backtracking with pruning.
Recommended for interviews: Start with row-wise backtracking. Interviewers expect this solution because it clearly shows constraint checking, recursion, and pruning. Once that works, mention the bitmask optimization to demonstrate deeper understanding of performance improvements. The optimized version doesn't change the asymptotic complexity (~O(N!)) but significantly reduces constant factors.
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.
C++
Java
Python
C#
JavaScript
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.
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.
Java
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.
| Approach | Complexity |
|---|---|
| Backtracking with Row-wise Construction | Time Complexity: O(N!), because we are trying N possible positions for each row for N queens. |
| Bit Manipulation Optimization | Time Complexity: O(N!), each row considers N placements, simplified by binary check. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Row-wise Construction | O(N!) | O(N) | Standard interview solution. Clear logic and easy to implement. |
| Bit Manipulation Optimization | O(N!) | O(N) | When performance matters or demonstrating advanced optimization techniques. |
6.1 N Queens Problem using Backtracking • Abdul Bari • 2,318,339 views views
Watch 9 more video solutions →Practice N-Queens with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor