N-Queens

▶

Steps

setup

Start Backtracking at Row 0

The algorithm begins at row 0 with empty board and no columns or diagonals attacked (cols=0, diag1=0, diag2=0).

💡 Starting with no queens placed means all columns are available for the first queen placement.

Line:

backtrack(0, 0, 0, 0)

💡 Initial call sets the stage for recursive exploration of queen placements row by row.

fill_cells

Calculate Available Positions at Row 0

Compute available_positions by negating attacked columns and diagonals and masking with (1 << n) - 1 to keep only n bits.

💡 This bitmask shows which columns in row 0 are safe to place a queen.

Line:

available_positions = ((1 << n) - 1) & (~(cols | diag1 | diag2))

💡 All columns are available initially since no attacks exist.

insert

Place Queen at Row 0, Column 0

Extract rightmost 1-bit from available_positions to place queen at column 0, update board and bitmasks accordingly.

💡 Choosing the leftmost available column first is a systematic way to explore all options.

Line:

position = available_positions & (-available_positions)
available_positions &= available_positions - 1
col = (position & -position).bit_length() - 1
board[row][col] = 'Q'

💡 Bitmask operations efficiently select the next column to try without scanning all bits.

traverse

Recurse to Row 1 with Updated Bitmasks

Call backtrack for row 1, updating cols, diag1, diag2 to mark attacks from queen at (0,0).

💡 Updating bitmasks propagates attack constraints to the next row.

Line:

backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)

💡 Bitmasks track attacked columns and diagonals compactly, enabling fast pruning.

fill_cells

Calculate Available Positions at Row 1

Compute available_positions for row 1 considering attacks from previous queen placements.

💡 This step shows which columns are safe for the queen in row 1.

Line:

available_positions = ((1 << n) - 1) & (~(cols | diag1 | diag2))

💡 Bitmask shows only columns 2 and 3 are free at row 1.

insert

Place Queen at Row 1, Column 2

Select rightmost available bit (column 2) to place queen, update board and bitmasks.

💡 Systematic choice of next available column continues the search.

Line:

position = available_positions & (-available_positions)
available_positions &= available_positions - 1
col = (position & -position).bit_length() - 1
board[row][col] = 'Q'

💡 Bitmask extraction efficiently picks the next column without iteration.

traverse

Recurse to Row 2 with Updated Bitmasks

Call backtrack for row 2 with updated cols, diag1, diag2 reflecting attacks from queens at (0,0) and (1,2).

💡 Bitmasks propagate constraints to the next row to prune invalid placements.

Line:

backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)

💡 The recursion deepens with updated attack masks narrowing available columns.

fill_cells

Calculate Available Positions at Row 2

Compute available_positions for row 2 considering attacks from queens placed so far.

💡 This shows which columns are safe for the queen in row 2.

Line:

available_positions = ((1 << n) - 1) & (~(cols | diag1 | diag2))

💡 Only column 1 is available at row 2 after pruning.

insert

Place Queen at Row 2, Column 1

Place queen at column 1, update board and bitmasks accordingly.

💡 Placing queen at the only available column continues the search.

Line:

position = available_positions & (-available_positions)
available_positions &= available_positions - 1
col = (position & -position).bit_length() - 1
board[row][col] = 'Q'

💡 Bitmask operations continue to efficiently select positions.

traverse

Recurse to Row 3 with Updated Bitmasks

Call backtrack for row 3 with updated bitmasks reflecting attacks from queens placed so far.

💡 Constraints propagate to the last row to find valid placements.

Line:

backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)

💡 The recursion reaches the last row with updated constraints.

fill_cells

Calculate Available Positions at Row 3

Compute available_positions for row 3 considering attacks from queens placed so far.

💡 This determines if a queen can be placed in row 3.

Line:

available_positions = ((1 << n) - 1) & (~(cols | diag1 | diag2))

💡 Only column 3 is available at row 3.

insert

Place Queen at Row 3, Column 3

Place queen at column 3, update board and bitmasks.

💡 Placing queen at the only available column completes a valid solution.

Line:

position = available_positions & (-available_positions)
available_positions &= available_positions - 1
col = (position & -position).bit_length() - 1
board[row][col] = 'Q'

💡 This placement leads to a complete valid solution.

reconstruct

Record Complete Solution at Row 4

Reached base case row == n, record current board configuration as a valid solution.

💡 Base case signals a full valid placement of queens on the board.

Line:

if row == n:
    solutions.append([''.join(r) for r in board])
    return

💡 The algorithm successfully found one of the two solutions for n=4.

delete

Backtrack from Row 3, Try Next Position

