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

↓

Place queen

↓

Move to next row

↓

Repeat until all rows placed

↓

If no safe col, backtrack

↓

Backtrack to previous row

↓

Try next col in previous row

↓

Repeat until solution or all options exhausted

Try placing queens row by row, checking safety. If stuck, backtrack to try other columns.

Execution Sample

DSA C#

bool SolveNQueens(int row) {
  if (row == N) return true;
  for (int col = 0; col < N; col++) {
    if (IsSafe(row, col)) {
      PlaceQueen(row, col);
      if (SolveNQueens(row + 1)) return true;
      RemoveQueen(row, col);
    }
  }
  return false;
}

Recursively place queens row by row, backtracking when no safe position is found.

Execution Table

Step	Operation	Row	Column Tried	Action	Board State (Q=queen, .=empty)
1	Start	-	-	Empty board	.... .... .... ....
2	Try place queen	0	0	Safe, place queen	Q... .... .... ....
3	Try place queen	1	0	Not safe, try next col	Q... .... .... ....
4	Try place queen	1	1	Not safe, try next col	Q... .... .... ....
5	Try place queen	1	2	Safe, place queen	Q... ..Q. .... ....
6	Try place queen	2	0	Not safe, try next col	Q... ..Q. .... ....
7	Try place queen	2	1	Not safe, try next col	Q... ..Q. .... ....
8	Try place queen	2	2	Not safe, try next col	Q... ..Q. .... ....
9	Try place queen	2	3	Safe, place queen	Q... ..Q. ...Q ....
10	Try place queen	3	0	Not safe, try next col	Q... ..Q. ...Q ....
11	Try place queen	3	1	Not safe, try next col	Q... ..Q. ...Q ....
12	Try place queen	3	2	Not safe, try next col	Q... ..Q. ...Q ....
13	Try place queen	3	3	Not safe, no cols left, backtrack	Q... ..Q. ...Q ....
14	Backtrack	2	3	Remove queen, try next col	Q... ..Q. .... ....
15	Try place queen	2	3	Not safe, no cols left, backtrack	Q... ..Q. .... ....
16	Backtrack	1	2	Remove queen, try next col	Q... .... .... ....
17	Try place queen	1	3	Safe, place queen	Q... ...Q .... ....
18	Try place queen	2	0	Not safe, try next col	Q... ...Q .... ....
19	Try place queen	2	1	Safe, place queen	Q... ...Q .Q.. ....
20	Try place queen	3	0	Not safe, try next col	Q... ...Q .Q.. ....
21	Try place queen	3	1	Not safe, try next col	Q... ...Q .Q.. ....
22	Try place queen	3	2	Not safe, try next col	Q... ...Q .Q.. ....
23	Try place queen	3	3	Not safe, no cols left, backtrack	Q... ...Q .Q.. ....
24	Backtrack	2	1	Remove queen, try next col	Q... ...Q .... ....
25	Try place queen	2	2	Not safe, try next col	Q... ...Q .... ....
26	Try place queen	2	3	Not safe, no cols left, backtrack	Q... ...Q .... ....
27	Backtrack	1	3	Remove queen, try next col	Q... .... .... ....
28	Try place queen	1	3	Safe, place queen	Q... ...Q .... ....
29	Try place queen	2	0	Not safe, try next col	Q... ...Q .... ....
30	Try place queen	2	1	Not safe, try next col	Q... ...Q .... ....
31	Try place queen	2	2	Safe, place queen	Q... ...Q ..Q. ....
32	Try place queen	3	0	Not safe, try next col	Q... ...Q ..Q. ....
33	Try place queen	3	1	Not safe, try next col	Q... ...Q ..Q. ....
34	Try place queen	3	2	Not safe, try next col	Q... ...Q ..Q. ....
35	Try place queen	3	3	Safe, place queen	Q... ...Q ..Q. ...Q
36	All queens placed	-	-	Solution found	Q... ...Q ..Q. ...Q

💡 All rows placed safely, solution found at step 36

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 8	After Step 13	After Step 16	After Step 17	After Step 19	After Step 23	After Step 26	After Step 31	Final
row	0	1	2	2	3	1	2	2	1	1	2	4 (done)
col tried	-	0	2	2	3	3	3	1	3	3	2	-
board queens count	0	1	2	2	3	1	2	2	1	1	3	4

Key Moments - 3 Insights

Why do we backtrack when no safe column is found in a row?

Because placing a queen in the current row is impossible without conflicts, so we remove the queen from the previous row and try a different column there. See steps 13 and 14 in execution_table.

How do we know if a position is safe to place a queen?

We check if no other queen is in the same column, or diagonals above the current row. This is why some columns are skipped in steps 3,4,6,7 etc.

Why does the recursion stop when row == N?

Because it means queens have been placed safely in all rows, so a solution is found. This is shown at step 36.

Visual Quiz - 3 Questions

Look at the execution_table, at which step is the first queen placed in row 2?

A Step 19

B Step 8

C Step 5

D Step 14

💡 Hint

Check the 'Row' and 'Action' columns in execution_table rows 5 to 30.

At which step does the algorithm backtrack for the first time?

A Step 9

B Step 20

C Step 13

D Step 21

💡 Hint

Look for 'backtrack' in the 'Action' column in execution_table.

According to variable_tracker, what is the value of 'row' after step 20?

A 3

B 1

C 2

D 4

💡 Hint

Check the 'row' values in variable_tracker for 'After Step 19' or closest step.

Concept Snapshot

N Queens Problem:
- Place N queens on NxN board so no two attack each other.
- Place queens row by row, checking columns and diagonals.
- Use backtracking to try different positions when stuck.
- Recursion stops when all rows have queens safely placed.
- Board state updated by placing/removing queens during search.

Full Transcript

