N-Queens II (Count Solutions)

▶

Steps

setup

Start Backtracking at Row 0

The algorithm begins at row 0 with empty columns and diagonals (all zero). It prepares to find all valid queen placements starting from the first row.

💡 Initializing bitmasks to zero means no columns or diagonals are under attack, so all positions are initially available.

Line:

def backtrack(row, cols, pos_diags, neg_diags):
    if row == n:
        return 1
    count = 0

💡 The recursion starts with no constraints, ready to explore all columns in the first row.

fill_cells

Calculate Available Positions at Row 0

Compute available positions by masking out columns and diagonals under attack. Since all are zero, all columns are available (bitmask 1111).

💡 Bitmasking quickly identifies safe columns without checking each cell individually.

Line:

available_positions = ((1 << n) - 1) & ~(cols | pos_diags | neg_diags)

💡 All four columns are free to place a queen in row 0.

insert

Place Queen at Row 0, Column 0

Select the rightmost available position (column 0) and place a queen there, updating bitmasks to mark attacked columns and diagonals.

💡 Placing a queen updates constraints for the next row to avoid attacks.

Line:

position = available_positions & -available_positions
available_positions &= available_positions - 1
count += backtrack(row + 1, cols | position, (pos_diags | position) << 1, (neg_diags | position) >> 1)

💡 Bitmasks now reflect that column 0 and diagonals from this queen are under attack.

fill_cells

Calculate Available Positions at Row 1

Calculate available positions for row 1 by masking out attacked columns and diagonals from previous queen placements.

💡 Bitmask operations efficiently identify safe columns for the current row.

Line:

available_positions = ((1 << n) - 1) & ~(cols | pos_diags | neg_diags)

💡 Only columns 2 and 3 are available for placing a queen at row 1.

insert

Place Queen at Row 1, Column 2

Choose the rightmost available position (column 2) at row 1 and place a queen, updating bitmasks accordingly.

💡 Each queen placement further restricts available positions in subsequent rows.

Line:

position = available_positions & -available_positions
available_positions &= available_positions - 1
count += backtrack(row + 1, cols | position, (pos_diags | position) << 1, (neg_diags | position) >> 1)

💡 Bitmasks now reflect attacks from queens at (0,0) and (1,2).

fill_cells

Calculate Available Positions at Row 2

Calculate available positions for row 2 by masking out attacked columns and diagonals from previous queens.

💡 Bitmasking quickly identifies safe columns for the current row.

Line:

available_positions = ((1 << n) - 1) & ~(cols | pos_diags | neg_diags)

💡 Only column 1 is available for placing a queen at row 2.

insert

Place Queen at Row 2, Column 1

Place queen at the only available position (column 1) in row 2, updating bitmasks for next row.

💡 This placement further restricts the next row's available positions.

Line:

position = available_positions & -available_positions
available_positions &= available_positions - 1
count += backtrack(row + 1, cols | position, (pos_diags | position) << 1, (neg_diags | position) >> 1)

💡 Bitmasks now reflect attacks from queens at (0,0), (1,2), and (2,1).

fill_cells

Calculate Available Positions at Row 3

Calculate available positions for row 3 by masking out attacked columns and diagonals.

💡 Bitmasking identifies column 3 as the only safe position at row 3.

Line:

available_positions = ((1 << n) - 1) & ~(cols | pos_diags | neg_diags)

💡 Only column 3 is available for queen placement at row 3.

insert

Place Queen at Row 3, Column 3 and Complete Solution

Place queen at column 3 in row 3, reaching the base case where all rows have queens placed, so count one solution.

💡 Reaching row == n means a valid solution is found and counted.

Line:

if row == n:
    return 1

💡 This leaf node contributes one to the total solution count.

backtrack

Backtrack to Row 3 and Try Next Position

Backtrack from row 4 to row 3 to try other available positions. No other positions remain at row 3, so backtrack further.

💡 Backtracking restores previous state to explore alternative branches.

Line:

available_positions &= available_positions - 1

💡 Backtracking is essential to explore all possible solutions.

backtrack

Backtrack to Row 2 and Try Next Position

Backtrack to row 2 to try other available positions. No other positions remain at row 2, so backtrack further.

💡 Backtracking continues until all options at a level are exhausted.

Line:

available_positions &= available_positions - 1

💡 Backtracking systematically explores all branches of the recursion tree.

insert

