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.

Practice

1. You need to generate all possible orderings of a list of unique integers. Which algorithmic approach guarantees that all permutations are generated without duplicates and with optimal time complexity?

easy

A. Backtracking with either a used array or in-place swapping to explore all permutations

B. Sorting the array repeatedly and collecting unique sequences

C. Dynamic programming to build permutations from smaller subproblems

D. Greedy algorithm that picks the next smallest unused element at each step

Solution

1. Step 1: Understand the problem requires all permutations

   Generating all permutations means enumerating every possible ordering of the input elements without duplicates.

2. Step 2: Identify the approach that systematically explores all orderings

   Backtracking with a used array or in-place swapping explores all permutations by recursively building sequences or swapping elements, ensuring no duplicates and covering all possibilities.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking is the standard method for generating all permutations [OK]

Hint: Backtracking systematically explores all permutations [OK]

Common Mistakes:

• Thinking greedy or sorting can generate all permutations without duplicates

2. Given the following iterative backtracking code snippet for restoring IP addresses, what is the final output when the input string is "25525511135"?

from typing import List

def restore_ip_addresses(s: str) -> List[str]:
    res = []
    stack = [(0, [])]  # (start index, path)
    while stack:
        start, path = stack.pop()
        if len(path) == 4:
            if start == len(s):
                res.append(".".join(path))
            continue
        remaining_segments = 4 - len(path)
        remaining_chars = len(s) - start
        if remaining_chars < remaining_segments or remaining_chars > 3 * remaining_segments:
            continue
        for length in range(1, 4):
            if start + length > len(s):
                break
            segment = s[start:start+length]
            if (segment.startswith('0') and len(segment) > 1) or (length == 3 and int(segment) > 255):
                continue
            stack.append((start + length, path + [segment]))
    return res

print(restore_ip_addresses("25525511135"))

easy

A. ["255.255.11.135"]

B. ["255.255.111.35", "255.255.11.135"]

C. ["255.255.11.135", "255.255.111.35"]

D. ["255.255.111.35"]

Solution

1. Step 1: Trace initial stack and first expansions

   Start with (0, []). Segments like '255', '25', '2' are pushed. Valid segments are checked for leading zeros and range.

2. Step 2: Identify valid IP addresses found

   Two valid IPs are found: "255.255.11.135" and "255.255.111.35". Both use all characters and have 4 segments.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both valid IPs appear in the result list [OK]

Hint: Valid IPs must have 4 segments and consume entire string [OK]

Common Mistakes:

• Confusing order of results
• Missing one valid IP due to pruning

3. What is the time complexity of the optimal backtracking solution that generates all valid parentheses sequences for input n?

medium

A. O(2^{2n} * n) because it generates all sequences and checks validity

B. O(n^2) because it builds sequences of length 2n with nested loops

C. O(n!) because it permutes parentheses positions

D. O(\frac{4^n}{n^{3/2}}) because the number of valid sequences is the nth Catalan number

Solution

1. Step 1: Identify number of valid sequences

   The number of valid parentheses sequences is the nth Catalan number, approximately 4^n / (n^{3/2}).

2. Step 2: Analyze backtracking time

   Backtracking generates all valid sequences, so time is proportional to number of sequences times sequence length, which is O(4^n / n^{3/2} * n) = O(4^n / n^{1/2}).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Matches known Catalan number growth for valid parentheses [OK]

Hint: Catalan number growth dominates complexity [OK]

Common Mistakes:

• Confusing brute force with backtracking complexity
• Assuming factorial complexity

4. Consider the following buggy code snippet for restoring IP addresses. Which line contains the subtle bug that causes invalid IP addresses to be included?

def restore_ip_addresses(s: str) -> List[str]:
    res = []
    stack = [(0, [])]
    while stack:
        start, path = stack.pop()
        if len(path) == 4:
            if start == len(s):
                res.append(".".join(path))
            continue
        remaining_segments = 4 - len(path)
        remaining_chars = len(s) - start
        if remaining_chars < remaining_segments or remaining_chars > 3 * remaining_segments:
            continue
        for length in range(1, 4):
            if start + length > len(s):
                break
            segment = s[start:start+length]
            # Bug: Missing check for leading zeros
            if length == 3 and int(segment) > 255:
                continue
            stack.append((start + length, path + [segment]))
    return res

medium

A. Line missing check for segments with leading zeros

B. Line checking if segment length is 3 and value > 255

C. Line pruning based on remaining characters and segments

D. Line appending new segment to stack

Solution

1. Step 1: Identify missing validation

   The code lacks a check to reject segments with leading zeros like '00' or '01', which are invalid.

2. Step 2: Confirm other checks are correct

   Check for segment > 255 and pruning are present and correct; appending to stack is correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing leading zero check allows invalid IP segments [OK]

Hint: Leading zero check is mandatory to avoid invalid IPs [OK]

Common Mistakes:

• Forgetting leading zero validation
• Misplacing pruning conditions

5. Suppose the Expression Add Operators problem is modified so that digits can be reused any number of times to form expressions (i.e., unlimited reuse of digits in order). Which of the following algorithmic changes correctly adapts the backtracking solution to handle this variant without infinite loops or incorrect results?

hard

A. Remove the index increment in recursive calls to allow reuse, but add a visited set to avoid infinite loops

B. Keep the index increment as is, but allow substring splits to wrap around to the start of the string

C. Modify backtracking to not increment index after choosing a digit, but limit recursion depth to n to prevent infinite loops

D. Allow index to reset to zero after reaching the end, but prune expressions longer than a fixed length to avoid infinite recursion

Solution

1. Step 1: Understand digit reuse impact

   Allowing reuse means the index does not always increment; digits can be chosen repeatedly, risking infinite recursion.

2. Step 2: Prevent infinite loops

   Not incrementing index requires limiting recursion depth (e.g., max length n) to avoid infinite loops while exploring repeated digits.

3. Step 3: Evaluate options

   Modify backtracking to not increment index after choosing a digit, but limit recursion depth to n to prevent infinite loops correctly limits recursion depth while allowing reuse; others either cause infinite loops or incorrect pruning.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Limiting recursion depth prevents infinite loops with reuse [OK]

Hint: Limit recursion depth when digits can be reused [OK]

Common Mistakes:

• Forgetting to limit recursion depth causes infinite loops