N Queens Problem in DSA C++ - 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

↓

Place queen in next row

↓

If no safe place, backtrack

↓

Remove queen from previous row

↓

Try next column

↓

Repeat until all queens placed or no solution

↓

Print solution or backtrack

↓

End

The flow shows placing queens row by row, checking safety, backtracking if needed, until all queens are placed.

Execution Sample

DSA C++

bool solve(int row) {
  if (row == N) return true;
  for (int col = 0; col < N; col++) {
    if (isSafe(row, col)) {
      board[row][col] = 'Q';
      if (solve(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	Action	Board State	Backtrack
1	Place queen	0	0	Check safe, place Q	Q . . . . . . . . . . . . . . .	No
2	Place queen	1	0	Not safe, skip	Q . . . . . . . . . . . . . . .	No
3	Place queen	1	1	Not safe, skip	Q . . . . . . . . . . . . . . .	No
4	Place queen	1	2	Safe, place Q	Q . . . . . Q . . . . . . . . .	No
5	Place queen	2	0	Not safe, skip	Q . . . . . Q . . . . . . . . .	No
6	Place queen	2	1	Not safe, skip	Q . . . . . Q . . . . . . . . .	No
7	Place queen	2	2	Not safe, skip	Q . . . . . Q . . . . . . . . .	No
8	Place queen	2	3	Safe, place Q	Q . . . . . Q . . . . Q . . . .	No
9	Place queen	3	0	Not safe, skip	Q . . . . . Q . . . . Q . . . .	No
10	Place queen	3	1	Safe, place Q	Q . . . . . Q . . . . Q . Q . .	No
11	All queens placed	-	-	Solution found	Q . . . . . Q . . . . Q . Q . .	No
12	Backtrack	3	1	Remove queen	Q . . . . . Q . . . . Q . . . .	Yes
13	Backtrack	2	3	Remove queen	Q . . . . . Q . . . . . . . . .	Yes
14	Try next col in row 2	2	4	No column 4, backtrack	Q . . . . . Q . . . . . . . . .	Yes
15	Backtrack	1	2	Remove queen	Q . . . . . . . . . . . . . . .	Yes
16	Try next col in row 1	1	3	Safe, place Q	Q . . . . . . Q . . . . . . . .	No
17	Place queen	2	0	Safe, place Q	Q . . . . . . Q Q . . . . . . .	No
18	Place queen	3	1	Not safe, skip	Q . . . . . . Q Q . . . . . . .	No
19	Place queen	3	2	Safe, place Q	Q . . . . . . Q Q . . . . . Q .	No
20	All queens placed	-	-	Solution found	Q . . . . . . Q Q . . . . . Q .	No
21	End	-	-	No more moves	Final solutions found	No

💡 All rows processed or no more columns to try, solutions found or backtracked fully.

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 8	After Step 10	After Step 11	After Step 15	After Step 16	After Step 20	Final
row	0	1	2	3	3	-	1	2	3	-
col	-	0	2	3	1	-	3	3	2	-
board	empty	Q . . . . . . . . . . . . . . .	Q . . . . . Q . . . . . . . . .	Q . . . . . Q . . . . Q . . . .	Q . . . . . Q . . . . Q . Q . .	Q . . . . . Q . . . . Q . Q . .	Q . . . . . . . . . . Q . . . .	Q . . . . . . Q . . . Q . . . .	Q . . . . . . Q Q . . . . . Q .	Final solutions stored

Key Moments - 3 Insights

Why do we backtrack after placing a queen?

If no safe position is found in the next row (see steps 12-15), we remove the last placed queen to try other columns. This is shown in the execution_table rows where 'Backtrack' is Yes.

How do we know if a position is safe?

We check if no other queen attacks the position vertically, diagonally left, or diagonally right. The code only places a queen if isSafe returns true, as seen in steps 1, 4, 8, 10, 16, and 17.

Why do we place queens row by row?

Placing queens row by row simplifies checking conflicts because we only need to check previous rows. The variable 'row' increments after each successful placement, as tracked in variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the board state?

A Q . . .\n. . Q .\n. . . Q\n. . . .

B Q . . .\n. . Q .\n. . . .\n. . . .

C Q . . .\n. . . .\n. . . Q\n. . . .

D . . . .\n. . Q .\n. . . Q\n. . . .

💡 Hint

Check the 'Board State' column at step 8 in execution_table.

At which step does the first backtrack occur?

A Step 11

B Step 12

C Step 15

D Step 20

💡 Hint

Look for the first row where 'Backtrack' is 'Yes' in execution_table.

If we change N to 3, what would happen to the execution_table?

A It would place queens in all columns without backtracking.

B It would find a solution quickly.

C It would backtrack fully without finding a solution.

D It would stop after placing one queen.

💡 Hint

Recall that 3 queens cannot be placed safely on a 3x3 board; backtracking will exhaust all options.

Concept Snapshot

N Queens Problem:
- Place N queens on NxN board
- One queen per row
- Check safety (no attacks vertically, diagonally)
- Use backtracking to try columns
- Remove queen if stuck (backtrack)
- Stop when all queens placed

Full Transcript

The N Queens Problem places N queens on an NxN chessboard so that no two queens attack each other. We place queens row by row, checking if each position is safe. If no safe position is found in a row, we backtrack by removing the last placed queen and trying the next column. This process continues until all queens are placed or all options are exhausted. The execution table shows each step, the board state, and when backtracking happens. The variable tracker follows the row, column, and board changes. Key moments clarify why backtracking is needed, how safety is checked, and why row-wise placement simplifies the problem. The visual quiz tests understanding of board states, backtracking steps, and problem constraints.

Practice

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

easy

A. Place N queens on an NxN board in the same column

B. Place N queens on an NxN board so that all queens attack each other

C. Place N queens on an NxN board in the same row

D. Place N queens on an NxN board so that no two queens attack each other

Solution

1. Step 1: Understand the problem statement

   The N Queens Problem requires placing queens so that none can attack another, meaning no two queens share the same row, column, or diagonal.

2. Step 2: Analyze the options

   Place N queens on an NxN board so that no two queens attack each other correctly states the goal. Options B, C, and D contradict the problem's requirement by allowing attacks or placing queens in the same row or column.

3. Final Answer:

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

4. Quick Check:

   Goal = No two queens attack each other [OK]

Hint: Remember: Queens must not threaten each other on board [OK]

Common Mistakes:

• Thinking queens can share rows or columns
• Confusing attacking with protecting
• Ignoring diagonal attacks

2. Which of the following C++ function signatures is correct for a recursive function solving the N Queens Problem?

easy

A. void solveNQueens(vector<int> row, int positions)

B. bool solveNQueens(int row, vector<int>& positions)

C. int solveNQueens(int row, int positions[])

D. bool solveNQueens(int positions, vector<int> row)

Solution

1. Step 1: Identify correct parameter types for recursion

   The function should take the current row (int) and a reference to a vector holding queen positions to track placements.

2. Step 2: Check each option's signature

   bool solveNQueens(int row, vector<int>& positions) uses int and vector<int>& correctly. void solveNQueens(vector<int> row, int positions) swaps types incorrectly. int solveNQueens(int row, int positions[]) uses array but lacks reference semantics. bool solveNQueens(int positions, vector<int> row) swaps parameter order and types incorrectly.

3. Final Answer:

   bool solveNQueens(int row, vector<int>& positions) -> Option B

4. Quick Check:

   Correct signature uses int and vector reference [OK]

Hint: Recursive function needs current row and positions by reference [OK]

Common Mistakes:

• Passing vector by value causing performance issues
• Swapping parameter order
• Using wrong data types for parameters

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

void printBoard(const vector<int>& positions) {
  for (int row = 0; row < positions.size(); ++row) {
    for (int col = 0; col < positions.size(); ++col) {
      if (positions[row] == col) std::cout << "Q ";
      else std::cout << ". ";
    }
    std::cout << std::endl;
  }
}

int main() {
  vector<int> positions = {1, 3, 0, 2};
  printBoard(positions);
  return 0;
}

medium

A. . . Q .
Q . . .
. . . Q
. Q . .

B. Q . . .
. Q . .
. . Q .
. . . Q

C. . Q . .
. . . Q
Q . . .
. . Q .

D. . . . Q
Q . . .
. Q . .
. . Q .

Solution

1. Step 1: Understand positions vector meaning

   Each index is a row; value at index is the column where queen is placed. For positions = {1,3,0,2}, queens are at (0,1), (1,3), (2,0), (3,2).

2. Step 2: Visualize the board

   Row 0: Q at col 1 -> . Q . . Row 1: Q at col 3 -> . . . Q Row 2: Q at col 0 -> Q . . . Row 3: Q at col 2 -> . . Q .

3. Final Answer:

   . Q . . . . . Q Q . . . . . Q . -> Option C

4. Quick Check:

   Positions map to board rows and columns correctly [OK]

Hint: Positions vector index = row, value = queen column [OK]

Common Mistakes:

• Mixing row and column indices
• Printing Q in wrong columns
• Ignoring zero-based indexing

4. Identify the bug in this code snippet for checking if a queen can be placed safely:

bool isSafe(int row, int col, const vector<int>& positions) {
  for (int i = 0; i < row; ++i) {
    if (positions[i] == col || abs(positions[i] - col) == abs(i - row))
      return false;
  }
  return true;
}

medium

A. No bug; the function correctly checks safety

B. The diagonal check condition is incorrect

C. The loop should run until i <= row instead of i < row

D. The function does not check for column conflicts

Solution

1. Step 1: Analyze loop and conditions

   The loop checks all rows before current row. It returns false if any queen shares the same column or diagonal.

2. Step 2: Verify correctness of conditions

   positions[i] == col checks column conflict. abs(positions[i] - col) == abs(i - row) checks diagonal conflict correctly.

3. Final Answer:

   No bug; the function correctly checks safety -> Option A

4. Quick Check:

   Column and diagonal checks are correct [OK]

Hint: Check columns and diagonals with absolute difference [OK]

Common Mistakes:

• Loop running one step too far
• Incorrect diagonal condition
• Missing column conflict check

5. Given the N Queens Problem, which approach best improves performance for large N by reducing unnecessary checks?

hard

A. Use bitmasks to track columns and diagonals instead of arrays

B. Use nested loops to check every cell repeatedly

C. Store all board states in a list and check later

D. Place queens randomly and backtrack only if conflict

Solution

1. Step 1: Understand performance bottlenecks

   Checking columns and diagonals repeatedly slows down backtracking for large N.

2. Step 2: Evaluate optimization techniques

   Using bitmasks allows O(1) checks for columns and diagonals, reducing overhead significantly compared to arrays or repeated loops.

3. Step 3: Analyze other options

   Nested loops and storing all states increase time and memory. Random placement is inefficient and unreliable.

4. Final Answer:

   Use bitmasks to track columns and diagonals instead of arrays -> Option A

5. Quick Check:

   Bitmask optimization = faster checks [OK]

Hint: Bitmasks speed up column and diagonal checks [OK]

Common Mistakes:

• Using slow nested loops for checks
• Storing all states wastes memory
• Random placement lacks systematic pruning