Remove queen from (3,3) and try next available positions at row 3 (none left), so backtrack further.

💡 Backtracking removes last queen to explore alternative placements.

Line:

board[row][col] = '.'

💡 Backtracking systematically explores all options by undoing previous choices.

delete

Backtrack from Row 2, Try Next Position

Remove queen from (2,1), try next available positions at row 2 (none left), backtrack to row 1.

💡 Backtracking continues to explore all possible queen placements.

Line:

board[row][col] = '.'

💡 Backtracking ensures no valid solution is missed.

insert

Place Queen at Row 1, Column 3

Try next available position at row 1: column 3, update board and bitmasks.

💡 Exploring alternative queen placements at row 1.

Line:

position = available_positions & (-available_positions)
available_positions &= available_positions - 1
col = (position & -position).bit_length() - 1
board[row][col] = 'Q'

💡 Backtracking explores all branches by trying all available positions.

traverse

Recurse to Row 2 with Updated Bitmasks (Second Branch)

Call backtrack for row 2 with updated bitmasks from queens at (0,0) and (1,3).

💡 Constraints update for new queen placement to prune invalid positions.

Line:

backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)

💡 The recursion explores a new branch with different constraints.

fill_cells

Calculate Available Positions at Row 2 (Second Branch)

Compute available_positions for row 2 with updated bitmasks.

💡 Shows which columns are safe for queen placement in this branch.

Line:

available_positions = ((1 << n) - 1) & (~(cols | diag1 | diag2))

💡 Only column 1 is available at row 2 in this branch.

insert

Place Queen at Row 2, Column 1 (Second Branch)

Place queen at column 1, update board and bitmasks.

💡 Placing queen at the only available column continues the search.

Line:

position = available_positions & (-available_positions)
available_positions &= available_positions - 1
col = (position & -position).bit_length() - 1
board[row][col] = 'Q'

💡 Bitmask operations continue to efficiently select positions.

traverse

Recurse to Row 3 (Second Branch)

Call backtrack for row 3 with updated bitmasks from queens at (0,0), (1,3), (2,1).

💡 Constraints update for last row to find valid placements.

Line:

backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)

💡 The recursion explores the last row in this branch.

def solveNQueens(n):
    solutions = []
    board = [['.' for _ in range(n)] for _ in range(n)]

    def backtrack(row, cols, diag1, diag2):
        if row == n:  # STEP 13: base case, record solution
            solutions.append([''.join(r) for r in board])
            return
        available_positions = ((1 << n) - 1) & (~(cols | diag1 | diag2))  # STEP 2,5,8,11,18
        while available_positions:
            position = available_positions & (-available_positions)  # STEP 3,6,9,12,16,19
            available_positions &= available_positions - 1  # STEP 3,6,9,12,16,19
            col = (position & -position).bit_length() - 1
            board[row][col] = 'Q'  # STEP 3,6,9,12,16,19
            backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)  # STEP 4,7,10,13,17,20
            board[row][col] = '.'  # STEP 14,15

    backtrack(0, 0, 0, 0)  # STEP 1
    return solutions

if __name__ == '__main__':
    print(solveNQueens(4))

📊

N-Queens - Watch the Algorithm Execute, Step by Step

Watching each recursive call and bitmask update reveals how the algorithm efficiently prunes invalid queen placements and backtracks to find all solutions.

enteringrow=0cols=0diag1=0diag2=0

Call Path (current → root)

backtrack(row=0, cols=0, diag1=0, diag2=0)

choosingrow=0cols=0diag1=0diag2=0

Call Path (current → root)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Remaining

0b1111

choosingrow=0cols=0diag1=0diag2=0

Call Path (current → root)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b0001

Remaining

0b1110

Partial: [(0,0)]

enteringrow=1cols=1diag1=2diag2=0

Call Path (current → root)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Partial: [(0,0)]

choosingrow=1cols=1diag1=2diag2=0

Call Path (current → root)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Remaining

0b1100

Partial: [(0,0)]

choosingrow=1cols=1diag1=2diag2=0

Call Path (current → root)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b0100

Remaining

0b1000

Partial: [(0,0), (1,2)]

enteringrow=2cols=5diag1=8diag2=1

Call Path (current → root)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Partial: [(0,0), (1,2)]

choosingrow=2cols=5diag1=8diag2=1

Call Path (current → root)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Remaining

0b0010

Partial: [(0,0), (1,2)]

choosingrow=2cols=5diag1=8diag2=1

Call Path (current → root)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b0010

Partial: [(0,0), (1,2), (2,1)]

enteringrow=3cols=7diag1=18diag2=0

Call Path (current → root)