Place Queen at Row 1, Column 3

Try the next available position at row 1, column 3, and recurse to row 2 with updated bitmasks.

💡 Trying alternative queen placements explores different solution branches.

Line:

position = available_positions & -available_positions
available_positions &= available_positions - 1
count += backtrack(row + 1, cols | position, (pos_diags | position) << 1, (neg_diags | position) >> 1)

💡 The recursion explores a new branch with queen at (1,3).

fill_cells

Calculate Available Positions at Row 2

Calculate available positions for row 2 with updated bitmasks after placing queen at (1,3).

💡 Bitmasking identifies safe columns quickly for the current row.

Line:

available_positions = ((1 << n) - 1) & ~(cols | pos_diags | neg_diags)

💡 Columns 0 and 1 are available at row 2.

insert

Place Queen at Row 2, Column 1

Place queen at column 1 in row 2 and recurse to row 3 with updated bitmasks.

💡 Each placement updates constraints for the next row.

Line:

position = available_positions & -available_positions
available_positions &= available_positions - 1
count += backtrack(row + 1, cols | position, (pos_diags | position) << 1, (neg_diags | position) >> 1)

💡 The recursion explores this branch with queens at (0,0), (1,3), (2,1).

fill_cells

Calculate Available Positions at Row 3

Calculate available positions for row 3 after placing queens at previous rows.

💡 Bitmasking identifies column 3 as the only safe position.

Line:

available_positions = ((1 << n) - 1) & ~(cols | pos_diags | neg_diags)

💡 Only column 3 is available at row 3.

insert

Place Queen at Row 3, Column 3 and Complete Second Solution

Place queen at column 3 in row 3, reaching the base case and counting the second valid solution.

💡 Completing all rows means a valid solution is found and counted.

Line:

if row == n:
    return 1

💡 This leaf node adds one more to the total solution count.

backtrack

Backtrack to Row 1 and Try Next Position

Backtrack to row 1 after exhausting all options at row 3, then try next available position at row 1 (column 1).

💡 Backtracking explores all possible queen placements at each row.

Line:

available_positions &= available_positions - 1

💡 The recursion explores a new branch starting with queen at (1,1).

backtrack

No More Positions at Row 1, Backtrack to Row 0

After trying all positions at row 1, no more options remain, so backtrack to row 0 to try next queen placement.

💡 Backtracking continues until all branches are explored.

Line:

available_positions &= available_positions - 1

💡 Backtracking ensures exhaustive search of all valid configurations.

insert

Place Queen at Row 0, Column 1

Try placing queen at column 1 in row 0 and recurse to row 1 with updated bitmasks.

💡 Trying different first-row placements explores new solution branches.

Line:

position = available_positions & -available_positions
available_positions &= available_positions - 1
count += backtrack(row + 1, cols | position, (pos_diags | position) << 1, (neg_diags | position) >> 1)

💡 The recursion explores new branches starting with queen at (0,1).

reconstruct

End of Search, Return Total Solutions

All recursive calls complete, returning the total count of 2 valid solutions for the 4-queens problem.

💡 The final count aggregates all valid leaf nodes found during recursion.

Line:

return backtrack(0, 0, 0, 0)

💡 The algorithm efficiently counted all solutions without enumerating invalid boards.

class Solution:
    def totalNQueens(self, n: int) -> int:
        def backtrack(row, cols, pos_diags, neg_diags):
            # STEP 1: Check if all rows are placed
            if row == n:
                return 1
            count = 0
            # STEP 2: Calculate available positions
            available_positions = ((1 << n) - 1) & ~(cols | pos_diags | neg_diags)
            while available_positions:
                # STEP 3: Extract rightmost available position
                position = available_positions & -available_positions
                # STEP 4: Remove chosen position
                available_positions &= available_positions - 1
                # STEP 5: Recurse with updated bitmasks
                count += backtrack(row + 1,
                                   cols | position,
                                   (pos_diags | position) << 1,
                                   (neg_diags | position) >> 1)
            return count

        return backtrack(0, 0, 0, 0)

📊

N-Queens II (Count Solutions) - Watch the Algorithm Execute, Step by Step

Watching the algorithm step through each recursive call and bitmask update reveals how pruning and bit operations efficiently solve the problem without brute force.

enteringrow=0cols=0pos_diags=0neg_diags=0

Call Path (current → root)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Remaining

col0col1col2col3