The N Queens Problem involves placing N queens on an NxN chessboard so that no two queens threaten each other. The algorithm tries to place a queen in each row, checking if the position is safe by ensuring no other queen is in the same column or diagonal. If a safe position is found, it places the queen and moves to the next row. If no safe position exists in a row, it backtracks by removing the queen from the previous row and tries the next column there. This process continues recursively until all queens are placed safely or all options are exhausted. The execution table shows step-by-step queen placements, checks, and backtracks, while the variable tracker monitors the current row, column tried, and number of queens on the board. Key moments clarify why backtracking is needed, how safety is checked, and when the recursion ends. The visual quiz tests understanding of queen placements, backtracking steps, and variable states. This approach helps visualize the recursive backtracking method to solve the N Queens Problem.

Practice

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

easy

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

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

C. Place N queens on an NxN board in a single row

D. Place N queens on an NxN board in a single column

Solution

1. Step 1: Understand the problem statement

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

2. Step 2: Identify the correct goal

   This means no two queens share the same row, column, or diagonal.

3. Final Answer:

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

4. Quick Check:

   Goal = No two queens attack each other [OK]

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

Common Mistakes:

• Thinking queens can share rows or columns
• Ignoring diagonal attacks
• Confusing with placing queens in one line

2. Which of the following C# code snippets correctly declares a 2D array to represent an 8x8 chessboard for the N Queens Problem?

easy

A. int[,] board = new int[8,8];

B. int[][] board = new int[8];

C. int board[8][8];

D. int board = new int[8,8];

Solution

1. Step 1: Identify correct 2D array declaration in C#

   In C#, a 2D array is declared as int[,] board = new int[8,8];.

2. Step 2: Check other options for syntax errors

   int[][] board = new int[8]; declares a jagged array but misses initialization of inner arrays. int board[8][8]; is invalid syntax in C#. int board = new int[8,8]; tries to assign an array to an int variable.

3. Final Answer:

   int[,] board = new int[8,8]; -> Option A

4. Quick Check:

   Correct 2D array syntax = int[,] board = new int[8,8]; [OK]

Hint: Use int[,] for 2D arrays in C# [OK]

Common Mistakes:

• Using jagged arrays without initializing inner arrays
• Using C++ style array declarations
• Assigning arrays to single int variables

3. Consider the following C# code snippet for checking if a queen can be placed at row 1, column 2 on a 4x4 board:

bool IsSafe(int[,] board, int row, int col) {
    for (int i = 0; i < col; i++) {
        if (board[row, i] == 1) return false;
    }
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i, j] == 1) return false;
    }
    for (int i = row, j = col; i < 4 && j >= 0; i++, j--) {
        if (board[i, j] == 1) return false;
    }
    return true;
}

int[,] board = new int[4,4];
board[0, 1] = 1;
bool result = IsSafe(board, 1, 2);
Console.WriteLine(result);

What will be the output?

medium

A. true

B. Compile-time error

C. false

D. Runtime exception

Solution

1. Step 1: Analyze the board state and IsSafe checks

   The board has a queen at (0,1). We check if placing at (1,2) is safe. The function checks left row, upper-left diagonal, and lower-left diagonal.

2. Step 2: Check conflicts for position (1,2)

   Left row check: no queen at (1,0) or (1,1). Upper-left diagonal: (0,1) has a queen, so returns false.

3. Final Answer:

   false -> Option C

4. Quick Check:

   Queen at (0,1) blocks (1,2) = false [OK]

Hint: Check diagonals carefully for conflicts [OK]

Common Mistakes:

• Ignoring diagonal checks
• Assuming no conflict if row is clear
• Misreading array indices

4. The following C# code attempts to solve the N Queens Problem but has a bug. What is the bug?

bool SolveNQueens(int[,] board, int col) {
    if (col >= board.GetLength(0)) return true;
    for (int i = 0; i < board.GetLength(0); i++) {
        if (IsSafe(board, i, col)) {
            board[i, col] = 1;
            if (SolveNQueens(board, col + 1)) return true;
            board[i, col] = 0;
        }
    }
    return false;
}

// IsSafe method is correct

medium

A. The function does not backtrack properly

B. No bug; code works correctly

C. The board array is not initialized

D. The base case should check row instead of column

Solution

1. Step 1: Review the recursive backtracking logic

   The function tries to place a queen in each row of the current column, checks safety, places queen, and recurses to next column.

2. Step 2: Verify base case and backtracking

   Base case returns true when all columns are processed. Backtracking resets board[i, col] to 0 if recursion fails. This is correct.

3. Final Answer:

   No bug; code works correctly -> Option B

4. Quick Check:

   Backtracking logic and base case are correct [OK]

Hint: Check base case and backtracking steps carefully [OK]

Common Mistakes:

• Confusing row and column in base case
• Forgetting to reset board on backtrack
• Assuming uninitialized board causes error

5. You want to modify the N Queens solver to count all possible solutions for N=4 instead of stopping at the first. Which change should you make to the recursive method?

hard

A. Add a global boolean flag to stop after first solution

B. Remove the IsSafe check to speed up counting

C. Change the board size to 5x5

D. Replace the return type with int and sum all recursive calls instead of returning on first true

Solution

1. Step 1: Understand current behavior

   The current solver returns true on finding the first solution, stopping further search.

2. Step 2: Modify to count all solutions

   Change return type to int, accumulate counts from recursive calls, and do not return early. This counts all valid placements.

3. Final Answer:

   Replace the return type with int and sum all recursive calls instead of returning on first true -> Option D

4. Quick Check:

   Counting solutions = sum recursive counts [OK]

Hint: Sum all recursive results to count solutions [OK]

Common Mistakes:

• Stopping at first solution
• Changing board size unnecessarily
• Removing safety checks causing wrong counts