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.