Peaceful Queen Placements
HardBacktracking
Problem
On an n × n chessboard, place n queens so that no two queens attack each other (no two share a row, a column or a diagonal).
Return the number of distinct placements.
Example 1
- Input:
- n = 4
- Output:
- 2
The two placements, row by row, are ".Q.. / ...Q / Q... / ..Q." and its mirror image.
Example 2
- Input:
- n = 1
- Output:
- 1
Constraints
- 1 ≤ n ≤ 10
Hint
Show the first hint
Each row must contain exactly one queen. So decide, row by row, which column it goes in.
Walkthrough
How to approach it
01Clarify before coding
- Are mirror images and rotations counted separately? Yes, every placement counts.
- Return the boards or the count? The count.
- n = 2 or 3? There are no solutions: return 0.
02Brute force
Choose n of the n² squares and check whether any two queens attack.
Cost: C(n², n) placements: C(64, 8) ≈ 4.4 billion for n = 8.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.