N-Queens
Hard · Backtracking · Array · Backtracking
Problem
Place n queens on an n × n chessboard so that no two queens attack each other: no two share a row, a column, or a diagonal.
Return every distinct placement. Each placement is a list of n strings, one per row from top to bottom, where 'Q' marks a queen and '.' an empty square. The placements may be returned in any order.
Some sizes have no placement at all: return an empty list for them.
Examples
Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
A 4 × 4 board has exactly two placements, and each is the mirror image of the other.
Input: n = 1 Output: [["Q"]]
One queen on one square attacks nothing.
Input: n = 3 Output: []
The middle square attacks everything else, and a queen in a corner leaves too few safe squares for the other two.
Constraints
- 1 <= n <= 9
Approaches
- Backtracking with a scan of the placed queens — time O(n! · n), space O(n)
Follow-up
Only the number of placements is needed in N-Queens II (LeetCode 52). Can you count them without building any boards, using three bitmasks instead of sets?
Related problems
Start free on Cariara · Coding problems · System design studio
