Start by placing queens row by row, using backtracking to abandon invalid configurations early. Track columns, diagonals, and anti-diagonals to prune paths quickly. The method ensures all valid board arrangements are generated without redundant checks, making it efficient for n up to 9.
Problem Statement
The N-Queens problem requires placing n queens on an n x n chessboard such that no two queens threaten each other. Each queen occupies a unique row, column, and diagonal.
Given an integer n, return all distinct board configurations representing valid N-Queens placements. Each configuration uses 'Q' for a queen and '.' for empty spaces, in any order.
Examples
Example 1
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2
Input: n = 1
Output: [["Q"]]
Example details omitted.
Constraints
- 1 <= n <= 9
Solution Approach
Backtracking with Row-by-Row Placement
Place queens row by row and recursively attempt placements in valid columns. If a conflict is detected, backtrack immediately to prune the search space.
Track Column and Diagonal Conflicts
Maintain sets for columns, diagonals, and anti-diagonals to detect conflicts in O(1). This ensures invalid placements are skipped quickly, preventing wasted recursion.
Construct and Collect Board Configurations
Once a valid placement reaches the last row, convert the positions into a board of strings and append to results. Repeat until all possibilities are explored.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity grows exponentially with n due to backtracking, approximately O(n!), but pruning reduces unnecessary recursive calls. Space complexity is O(n) for tracking columns and diagonals plus O(n) per board for storing solutions.
What Interviewers Usually Probe
- Check if the candidate prunes branches early using column and diagonal tracking.
- Look for clean recursion and backtracking structure without redundant iterations.
- Confirm candidate can generate all distinct board arrangements correctly.
Common Pitfalls or Variants
Common pitfalls
- Not handling diagonal conflicts correctly, leading to invalid placements.
- Modifying the board in place without restoring state during backtracking.
- Failing to return results in the required board string format with 'Q' and '.'.
Follow-up variants
- Return only the count of N-Queens solutions instead of full board configurations.
- Solve for N-Queens II with restricted pre-placed queens in some rows.
- Adapt the solution to k-Queens on an m x n board with k <= min(m,n).
How GhostInterview Helps
- Automatically applies backtracking with pruning patterns to generate valid solutions quickly.
- Highlights row, column, and diagonal tracking strategies to avoid common interview mistakes.
- Provides step-by-step board construction to verify every placement efficiently during problem solving.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the N-Queens problem pattern used in GhostInterview?
It is a backtracking search with pruning, placing queens row by row while tracking columns and diagonals to skip invalid paths.
How does GhostInterview handle large n values?
It efficiently prunes invalid paths using column and diagonal sets, but practical performance is best for n up to 9 due to exponential growth.
Can the solution return the board in any order?
Yes, GhostInterview generates all valid configurations, and the order of solutions does not affect correctness.
Why is backtracking necessary for N-Queens?
Backtracking systematically explores possibilities while pruning invalid paths, avoiding redundant or conflicting queen placements.
What common mistakes should I avoid when coding N-Queens?
Avoid missing diagonal checks, failing to restore board state during recursion, and returning incorrectly formatted board strings.
Need direct help with N-Queens instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture N-Queens from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Generate all unique permutations of an array containing duplicates using backtracking and pruning to avoid repeated sequences efficiently.
Open problem page#46 PermutationsGenerate all possible orderings of a distinct integer array using backtracking search with careful pruning to avoid duplicates.
Open problem page#40 Combination Sum IIFind all unique combinations of numbers that sum to a target using backtracking with careful pruning to avoid duplicates.
Open problem page