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 placement

↓

If no safe col in row

→Backtrack to previous row

↓

If all rows placed

→Solution found

↓

End or find more solutions

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

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;
}

This code tries to 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	Try place queen	0	0	Safe, place queen	Q . . . . . . . . . . . . . . .
2	Try place queen	1	0	Not safe, try next	Q . . . . . . . . . . . . . . .
3	Try place queen	1	1	Not safe, try next	Q . . . . . . . . . . . . . . .
4	Try place queen	1	2	Safe, place queen	Q . . . . . Q . . . . . . . . .
5	Try place queen	2	0	Not safe, try next	Q . . . . . Q . . . . . . . . .
6	Try place queen	2	1	Not safe, try next	Q . . . . . Q . . . . . . . . .
7	Try place queen	2	3	Safe, place queen	Q . . . . . Q . . . . Q . . . .
8	Try place queen	3	0	Not safe, try next	Q . . . . . Q . . . . Q . . . .
9	Try place queen	3	1	Safe, place queen	Q . . . . . Q . . . . Q . Q . .
10	All queens placed	N/A	N/A	Solution found	Q . . . . . Q . . . . Q . Q . .
11	Backtrack	3	1	Remove queen	Q . . . . . Q . . . . Q . . . .
12	Try next col	3	2	Not safe, try next	Q . . . . . Q . . . . Q . . . .
13	Try next col	3	3	Not safe, backtrack	Q . . . . . Q . . . . Q . . . .
14	Backtrack	2	3	Remove queen	Q . . . . . Q . . . . . . . . .
15	Try next col	2	4	No column 4, backtrack	Q . . . . . Q . . . . . . . . .
16	Backtrack	1	2	Remove queen	Q . . . . . . . . . . . . . . .
17	Try next col	1	3	Safe, place queen	Q . . . . . . Q . . . . . . . .
18	Try place queen	2	0	Not safe, try next	Q . . . . . . Q . . . . . . . .
19	Try place queen	2	1	Safe, place queen	Q . . . . . . Q . Q . . . . . .
20	Try place queen	3	0	Not safe, try next	Q . . . . . . Q . Q . . . . . .
21	Try place queen	3	1	Not safe, try next	Q . . . . . . Q . Q . . . . . .
22	Try place queen	3	2	Not safe, try next	Q . . . . . . Q . Q . . . . . .
23	Try place queen	3	3	Not safe, backtrack	Q . . . . . . Q . Q . . . . . .
24	Backtrack	2	1	Remove queen	Q . . . . . . Q . . . . . . . .
25	Try next col	2	2	Not safe, try next	Q . . . . . . Q . . . . . . . .
26	Try next col	2	3	Not safe, backtrack	Q . . . . . . Q . . . . . . . .
27	Backtrack	1	3	Remove queen	Q . . . . . . . . . . . . . . .
28	Try next col	1	4	No column 4, backtrack	Q . . . . . . . . . . . . . . .
29	Backtrack	0	0	Remove queen	. . . . . . . . . . . . . . . .
30	Try next col	0	1	Safe, place queen	. Q . . . . . . . . . . . . . .
31	Continue similarly	N/A	N/A	Continue placing queens	Partial board states...
32	Eventually	N/A	N/A	Find all solutions or stop	Final board states
33	End	N/A	N/A	No more columns to try	Final or no solution

💡 All rows processed with safe queen placements or all options exhausted with backtracking

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 7	After Step 10	After Step 29	After Step 30	Final
row	0	1	2	3	N (4)	0	1	N or backtracked
col	0	0	3	3	1	0	1	varies
board	[empty]	Q . . . . . . . . . . . . . . .	Q . . . . . Q . . . . . . . . .	Q . . . . . Q . . . . Q . . . .	Q . . . . . Q . . . . Q . Q . .	. . . . . . . . . . . . . . . .	. Q . . . . . . . . . . . . . .	varies with placement

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-15 and 25-27 in execution_table).

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

We check columns, and diagonals for existing queens before placing (implied in 'Safe' or 'Not safe' in execution_table rows like 2, 4, 5).

Why does the algorithm stop when row == N?

Because all N queens have been placed safely on the board, meaning a solution is found (see step 10).

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

Refer to the 'Board State' column at step 10 in execution_table.

At which step does the algorithm first backtrack by removing a queen?

A Step 11

B Step 10

C Step 5

D Step 1

💡 Hint

Look for 'Remove queen' action in execution_table.

If the board size N is increased, how would the variable 'row' change in variable_tracker?

A It would decrease

B It would go up to N instead of 4

C It would stay the same

D It would become negative

💡 Hint

The 'row' variable tracks current row; it goes from 0 to N (see variable_tracker).

Concept Snapshot

