N-Queens II
Hard · Backtracking · Backtracking · Bit Manipulation
Problem
The n-queens puzzle asks you to place n chess queens on an n × n board so that no two queens attack each other: no two share a row, a column or a diagonal.
Given n, return the number of distinct placements. You only need the count, not the boards.
Examples
Input: n = 5 Output: 10
There are ten placements on a 5 × 5 board.
Input: n = 6 Output: 4
The 6 × 6 board has only four placements, fewer than the 5 × 5 board.
Input: n = 3 Output: 0
Three queens cannot be placed safely on a 3 × 3 board.
Constraints
- 1 <= n <= 9
Approaches
- Baseline: every column arrangement, then check diagonals — time O(n! · n²), space O(n)
Follow-up
The board is symmetric: count only placements whose first-row queen is in the left half, double the result, and handle the middle column of an odd board separately. That halves the work. The use cases fix one queen in advance, or block squares, and count what remains.
Related problems
Start free on Cariara · Coding problems · System design studio
