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. You need to generate all combinations of balanced parentheses pairs for a given number n. Which algorithmic approach guarantees generating only valid sequences without generating invalid ones first?

easy

A. Brute force: generate all possible sequences of '(' and ')' of length 2n, then filter valid ones

B. Backtracking with pruning: build sequences by adding '(' or ')' only when it keeps the sequence valid

C. Greedy approach: always add '(' until n is reached, then add ')' to close all opened parentheses

D. Dynamic programming: count the number of valid sequences using Catalan number formula

Solution

1. Step 1: Understand problem constraints

   We want to generate all valid parentheses sequences without generating invalid ones first.

2. Step 2: Analyze approaches

   Brute force generates all sequences including invalid ones, greedy fails to generate all valid sequences, DP counts sequences but does not generate them. Backtracking with pruning adds '(' or ')' only when valid, thus generating only valid sequences.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with pruning avoids invalid sequences [OK]

Hint: Backtracking prunes invalid sequences early [OK]

Common Mistakes:

• Thinking greedy can generate all valid sequences
• Confusing counting with generating sequences

2. Given the following code snippet for getPermutation, what is the returned value when calling getPermutation(3, 3)?

easy

A. '123'

B. '312'

C. '213'

D. '231'

Solution

1. Step 1: Trace factorial array computation

   factorial = [1, 1, 2] for n=3.

2. Step 2: Calculate indices and build result

   k=3 -> k=2 zero-based. For i=2: idx=2//2=1, pick '2'. For i=1: k=2%2=0, idx=0//1=0, pick '1'. For i=0: k=0%1=0, idx=0//1=0, pick '3'. Result = '213'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected k-th permutation '213' [OK]

Hint: Remember to convert k to zero-based before indexing [OK]

Common Mistakes:

• Off-by-one error in k adjustment
• Wrong index calculation in loop
• Not popping used numbers

3. Consider this modified code snippet for generating parentheses. Which line contains a subtle bug that can cause invalid sequences to be generated?

medium

A. Line with 'if close_count <= open_count:' condition

B. Line with 's.pop()' after backtrack calls

C. Line with 'if open_count < n:' condition

D. Line with 'if len(s) == 2 * n:' base case

Solution

1. Step 1: Examine close_count condition

   The condition 'close_count <= open_count' allows adding ')' even when close_count equals open_count, which can produce invalid sequences.

2. Step 2: Correct condition

   The correct condition is 'close_count < open_count' to ensure ')' is added only when there are unmatched '('.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to '<' fixes invalid sequence generation [OK]

Hint: Close count must be strictly less than open count [OK]

Common Mistakes:

• Using <= instead of < for close_count condition
• Forgetting to pop after recursion

4. What is the time complexity of the optimal backtracking algorithm that generates unique permutations of an array with duplicates by sorting and skipping duplicates during recursion?

medium

A. O(n! * log n) due to sorting and binary search for duplicates

B. O(n! * n^2) because each permutation requires copying the array and checking duplicates

C. O(n^n) because the recursion explores all possible swaps without pruning

D. O(n! * n) because pruning duplicates early reduces redundant branches but each permutation still requires O(n) copying

Solution

1. Step 1: Identify complexity of outer and inner loops

   Backtracking explores permutations, which is O(n!). Each permutation requires copying O(n) elements to result.

2. Step 2: Check if pruning duplicates reduces complexity

   Pruning duplicates early avoids redundant branches, so complexity is O(n! * n), not worse. Sorting is O(n log n) but done once.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Pruning reduces branches but copying each permutation costs O(n) [OK]

Hint: Pruning duplicates reduces branches but copying costs O(n) per permutation [OK]

Common Mistakes:

• Confusing pruning effect or ignoring copy cost

5. Suppose you want to modify the palindrome partitioning algorithm to allow reuse of substrings in partitions (i.e., substrings can appear multiple times in different partitions). Which change to the algorithm is necessary to correctly handle this variant without losing valid partitions or causing duplicates?

hard

A. Memoize palindrome checks and reuse results but keep backtracking unchanged

B. Modify backtracking to avoid popping from path to reuse substrings across calls

C. Use a global visited set to skip substrings already used in previous partitions

D. Allow substrings to be reused by resetting path after each complete partition

Solution

1. Step 1: Understand reuse requirement

   Reusing substrings means substrings can appear multiple times in different partitions, so path management must allow multiple uses.

2. Step 2: Identify necessary algorithm change

   Memoizing palindrome checks improves efficiency by avoiding repeated palindrome computations, while backtracking logic remains unchanged to generate all valid partitions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Memoization optimizes palindrome checks without affecting partition generation correctness [OK]

Hint: Memoize palindrome checks to optimize without changing backtracking [OK]

Common Mistakes:

• Assuming popping affects substring reuse
• Using visited sets that block valid reuse
• Resetting path incorrectly losing partitions