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.