N Queens Problem:
- Place N queens on NxN board
- One queen per row, no two queens attack
- Use backtracking: place queen, check safety
- If stuck, remove last queen and try next column
- Stop when all queens placed safely

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 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 continues until all queens are placed or all options are exhausted. The execution table shows step-by-step queen placements, safety checks, backtracking, and board states. The variable tracker monitors the current row, column tried, and board configuration after each step. Key moments clarify why backtracking is needed, how safety is checked, and when the algorithm stops. The visual quiz tests understanding of board states, backtracking steps, and variable changes. The snapshot summarizes the problem and backtracking approach in simple terms.

Practice

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

easy

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

B. Find the shortest path for a queen to move across the board

C. Count the total number of queens on the board

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

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 chessboard so that no two queens attack each other -> Option D

4. Quick Check:

   Goal = Place queens safely [OK]

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

Common Mistakes:

• Thinking queens can attack each other
• Confusing the problem with counting queens
• Ignoring diagonal attacks

2. Which of the following is the correct way to declare a 2D array for the chessboard in C for the N Queens Problem with size N?

easy

A. int board[];

B. int board[N][N];

C. int board[N];

D. int board(N,N);

Solution

1. Step 1: Recall C syntax for 2D arrays

   In C, a 2D array is declared as type name[size1][size2]; where both sizes are specified.

2. Step 2: Match the correct declaration

   int board[N][N]; uses int board[N][N]; which correctly declares a 2D array for the chessboard.

3. Final Answer:

   int board[N][N]; -> Option B

4. Quick Check:

   2D array syntax = int board[N][N]; [OK]

Hint: Use int board[N][N] for 2D arrays in C [OK]

Common Mistakes:

• Using 1D array for 2D board
• Incorrect syntax like int board(N,N);
• Not specifying both dimensions

3. What will be the output of the following code snippet for N=4 when printing the board after placing queens at positions (0,1), (1,3), (2,0), (3,2)?

int board[4][4] = {0};
board[0][1] = 1;
board[1][3] = 1;
board[2][0] = 1;
board[3][2] = 1;
for(int i=0; i<4; i++) {
  for(int j=0; j<4; j++) {
    printf("%d ", board[i][j]);
  }
  printf("\n");
}

medium

A. 0 0 1 0
1 0 0 0
0 1 0 0
0 0 0 1

B. 1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

C. 0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

D. 0 0 0 1
0 0 1 0
1 0 0 0
0 1 0 0

Solution

1. Step 1: Place queens on the board as per given positions

   Set board[0][1], board[1][3], board[2][0], board[3][2] to 1; others remain 0.

2. Step 2: Print the board row-wise

   Row 0: 0 1 0 0 Row 1: 0 0 0 1 Row 2: 1 0 0 0 Row 3: 0 0 1 0

3. Final Answer:

   0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 -> Option C

4. Quick Check:

   Positions match output [OK]

Hint: Map queen positions to 1s in 2D array [OK]

Common Mistakes:

• Mixing row and column indices
• Printing without spaces or newlines
• Incorrect initialization of board

4. Identify the error in this C function snippet for checking if a queen can be placed at board[row][col]:

int isSafe(int board[][N], int row, int col) {
  for(int i=0; i=0 && j>=0; i--, j--) {
    if(board[i][j] == 1) return 0;
  }
  for(int i=row, j=col; i>=0 && j

medium

A. The function assumes N is a global constant but it may not be

B. The function incorrectly checks columns beyond the current row

C. The function misses checking the lower diagonals

D. The function does not check the current row for queens

Solution

1. Step 1: Analyze the use of N in function parameter

   The function uses int board[][N] but N is not passed as a parameter or defined locally.

2. Step 2: Understand C array parameter rules

   In C, array sizes must be known or passed explicitly; assuming N as global can cause errors if not defined.

3. Final Answer:

   The function assumes N is a global constant but it may not be -> Option A

4. Quick Check:

   Array size N must be known [OK]

Hint: Always pass array size explicitly or define globally [OK]

Common Mistakes:

• Ignoring array size requirements in C
• Assuming N is always global
• Missing checks for diagonals

5. Given the backtracking approach to solve the N Queens Problem, which of the following best describes the role of recursion in the solution?

hard

A. Recursion tries to place queens row by row and backtracks when no safe position is found

B. Recursion counts the total number of queens placed on the board

C. Recursion moves queens randomly until all are placed

D. Recursion only checks if the board is full without placing queens

Solution

1. Step 1: Understand backtracking in N Queens

   Backtracking uses recursion to place queens one row at a time, checking safety.

2. Step 2: Identify recursion behavior

   If no safe position is found in a row, recursion backtracks to previous row to try other positions.

3. Final Answer:

   Recursion tries to place queens row by row and backtracks when no safe position is found -> Option A

4. Quick Check:

   Backtracking = recursive trial and error [OK]

Hint: Think recursion as trial and error with backtracking [OK]

Common Mistakes:

• Thinking recursion places queens randomly
• Confusing recursion with counting
• Ignoring backtracking step