N-Queens II (Count Solutions)

📋

Problem

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 integer

Edge cases: n = 1 → 1 solutionn = 2 → 0 solutions (no valid placements)n = 3 → 0 solutions (no valid placements)

</>

IDE

def 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
    pass

class 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
}

Common Bugs to Avoid

Wrong: 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.

Wrong: 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.

Wrong: 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.

Wrong: Timeout on n=14Naive recursion with board validation causing exponential blowup.✅ Use bitmask optimization to track columns and diagonals efficiently and prune early.

✓

Test Cases

Focus on handling smallest boards and no-solution cases correctly.

Watch out for common algorithmic traps like greedy placement and off-by-one errors.

Optimize your solution with bitmasking and pruning to handle large n efficiently.

t1_01basic

Input4

Expected2

⏱ Performance - must finish in 2000ms

There are two distinct ways to place 4 queens on a 4x4 board so that none attack each other.

💡 Try placing queens row by row and check conflicts.

💡 Use backtracking to explore all valid placements.

💡 Count solutions when all rows are successfully assigned.

Why it failed: Incorrect count for n=4 indicates backtracking or conflict check is flawed. Fix by ensuring diagonal and column conflicts are correctly detected.

✓ Correctly counts all valid 4-queen placements.

t1_02basic

Input5

Expected10

⏱ Performance - must finish in 2000ms

There are 10 distinct ways to place 5 queens on a 5x5 board with no conflicts.

💡 Backtracking explores all column choices per row.

💡 Check columns and diagonals for conflicts before placing.

💡 Count solutions only when all rows are assigned.

Why it failed: Incorrect count for n=5 means conflict detection or recursion termination is wrong. Fix by verifying all conflict checks and base case return.

✓ Correctly counts all valid 5-queen placements.

t2_01edge

Input1

Expected1

⏱ Performance - must finish in 2000ms

Only one queen on 1x1 board, trivially one solution.

💡 Check base case when n=1.

💡 No conflicts possible with single queen.

💡 Return 1 immediately or after placing queen.

Why it failed: Fails n=1 test if base case not handled or recursion never returns 1. Fix by adding base case for row == n returning 1.

✓ Correctly handles smallest board with one queen.

t2_02edge

Input2

Expected0

⏱ Performance - must finish in 2000ms

No valid placements for 2 queens on 2x2 board without conflicts.

💡 Try all placements and verify no solutions found.

💡 Check that conflict detection prevents invalid placements.

💡 Return 0 if no full assignments possible.

Why it failed: Fails n=2 test if code returns nonzero solutions. Fix by ensuring conflict checks correctly reject all invalid placements.

✓ Correctly returns zero for no solution cases.

t2_03edge

Input3

Expected0

⏱ Performance - must finish in 2000ms

No valid placements for 3 queens on 3x3 board without conflicts.

💡 Try all column placements per row and check conflicts.

💡 No full assignment possible for n=3.

💡 Return 0 if no valid solutions found.

Why it failed: Fails n=3 test if code returns nonzero solutions. Fix by verifying conflict checks and backtracking logic.

✓ Correctly returns zero for no solution cases.

t3_01corner

Input6

Expected4

⏱ Performance - must finish in 2000ms

There are 4 distinct solutions for 6-queens problem.

💡 Avoid greedy placement; try all columns per row.

💡 Check all diagonals and columns for conflicts.

💡 Count solutions only when all rows assigned.

Why it failed: Greedy approach fails here by missing solutions. Fix by implementing full backtracking instead of greedy column choice.

✓ Correctly counts all solutions avoiding greedy traps.

t3_02corner

Input7

Expected40

⏱ Performance - must finish in 2000ms

There are 40 distinct solutions for 7-queens problem.

💡 Ensure no reuse of columns or diagonals across rows.

💡 Use sets or bitmasks to track conflicts efficiently.

💡 Count solutions only when all rows assigned.

Why it failed: Confusing 0/1 vs unbounded placement leads to counting invalid solutions multiple times. Fix by ensuring each row places exactly one queen.

✓ Correctly enforces one queen per row and counts solutions.

t3_03corner

Input8

Expected92

⏱ Performance - must finish in 2000ms

There are 92 distinct solutions for 8-queens problem.

💡 Check off-by-one errors in recursion termination.

💡 Verify conflict checks include both diagonals and columns.

💡 Count solutions only when row == n.

Why it failed: Off-by-one error in recursion causes missing or extra counts. Fix by ensuring base case triggers exactly when row == n.

✓ Correctly counts all solutions with proper recursion base case.

t4_01performance

Input14

Expectednull

⏱ Performance - must finish in 2000ms

n=14, backtracking with pruning or bitmask optimization must complete within 2 seconds.

💡 Use bitmask to track columns and diagonals efficiently.

💡 Prune invalid branches early in recursion.

💡 Avoid naive board validation to meet time constraints.

Why it failed: TLE occurs if brute force or naive conflict checks used. Fix by implementing bitmask-based pruning and efficient backtracking.

✓ Algorithm runs within time limit using bitmask optimization.