N-Queens Count

Count the number of distinct solutions to place n queens on an n×n board.

backtracking recursion n-queens counting

Write a function `n_queens_count(n)` that returns the number of distinct solutions to the classic N-Queens puzzle: place `n` queens on an `n` x `n` chessboard such that no two queens attack each other (i.e., no two queens share the same row, column, or diagonal). For `n = 0`, return `1` (the empty board has exactly one solution). The function must be deterministic and handle all integers from `0` up to `15`. For `n >= 16`, the result is not required, but you may still compute it if desired (will not be tested). The function signature is exactly `def n_queens_count(n: int) -> int:`.

Implement the function so that it counts the number of distinct arrangements, where two arrangements are distinct if their sets of queen positions differ.

Constraints

Input: integer n, 0 ≤ n ≤ 15.
Time: The function must return within a few seconds for n ≤ 15. Standard backtracking is acceptable. Optimized approaches (bitmask) are allowed.
Output: integer count.

Example

>>> n_queens_count(1)
1
>>> n_queens_count(2)
0
>>> n_queens_count(4)
2
>>> n_queens_count(8)
92

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use backtracking row by row, tracking used columns and both diagonal directions.

Represent diagonals with row+col and row-col (or with bitmasks for speed).

For n=0, treat as one empty board solution.

You can use an iterative or recursive approach; recursion is simplest.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.