N-Queens II: Counting Valid Placements

The N-Queens problem is a classic combinatorial puzzle. Given a chessboard of size N x N, the challenge is to determine the number of distinct ways to place N queens such that no two queens threaten each other. This means no two queens can share the same row, column, or diagonal. This variation focuses on counting these valid configurations rather than listing them.

Problem Description

You are tasked with writing a function that takes an integer n representing the size of an N x N chessboard. Your function should return the total number of distinct configurations where N queens can be placed on this chessboard without any two queens attacking each other.

Key Requirements:

• A queen attacks any piece in the same row, same column, or on the same diagonal.
• All N queens must be placed on the board.
• You need to count the number of valid solutions, not list the actual placements.

Expected Behavior:

• The function should accept a positive integer n.
• The function should return a non-negative integer representing the count of valid N-Queens placements.

Edge Cases:

• n = 1: A single queen on a 1x1 board is a valid placement.
• n = 2 or n = 3: No valid placements are possible.

Examples

Example 1:

Input: 4
Output: 2
Explanation:
There are two distinct solutions for placing 4 queens on a 4x4 board:

Solution 1:
. Q . .
. . . Q
Q . . .
. . Q .

Solution 2:
. . Q .
Q . . .
. . . Q
. Q . .

In both cases, no two queens share the same row, column, or diagonal.

Example 2:

Input: 1
Output: 1
Explanation:
A single queen on a 1x1 board is the only possible configuration and it's valid.

Example 3:

Input: 3
Output: 0
Explanation:
It's impossible to place 3 queens on a 3x3 board without them attacking each other.

Constraints

• 1 <= n <= 9
• n will always be an integer.
• The expected performance is to complete the calculation within a reasonable time for the given constraints, suggesting an efficient algorithmic approach.

Notes

This problem is a classic example that can be solved using recursion and backtracking. Consider how you can systematically explore possible queen placements and efficiently prune branches of the search tree that are guaranteed not to lead to a valid solution. You'll need a way to keep track of which columns and diagonals are already occupied by queens.