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. You are given a string containing only digits. Your task is to split it into exactly four parts such that each part represents a valid IP address segment (0 to 255, no leading zeros except for '0'). Which algorithmic approach guarantees finding all valid IP addresses efficiently?

easy

A. Sorting the digits and then partitioning into four segments

B. Greedy approach that picks the shortest valid segment at each step

C. Dynamic programming to count the number of valid segmentations

D. Backtracking with pruning to explore all valid segmentations

Solution

1. Step 1: Understand the problem constraints

   The problem requires enumerating all valid IP addresses, which involves exploring multiple segmentations of the string.

2. Step 2: Evaluate algorithm suitability

   Greedy approaches fail because they may miss valid segmentations; DP counting does not generate all solutions; sorting digits destroys original order. Backtracking with pruning systematically explores all valid partitions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking explores all partitions with pruning to avoid invalid segments [OK]

Hint: Backtracking explores all segmentations with pruning [OK]

Common Mistakes:

• Assuming greedy can find all valid IPs
• Using DP counting without generating solutions

2. What is the time complexity of the backtracking with bitmask optimization approach for counting beautiful arrangements of size n?

medium

A. O(n * n!)

B. O(n^2)

C. O(n * 2^n)

D. O(n!)

Solution

1. Step 1: Identify the search space

   The algorithm explores permutations of n numbers, which is n! in worst case.

2. Step 2: Consider pruning and bitmask usage

   Bitmask helps track used numbers efficiently, pruning invalid branches but the total number of recursive calls is proportional to n * n! because for each position, up to n choices are tried.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores permutations with n choices per position, leading to O(n * n!) complexity [OK]

Hint: Backtracking permutations with bitmask -> O(n * n!) time [OK]

Common Mistakes:

• Confusing bitmask with exponential 2^n complexity
• Assuming polynomial due to pruning

3. What is the time complexity of the optimal palindrome partitioning algorithm that uses backtracking with dynamic palindrome checks by expanding around centers for palindrome verification on a string of length n?

medium

A. O(n^2) because palindrome checks are done in constant time using DP

B. O(n^3) due to checking all substrings and palindrome verification

C. O(2^n) since all partitions are generated without extra palindrome checks

D. O(n * 2^n) because each character can start a partition and palindrome checks are O(n)

Solution

1. Step 1: Identify number of partitions

   There are up to 2^(n-1) ways to partition a string of length n.

2. Step 2: Analyze palindrome check cost

   Using expand around center, palindrome check per substring is O(n) worst case, done during backtracking.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Combining partitions and palindrome checks yields O(n * 2^n) [OK]

Hint: Partitions grow exponentially; palindrome checks add linear factor [OK]

Common Mistakes:

• Assuming palindrome checks are O(1) without DP
• Confusing total partitions with time complexity
• Ignoring recursion stack space

4. What is the time complexity of the BFS approach for removing invalid parentheses from a string of length n, considering the worst case?

medium

A. O(n * 2^n) because there can be up to 2^n states and each validity check takes O(n)

B. O(n!) because permutations of removals are explored

C. O(2^n) because BFS explores all subsets of characters without repeated checks

D. O(n^2) because each level removes one character and checks validity in O(n)

Solution

1. Step 1: Count possible states

   Each character can be either removed or kept, so up to 2^n possible strings can be generated.

2. Step 2: Analyze per-state cost

   Each string requires an O(n) validity check, so total worst-case time is O(n * 2^n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   2^n states times O(n) validity checks [OK]

Hint: 2^n states times O(n) validity checks [OK]

Common Mistakes:

• Confusing O(n^2) with BFS complexity
• Ignoring validity check cost
• Assuming factorial complexity

5. Examine the following code snippet for the Word Search II problem. Which line contains a subtle bug that can cause incorrect results or infinite loops?

medium

A. Line: currNode = node.children.get(letter)

B. Line: Missing marking of board[r][c] as visited before recursion

C. Line: if currNode.word:

D. Line: board[r][c] = letter at the end

Solution

1. Step 1: Identify visited marking necessity

   Backtracking requires marking the current cell as visited (e.g., replacing letter with '#') to avoid revisiting the same cell in the current path.

2. Step 2: Locate missing visited marking

   The code lacks the line that marks board[r][c] as visited before recursive calls, causing revisits and potential infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without visited marking, recursion revisits same cells [OK]

Hint: Visited marking prevents revisiting same cell in recursion [OK]

Common Mistakes:

• Forgetting to mark visited cells or unmark after recursion.