choosingrow=0cols=0pos_diags=0neg_diags=0

Call Path (current → root)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Remaining

col0col1col2col3

enteringrow=1cols=1pos_diags=2neg_diags=0

Call Path (current → root)

backtrack(row=1, cols=1, pos_diags=2, neg_diags=0)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Remaining

col1col2col3

Partial: [col0]

choosingrow=1cols=1pos_diags=2neg_diags=0

Call Path (current → root)

backtrack(row=1, cols=1, pos_diags=2, neg_diags=0)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Remaining

col2col3

Partial: [col0]

enteringrow=2cols=5pos_diags=8neg_diags=1

Call Path (current → root)

backtrack(row=2, cols=5, pos_diags=8, neg_diags=1)

backtrack(row=1, cols=1, pos_diags=2, neg_diags=0)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Remaining

col1

Partial: [col0, col2]

choosingrow=2cols=5pos_diags=8neg_diags=1

Call Path (current → root)

backtrack(row=2, cols=5, pos_diags=8, neg_diags=1)

backtrack(row=1, cols=1, pos_diags=2, neg_diags=0)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Remaining

col1

Partial: [col0, col2]

enteringrow=3cols=7pos_diags=18neg_diags=0

Call Path (current → root)

backtrack(row=3, cols=7, pos_diags=18, neg_diags=0)

backtrack(row=2, cols=5, pos_diags=8, neg_diags=1)

backtrack(row=1, cols=1, pos_diags=2, neg_diags=0)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Remaining

col3

Partial: [col0, col2, col1]

choosingrow=3cols=7pos_diags=18neg_diags=0

Call Path (current → root)

backtrack(row=3, cols=7, pos_diags=18, neg_diags=0)

backtrack(row=2, cols=5, pos_diags=8, neg_diags=1)

backtrack(row=1, cols=1, pos_diags=2, neg_diags=0)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Remaining

col3

Partial: [col0, col2, col1]

backtrackingrow=4cols=15pos_diags=36neg_diags=1

Call Path (current → root)

backtrack(row=4, cols=15, pos_diags=36, neg_diags=1)

backtrack(row=3, cols=7, pos_diags=18, neg_diags=0)

backtrack(row=2, cols=5, pos_diags=8, neg_diags=1)

backtrack(row=1, cols=1, pos_diags=2, neg_diags=0)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Partial: [col0, col2, col1, col3]

Found 1: [solution1]

backtrackingrow=3cols=7pos_diags=18neg_diags=0

Call Path (current → root)

backtrack(row=3, cols=7, pos_diags=18, neg_diags=0)

backtrack(row=2, cols=5, pos_diags=8, neg_diags=1)

backtrack(row=1, cols=1, pos_diags=2, neg_diags=0)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Tried

col3

Partial: [col0, col2, col1]

Found 1: [solution1]

backtrackingrow=2cols=5pos_diags=8neg_diags=1

Call Path (current → root)

backtrack(row=2, cols=5, pos_diags=8, neg_diags=1)

backtrack(row=1, cols=1, pos_diags=2, neg_diags=0)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Tried

col1

Partial: [col0, col2]

Found 1: [solution1]

enteringrow=2cols=9pos_diags=4neg_diags=2

Call Path (current → root)

backtrack(row=1, cols=9, pos_diags=4, neg_diags=2)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Remaining

col0col1

Partial: [col0, col3]

Found 1: [solution1]

choosingrow=2cols=9pos_diags=4neg_diags=2

Call Path (current → root)

backtrack(row=1, cols=9, pos_diags=4, neg_diags=2)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Remaining

col0col1

Partial: [col0, col3]

Found 1: [solution1]

enteringrow=3cols=11pos_diags=10neg_diags=1

Call Path (current → root)

backtrack(row=2, cols=11, pos_diags=10, neg_diags=1)

backtrack(row=1, cols=9, pos_diags=4, neg_diags=2)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Remaining

col3

Partial: [col0, col3, col1]

Found 1: [solution1]

choosingrow=3cols=11pos_diags=10neg_diags=1

Call Path (current → root)

backtrack(row=2, cols=11, pos_diags=10, neg_diags=1)

backtrack(row=1, cols=9, pos_diags=4, neg_diags=2)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Remaining

col3

Partial: [col0, col3, col1]

Found 1: [solution1]

backtrackingrow=4cols=15pos_diags=20neg_diags=2

