N-Queens
The key idea
Place exactly one queen per row and search row by row. Track which columns and which two diagonals are already attacked so a candidate square is validated in
O(1); backtrack the moment a row has no safe column.Problem
The n-queens puzzle is the problem of placing n queens on an n x n chessboard so 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 '.' indicate a queen and an empty space, respectively.
Constraints
1 <= n <= 9
Examples
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Input: n = 1
Output: [["Q"]]
Complexity
Time: O(n!) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Backtracking problems
- Combination SumMEDIUM
- Combination Sum IIMEDIUM
- Combination Sum IIIMEDIUM
- CombinationsMEDIUM
- Generate ParenthesesMEDIUM
- Letter Combinations of a Phone NumberMEDIUM
- Matchsticks to SquareMEDIUM
- N-Queens IIHARD
- Non-decreasing SubsequencesMEDIUM
- Palindrome PartitioningMEDIUM
- Partition to K Equal Sum SubsetsMEDIUM
- PermutationsMEDIUM