N-Queens II (Count Solutions)
Imagine placing queens on a chessboard so that none can attack each other, and you want to know how many ways this can be done without listing them all.
Given an integer n, return the number of distinct solutions to the n-queens puzzle. The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
1 ≤ n ≤ 14The output fits in a 32-bit integerdef totalNQueens(n: int) -> int:public int totalNQueens(int n)int totalNQueens(int n)function totalNQueens(n)def totalNQueens(n: int) -> int:
# Write your solution here
passclass Solution {
public int totalNQueens(int n) {
// Write your solution here
return 0;
}
}#include <vector>
using namespace std;
int totalNQueens(int n) {
// Write your solution here
return 0;
}function totalNQueens(n) {
// Write your solution here
}0Returning zero for all inputs due to missing base case or incorrect recursion termination.✅ Add base case: if row == n, return 1 to count a valid solution.Incorrect positive count for n=2 or n=3Conflict checks missing or incorrect, allowing invalid queen placements.✅ Check columns and both diagonals for conflicts before placing a queen.Less than correct count for n=6 or n=7Greedy or partial backtracking skipping valid solutions.✅ Implement full backtracking exploring all columns per row without early pruning except conflicts.Timeout on n=14Naive recursion with board validation causing exponential blowup.✅ Use bitmask optimization to track columns and diagonals efficiently and prune early.42There are two distinct ways to place 4 queens on a 4x4 board so that none attack each other.
510There are 10 distinct ways to place 5 queens on a 5x5 board with no conflicts.
11Only one queen on 1x1 board, trivially one solution.
20No valid placements for 2 queens on 2x2 board without conflicts.
30No valid placements for 3 queens on 3x3 board without conflicts.
64There are 4 distinct solutions for 6-queens problem.
740There are 40 distinct solutions for 7-queens problem.
892There are 92 distinct solutions for 8-queens problem.
14nulln=14, backtracking with pruning or bitmask optimization must complete within 2 seconds.