backtrack(row=3, cols=7, diag1=18, diag2=0)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Partial: [(0,0), (1,2), (2,1)]

choosingrow=3cols=7diag1=18diag2=0

Call Path (current → root)

backtrack(row=3, cols=7, diag1=18, diag2=0)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Remaining

0b1000

Partial: [(0,0), (1,2), (2,1)]

choosingrow=3cols=7diag1=18diag2=0

Call Path (current → root)

backtrack(row=3, cols=7, diag1=18, diag2=0)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b1000

Partial: [(0,0), (1,2), (2,1), (3,3)]

backtrackingrow=4cols=15diag1=36diag2=1

Call Path (current → root)

backtrack(row=4, cols=15, diag1=36, diag2=1)

backtrack(row=3, cols=7, diag1=18, diag2=0)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Partial: [(0,0), (1,2), (2,1), (3,3)]

Found 1: [.Q..,...Q,Q...,..Q.]

backtrackingrow=3cols=7diag1=18diag2=0

Call Path (current → root)

backtrack(row=3, cols=7, diag1=18, diag2=0)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b1000

Partial: [(0,0), (1,2), (2,1)]

Found 1: [.Q..,...Q,Q...,..Q.]

backtrackingrow=2cols=5diag1=8diag2=1

Call Path (current → root)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b0010

Partial: [(0,0), (1,2)]

Found 1: [.Q..,...Q,Q...,..Q.]

choosingrow=1cols=1diag1=2diag2=0

Call Path (current → root)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b01000b1000

Partial: [(0,0), (1,3)]

Found 1: [.Q..,...Q,Q...,..Q.]

enteringrow=2cols=9diag1=20diag2=1

Call Path (current → root)

backtrack(row=1, cols=9, diag1=20, diag2=1)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Partial: [(0,0), (1,3)]

Found 1: [.Q..,...Q,Q...,..Q.]

choosingrow=2cols=9diag1=20diag2=1

Call Path (current → root)

backtrack(row=1, cols=9, diag1=20, diag2=1)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Remaining

0b0010

Partial: [(0,0), (1,3)]

Found 1: [.Q..,...Q,Q...,..Q.]

choosingrow=2cols=9diag1=20diag2=1

Call Path (current → root)

backtrack(row=1, cols=9, diag1=20, diag2=1)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b0010

Partial: [(0,0), (1,3), (2,1)]

Found 1: [.Q..,...Q,Q...,..Q.]

enteringrow=3cols=11diag1=44diag2=0

Call Path (current → root)

backtrack(row=3, cols=11, diag1=44, diag2=0)

backtrack(row=2, cols=9, diag1=20, diag2=1)

backtrack(row=1, cols=9, diag1=20, diag2=1)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Partial: [(0,0), (1,3), (2,1)]

Found 1: [.Q..,...Q,Q...,..Q.]

Key Takeaways

✓ Bitmasking efficiently tracks attacked columns and diagonals, enabling fast pruning of invalid queen placements.

This insight is hard to see from code alone because bitwise operations are compact and non-intuitive without visualization.

✓ The recursion tree shows how the algorithm explores each row, tries all available columns, and backtracks when no options remain.

Visualizing each recursive call clarifies the systematic search and pruning process.

✓ Solutions are collected only at the base case when all rows have queens placed, demonstrating how partial answers build up to complete solutions.

Understanding when and how solutions are recorded is clearer when watching the recursion unfold step-by-step.

Practice

1. What is the time complexity of the optimal backtracking solution for the Expression Add Operators problem, where n is the length of the input string? Assume the solution tries all operator insertions and substring splits with pruning and efficient string building.

medium

A. O(4^n) because at each position there are up to 4 choices (3 operators + no operator split)

B. O(n * 3^n) because each digit can be combined with 3 operators and substring splits

C. O(2^n) since only two operators are considered at each step

D. O(n^3) due to substring parsing and operator insertions

Solution

1. Step 1: Identify branching factor per digit

   At each digit, we can insert one of 3 operators (+, -, *) or choose to extend the current operand (no operator), but the main branching factor is 3 operators per split, and substring splits add a factor of n.

2. Step 2: Calculate total complexity

   The total complexity is roughly O(n * 3^n) because for each of the n positions, there are up to 3 operator choices, and substring splits add an n factor.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Exponential branching with 3 operators and substring splits [OK]

Hint: 3 operators per digit and substring splits lead to O(n * 3^n) complexity [OK]

Common Mistakes:

• Confusing substring parsing cost as cubic
• Assuming only 2 operators reduce complexity
• Miscounting branching factor as 4

