Bird
Raised Fist0
Interview PrepbacktrackinghardAmazonGoogle

N-Queens II (Count Solutions)

Choose your preparation mode3 modes available
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.
📊
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.
Step 1/20
·Active fillAnswer cell
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.