N Queens Problem in DSA Python - Execution Trace

Concept Flow - N Queens Problem

Start with empty board

↓

Place queen in row 0, col 0

↓

Check if safe

Yes↓

Move to next row

↓

Try placing queen in next row

↓

If no safe position, backtrack

↓

Remove queen from previous row

↓

Try next column in previous row

↓

Repeat until all queens placed or no solution

↓

Print solution or backtrack further

The algorithm tries to place queens row by row, checking safety, and backtracks if no safe position is found.

Execution Sample

DSA Python

def solve_n_queens(board, row):
    if row == len(board):
        print_board(board)
        return True
    for col in range(len(board)):
        if is_safe(board, row, col):
            board[row][col] = 'Q'
            if solve_n_queens(board, row + 1):
                return True
            board[row][col] = '.'
    return False

This code tries to place queens row by row, backtracking when no safe column is found.

Execution Table

Step	Operation	Row	Column Tried	Action	Board State
1	Place queen	0	1	Safe, place Q	[. Q . .] [. . . .] [. . . .] [. . . .]
2	Place queen	1	1	Not safe, try next	[. Q . .] [. . . .] [. . . .] [. . . .]
3	Place queen	1	2	Not safe, try next	[. Q . .] [. . . .] [. . . .] [. . . .]
4	Place queen	1	3	Safe, place Q	[. Q . .] [. . . Q] [. . . .] [. . . .]
5	Place queen	2	1	Not safe, try next	[. Q . .] [. . . Q] [. . . .] [. . . .]
6	Place queen	2	2	Not safe, try next	[. Q . .] [. . . Q] [. . . .] [. . . .]
7	Place queen	2	0	Safe, place Q	[. Q . .] [. . . Q] [Q . . .] [. . . .]
8	Place queen	3	1	Not safe, try next	[. Q . .] [. . . Q] [Q . . .] [. . . .]
9	Place queen	3	2	Safe, place Q	[. Q . .] [. . . Q] [Q . . .] [. . Q .]
10	All queens placed	-	-	Solution found	[. Q . .] [. . . Q] [Q . . .] [. . Q .]

💡 All 4 queens placed safely, solution found.

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 7	After Step 9	Final
row	0	1	2	3	4	4
board	[. . . .] [. . . .] [. . . .] [. . . .]	[. Q . .] [. . . .] [. . . .] [. . . .]	[. Q . .] [. . . Q] [. . . .] [. . . .]	[. Q . .] [. . . Q] [Q . . .] [. . . .]	[. Q . .] [. . . Q] [Q . . .] [. . Q .]	[. Q . .] [. . . Q] [Q . . .] [. . Q .]

Key Moments - 3 Insights

Why do we backtrack and remove a queen from the board?

When no safe column is found in a row (see steps 5 and 6), we remove the queen placed in the previous row to try a new position (backtracking). This is shown in the execution_table where after failing to place in row 2 columns 1 and 2, the algorithm tries a different column.

How do we know if a position is safe for placing a queen?

A position is safe if no other queen attacks it vertically, horizontally, or diagonally. The execution_table shows attempts in columns that are unsafe being skipped (steps 2 and 3).

When does the algorithm stop?

The algorithm stops when all queens are placed safely (row equals board size). Step 10 shows the final solution and termination.

Visual Quiz - 3 Questions

Look at the execution_table, what is the board state after step 4?

A [. Q . .] [. . . Q] [. . . .] [. . . .]

B [. Q . .] [. . . .] [. . . .] [. . . .]

C [. Q . .] [. . . .] [Q . . .] [. . . .]

D [. . . .] [. . . .] [. . . .] [. . . .]

💡 Hint

Check the 'Board State' column in row with Step 4 in execution_table.

At which step does the algorithm place the queen in row 3, column 2?

A Step 8

B Step 9

C Step 7

D Step 10

💡 Hint

Look at the 'Row' and 'Column Tried' columns in execution_table for row 3 and column 2.

If the queen at row 2, column 0 was not safe, what would happen next?

A The algorithm would backtrack to row 1 and try next column

B The algorithm would place queen at row 3 immediately

C The algorithm would try next column in row 2

D The algorithm would stop and print solution

💡 Hint

Refer to the backtracking logic shown between steps 5-7 in execution_table.

Concept Snapshot

N Queens Problem:
- Place N queens on NxN board so no two queens attack each other.
- Place queens row by row, checking safety.
- If no safe spot in a row, backtrack to previous row.
- Repeat until all queens placed or no solution.
- Uses recursion and backtracking.

Full Transcript

The N Queens Problem places N queens on an NxN chessboard so that no two queens threaten each other. The algorithm tries to place queens one row at a time. For each row, it tries each column and checks if placing a queen there is safe. If safe, it places the queen and moves to the next row. If no safe column is found, it backtracks by removing the queen from the previous row and tries the next column there. This continues until all queens are placed safely or no solution exists. The execution table shows step-by-step queen placements and backtracking on a 4x4 board, ending with a valid solution.

Practice

1. What is the main goal of the N Queens Problem?

easy