2. The following code attempts to count all N-Queens solutions using bitmask backtracking. Which line contains a subtle bug that causes incorrect counts?

medium

A. Line extracting rightmost 1-bit from available_positions

B. Line updating neg_diags by shifting right after adding position

C. Line updating pos_diags by shifting left after adding position

D. Line computing available_positions with bitwise negation

Solution

1. Step 1: Understand diagonal bitmask updates

   Positive diagonals shift left by 1, negative diagonals shift right by 1 to track attacks on next row.

2. Step 2: Identify incorrect shift directions

   Code incorrectly shifts pos_diags right and neg_diags left, reversing diagonal tracking and causing missed conflicts.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct diagonal updates are pos_diags << 1 and neg_diags >> 1 [OK]

Hint: Diagonal bitmasks must shift opposite directions each row [OK]

Common Mistakes:

• Swapping pos and neg diagonal shifts
• Forgetting to shift diagonals at all

3. Suppose the problem changes so that each element in the input array can be used multiple times in each permutation (i.e., unlimited reuse). Which modification to the backtracking algorithm correctly generates all unique permutations with duplicates allowed and reuse permitted?

hard

A. Use backtracking without swapping, but at each recursion level, iterate over all elements and skip duplicates using a 'used' boolean array to avoid repeated elements at the same recursion depth.

B. Remove the 'seen' set and allow swapping elements freely without skipping duplicates.

C. Sort the array and use the same swapping and 'seen' set logic as before, but do not increment the recursion start index to allow reuse.

D. Generate all permutations without sorting or skipping duplicates, then filter duplicates at the end using a hash set.

Solution

1. Step 1: Understand reuse requirement

   Unlimited reuse means elements can be chosen multiple times at each recursion level, so swapping and incrementing start index is not suitable.

2. Step 2: Identify correct approach

   Backtracking without swapping, iterating over all elements at each recursion level, and using a 'used' boolean array to skip duplicates at the same depth ensures unique permutations with reuse.

3. Step 3: Evaluate other options

   Removing 'seen' causes duplicates; swapping without incrementing start index breaks logic; filtering duplicates after generation is inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with reuse requires iteration over all elements each recursion, not swapping with start index increment [OK]

Hint: Reuse requires iteration over all elements each recursion, not swapping with start index increment [OK]

Common Mistakes:

• Trying to reuse elements by swapping without adjusting recursion index or skipping duplicates properly

4. Suppose the problem is modified so that parentheses can be reused multiple times (e.g., you can insert removed parentheses back anywhere). Which of the following algorithmic changes correctly adapts the BFS approach to handle this variant?

hard

A. Switch to backtracking with memoization to explore insertions and removals explicitly, pruning invalid states

B. Use BFS as is, since it already explores all possible removals and insertions implicitly

C. Use a greedy approach to insert parentheses at earliest invalid positions without BFS or backtracking

D. Modify BFS to allow adding parentheses back by generating new states with insertions at every position

Solution

1. Step 1: Understand reuse of parentheses

   Allowing reuse means we can insert parentheses anywhere, greatly increasing state space and complexity.

2. Step 2: Analyze BFS suitability

   Standard BFS only removes characters; it does not handle insertions, so it cannot explore all states correctly.

3. Step 3: Identify correct approach

   Backtracking with memoization can explicitly explore insertions and removals, pruning invalid states to handle reuse properly.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with memoization handles insertions and pruning [OK]

Hint: Reuse requires explicit insertion exploration, not just removal BFS [OK]

Common Mistakes:

• Assuming BFS handles insertions
• Using greedy for complex insertions
• Modifying BFS without pruning leads to explosion

5. Suppose the Sudoku solver is modified so that digits can be reused multiple times in the same row, column, or box (i.e., constraints are relaxed). Which of the following statements about the backtracking algorithm is true?

hard

A. Constraint checks can be removed, and backtracking reduces to brute force filling

B. Heuristic ordering of empty cells becomes unnecessary since constraints are relaxed

C. The existing backtracking with constraint propagation still works correctly without changes

D. The problem becomes trivial and can be solved in linear time by filling all empty cells with '1'

Solution

1. Step 1: Understand effect of relaxing constraints

   Allowing repeated digits removes Sudoku constraints, so no need to check row, column, or box validity.

2. Step 2: Impact on backtracking algorithm

   Backtracking degenerates to brute force filling since any digit can be placed anywhere; constraint propagation is useless.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Relaxed constraints mean no pruning, so backtracking is brute force [OK]

Hint: Relaxed constraints remove pruning, reverting to brute force [OK]

Common Mistakes:

• Assuming heuristics still help
• Thinking problem becomes trivial linear time