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. 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.
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.
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.
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.
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.
| 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. |
| DFS (Backtracking) | — |
| 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. |
L14. N-Queens | Leetcode Hard | Backtracking • take U forward • 635,206 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