N-Queens II
The key idea
Place exactly one queen per row and recurse row by row. A column is safe only if no earlier queen shares its column or either diagonal. Track used columns and the two diagonal families (row - col and row + col) in sets so each safety check is O(1); count a solution whenever a queen has been placed in every row.
Problem
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 *the number of distinct solutions* to the n-queens puzzle.
Two queens attack each other if they share the same row, the same column, or the same diagonal.
Constraints
- 1 <= n <= 9
Examples
Input: n = 4
Output: 2
Input: n = 1
Output: 1
Input: n = 2
Output: 0
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-QueensHARD
- Non-decreasing SubsequencesMEDIUM
- Palindrome PartitioningMEDIUM
- Partition to K Equal Sum SubsetsMEDIUM
- PermutationsMEDIUM