A. Place N queens on an NxN chessboard so that no two queens attack each other

B. Count the total number of queens on a chessboard

C. Move queens to capture all opponent pieces

D. Arrange queens in a single row on the chessboard

Solution

1. Step 1: Understand the problem statement

   The N Queens Problem requires placing N queens on an NxN board so that no two queens threaten each other.

2. Step 2: Analyze the options

   Only Place N queens on an NxN chessboard so that no two queens attack each other correctly describes placing queens so none attack each other. Other options describe unrelated tasks.

3. Final Answer:

   Place N queens on an NxN chessboard so that no two queens attack each other -> Option A

4. Quick Check:

   Goal = Place queens safely [OK]

Hint: Remember: no two queens can share row, column, or diagonal [OK]

Common Mistakes:

• Thinking queens can be in the same row or column
• Confusing the problem with counting queens
• Assuming queens can attack each other

2. Which of the following Python code snippets correctly initializes an empty chessboard for the N Queens Problem with size n?

easy

A. board = [[0 for _ in range(n)] for _ in range(n)]

B. board = [[0]*n]

C. board = [0]*n

D. board = [[0]*n]*n

Solution

1. Step 1: Understand board initialization

   We need a 2D list with independent rows to represent the chessboard.

2. Step 2: Analyze each option

   board = [[0]*n]*n creates rows referencing the same list, causing bugs. board = [[0 for _ in range(n)] for _ in range(n)] creates independent rows correctly. board = [0]*n creates a 1D list, not 2D. board = [[0]*n] creates a single row only.

3. Final Answer:

   board = [[0 for _ in range(n)] for _ in range(n)] -> Option A

4. Quick Check:

   Independent rows = board = [[0 for _ in range(n)] for _ in range(n)] [OK]

Hint: Use nested list comprehension for independent rows [OK]

Common Mistakes:

• Using [[0]*n]*n causing shared references
• Creating 1D list instead of 2D
• Forgetting to repeat for each row

3. What will be the output of the following Python code snippet for n = 4?

def is_safe(board, row, col):
    for i in range(col):
        if board[row][i] == 1:
            return False
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    for i, j in zip(range(row, len(board), 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    return True

board = [[0]*4 for _ in range(4)]
board[1][0] = 1
print(is_safe(board, 1, 1))
print(is_safe(board, 0, 1))

medium

A. True\nFalse

B. False\nFalse

C. False\nTrue

D. True\nTrue

Solution

1. Step 1: Check is_safe for position (1,1)

   Column check: board[1][0] == 1, so returns False.

2. Step 2: Check is_safe for position (0,1)

   Row left: board[0][0] == 0. Upper diagonal: board[0][1] == 0. Lower diagonal: board[1][0] == 1, so returns False.

3. Final Answer:

   False\nFalse -> Option B

4. Quick Check:

   Check columns and diagonals = False, False [OK]

Hint: Check columns and diagonals left of position [OK]

Common Mistakes:

• Ignoring diagonal checks
• Confusing row and column indices
• Assuming safe if no queen in same row only

4. Identify the error in the following code snippet for solving the N Queens Problem:

def solve_n_queens(board, col):
    if col >= len(board):
        return True
    for row in range(len(board)):
        if is_safe(board, row, col):
            board[row][col] = 1
            if solve_n_queens(board, col + 1):
                return True
            board[row][col] = 0
    return False

board = [[0]*4 for _ in range(4)]
solve_n_queens(board, 0)
print(board)

medium

A. The base case condition is incorrect

B. The board is not reset properly after backtracking

C. The function returns True too early, missing all solutions

D. The is_safe function is not called

Solution

1. Step 1: Analyze the recursion and return statements

   The function returns True immediately after finding the first solution, so it stops searching further.

2. Step 2: Understand impact on solution finding

   This means it finds only one solution and does not explore all possible solutions.

3. Final Answer:

   The function returns True too early, missing all solutions -> Option C

4. Quick Check:

   Early return stops full search [OK]

Hint: Return True only after exploring all columns [OK]

Common Mistakes:

• Stopping recursion after first solution
• Not resetting board on backtrack
• Incorrect base case check

5. Given the N Queens Problem, which approach best improves efficiency by reducing unnecessary checks during queen placement?

hard

A. Place queens randomly and retry if conflicts occur

B. Check the entire board for conflicts every time before placing a queen

C. Use nested loops to try all possible board configurations without pruning

D. Use backtracking with arrays to track columns and diagonals already occupied

Solution

1. Step 1: Understand efficiency in N Queens

   Checking the entire board repeatedly wastes time; pruning reduces checks.

2. Step 2: Analyze options for pruning

   Using arrays to track columns and diagonals occupied avoids repeated scanning, improving speed.

3. Final Answer:

   Use backtracking with arrays to track columns and diagonals already occupied -> Option D

4. Quick Check:

   Pruning with tracking arrays = Use backtracking with arrays to track columns and diagonals already occupied [OK]

Hint: Track columns and diagonals to skip invalid spots fast [OK]

Common Mistakes:

• Checking full board every time
• Trying random placements without pruning
• Using brute force without backtracking