Call Path (current → root)

backtrack(row=4, cols=15, pos_diags=20, neg_diags=2)

backtrack(row=3, cols=15, pos_diags=20, neg_diags=2)

backtrack(row=2, cols=11, pos_diags=10, neg_diags=1)

backtrack(row=1, cols=9, pos_diags=4, neg_diags=2)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Partial: [col0, col3, col1, col3]

Found 2: [solution1] [solution2]

backtrackingrow=1cols=0pos_diags=0neg_diags=0

Call Path (current → root)

backtrack(row=1, cols=0, pos_diags=0, neg_diags=0)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Tried

col0col3

Remaining

col1col2

Partial: [col0]

Found 2: [solution1] [solution2]

backtrackingrow=0cols=0pos_diags=0neg_diags=0

Call Path (current → root)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Tried

col0

Remaining

col1col2col3

Found 2: [solution1] [solution2]

enteringrow=1cols=2pos_diags=4neg_diags=1

Call Path (current → root)

backtrack(row=1, cols=2, pos_diags=4, neg_diags=1)

backtrack(row=0, cols=0, pos_diags=0, neg_diags=0)

Remaining

col0col3

Partial: [col1]

Found 2: [solution1] [solution2]

Answer: 2

Total calls: 15 · Pruned: 0

Key Takeaways

✓ Bitmasking efficiently encodes and updates constraints for columns and diagonals, enabling fast pruning.

This insight is hard to see from code alone because bit operations are compact and abstract, but visualization shows how constraints evolve.

✓ The recursion tree structure clearly shows how the algorithm explores each row's queen placements and backtracks when no options remain.

Seeing the tree helps understand the exhaustive search and pruning, which is less obvious from reading code.

✓ Each leaf node corresponds to a complete valid solution, and the algorithm counts these leaves to find the total number of solutions.

Understanding that counting solutions is about counting leaf nodes clarifies the base case and return values.

Practice

1. Consider the following code snippet for counting beautiful arrangements. What is the final output when n = 2?

easy

A. 1

B. 3

C. 2

D. 4

Solution

1. Step 1: Trace backtrack calls for n=2

   Positions: 1 and 2. At pos=1, try nums 1 and 2. Both satisfy divisibility. For pos=2, remaining number also satisfies divisibility.

2. Step 2: Count valid permutations

   Permutations: [1,2] and [2,1] both valid, total count = 2.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both permutations satisfy conditions, so output is 2 [OK]

Hint: Check all permutations for small n manually [OK]

Common Mistakes:

• Off-by-one in position indexing
• Counting invalid permutations

2. Given the following Python code for generating parentheses, what is the content of result after calling generateParenthesis(2)?

easy

A. ['((', '))']

B. ['()()', '(())']

C. ['(())', '()()']

D. ['()()', '(()']

Solution

1. Step 1: Trace backtrack calls for n=2

   Sequences generated are '(())' and '()()' in that order due to DFS with backtracking.

2. Step 2: Confirm order and validity

   Both sequences are valid balanced parentheses of length 4, matching expected output.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches known valid sequences for n=2 [OK]

Hint: Backtracking generates sequences in DFS order [OK]

Common Mistakes:

• Confusing order of sequences
• Including invalid partial sequences

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. The following code attempts to generate all permutations of a list using Heap's algorithm but contains a subtle bug:

def permute(nums):
    res = [nums[:]]
    c = [0] * len(nums)
    i = 0
    while i < len(nums):
        if c[i] < i:
            if i % 2 == 0:
                nums[0], nums[i] = nums[i], nums[0]
            else:
                nums[c[i]], nums[i] = nums[i], nums[c[i]]
            res.append(nums)
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return res

What is the bug in this code?

medium

A. The used array c is not reset properly, causing infinite loop

B. Appending nums directly without copying causes all entries in res to reference the same list

C. Swapping nums[0] and nums[i] when i is even is incorrect logic

D. The initial res list should be empty, not contain nums[:] at start

Solution

1. Step 1: Identify how results are stored

   The code appends nums directly to res without copying.

2. Step 2: Understand consequences of appending references

   Since nums is mutated in-place, all entries in res point to the same list, resulting in duplicates of the final permutation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Appending a copy nums[:] fixes the bug [OK]

Hint: Always append a copy of mutable lists to results [OK]

Common Mistakes:

• Forgetting to copy before appending results in duplicate references

5. 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