N Queens Problem in DSA Typescript - 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 all rows placed

→Solution found

↓

Backtrack if no safe col

↓

Try next col in previous row

↓

Repeat until all solutions found or all options exhausted

The flow tries to place queens row by row, checking safety, placing if safe, moving to next row, or backtracking if no safe position.

Execution Sample

DSA Typescript

function solveNQueens(row) {
  if (row === N) {
    printBoard();
    return;
  }
  for (let col = 0; col < N; col++) {
    if (isSafe(row, col)) {
      placeQueen(row, col);
      solveNQueens(row + 1);
      removeQueen(row, col);
    }
  }
}

This code tries to place queens row by row, checking safety, placing, recursing, and backtracking.

Execution Table

Step	Operation	Row	Col	Action	Board State	Pointer Changes	Visual State
1	Try place queen	0	0	Check safe	Empty board	None	[. . . .] [. . . .] [. . . .] [. . . .]
2	Place queen	0	0	Place Q	Queen at (0,0)	queenPositions[0]=0	[Q . . .] [. . . .] [. . . .] [. . . .]
3	Try place queen	1	0	Check safe	Queen at (0,0)	None	[Q . . .] [. . . .] [. . . .] [. . . .]
4	Try place queen	1	1	Check safe	Queen at (0,0)	None	[Q . . .] [. . . .] [. . . .] [. . . .]
5	Place queen	1	1	Place Q	Queens at (0,0),(1,1)	queenPositions[1]=1	[Q . . .] [. Q . .] [. . . .] [. . . .]
6	Try place queen	2	0	Check safe	Queens at (0,0),(1,1)	None	[Q . . .] [. Q . .] [. . . .] [. . . .]
7	Try place queen	2	1	Check safe	Queens at (0,0),(1,1)	None	[Q . . .] [. Q . .] [. . . .] [. . . .]
8	Try place queen	2	2	Check safe	Queens at (0,0),(1,1)	None	[Q . . .] [. Q . .] [. . . .] [. . . .]
9	Place queen	2	2	Place Q	Queens at (0,0),(1,1),(2,2)	queenPositions[2]=2	[Q . . .] [. Q . .] [. . Q .] [. . . .]
10	Try place queen	3	0	Check safe	Queens at (0,0),(1,1),(2,2)	None	[Q . . .] [. Q . .] [. . Q .] [. . . .]
11	Try place queen	3	1	Check safe	Queens at (0,0),(1,1),(2,2)	None	[Q . . .] [. Q . .] [. . Q .] [. . . .]
12	Try place queen	3	2	Check safe	Queens at (0,0),(1,1),(2,2)	None	[Q . . .] [. Q . .] [. . Q .] [. . . .]
13	Try place queen	3	3	Check safe	Queens at (0,0),(1,1),(2,2)	None	[Q . . .] [. Q . .] [. . Q .] [. . . .]
14	Backtrack	3	3	Remove Q at (2,2)	Queens at (0,0),(1,1)	queenPositions[2]=-1	[Q . . .] [. Q . .] [. . . .] [. . . .]
15	Backtrack	2	2	Remove Q at (1,1)	Queen at (0,0)	queenPositions[1]=-1	[Q . . .] [. . . .] [. . . .] [. . . .]
16	Try place queen	1	2	Check safe	Queen at (0,0)	None	[Q . . .] [. . . .] [. . . .] [. . . .]
17	Place queen	1	2	Place Q	Queens at (0,0),(1,2)	queenPositions[1]=2	[Q . . .] [. . Q .] [. . . .] [. . . .]
18	Try place queen	2	0	Check safe	Queens at (0,0),(1,2)	None	[Q . . .] [. . Q .] [. . . .] [. . . .]
19	Place queen	2	0	Place Q	Queens at (0,0),(1,2),(2,0)	queenPositions[2]=0	[Q . . .] [. . Q .] [Q . . .] [. . . .]
20	Try place queen	3	0	Check safe	Queens at (0,0),(1,2),(2,0)	None	[Q . . .] [. . Q .] [Q . . .] [. . . .]
21	Try place queen	3	1	Check safe	Queens at (0,0),(1,2),(2,0)	None	[Q . . .] [. . Q .] [Q . . .] [. . . .]
22	Place queen	3	1	Place Q	Queens at (0,0),(1,2),(2,0),(3,1)	queenPositions[3]=1	[Q . . .] [. . Q .] [Q . . .] [. Q . .]
23	Solution found	-	-	All queens placed	Full board	queenPositions=[0,2,0,1]	[Q . . .] [. . Q .] [Q . . .] [. Q . .]

💡 All rows processed or backtracked fully, solutions found or no more options

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	After Step 14	After Step 17	After Step 19	After Step 22	Final
queenPositions	[-1,-1,-1,-1]	[0,-1,-1,-1]	[0,1,-1,-1]	[0,1,2,-1]	[0,1,-1,-1]	[0,2,-1,-1]	[0,2,0,-1]	[0,2,0,1]	[0,2,0,1]
row	0	1	1	2	2	1	2	3	4

Key Moments - 3 Insights

Why do we remove a queen after trying all columns in a row?

Because if no safe position is found in the next rows, we must backtrack and try a different position in the previous row. See steps 13-15 where queen at (2,2) is removed to try other options.

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 diagonal. This is done before placing a queen, as shown in steps 1, 3, 4, 6, etc., where 'Check safe' is performed.

Why does the algorithm stop when row equals N?

Because placing queens in all rows means a solution is found. Step 23 shows 'Solution found' when row 4 (N=4) is reached.

Visual Quiz - 3 Questions

Look at the execution table, what is the queenPositions array after step 5?

A [0,1,-1,-1]

B [0,0,-1,-1]

C [-1,-1,-1,-1]

D [1,1,-1,-1]

💡 Hint

Check the queenPositions variable in variable_tracker after step 5

At which step does the algorithm backtrack from placing queen at (2,2)?

A Step 17

B Step 9

C Step 14

D Step 22

💡 Hint

Look for 'Backtrack' and 'Remove Q at (2,2)' in execution_table rows

If we change N to 3, what will happen to the solution found step?

A It will occur earlier

B It will never occur

C It will occur at step 23

D It will occur multiple times

💡 Hint

N=3 has no solutions, so 'Solution found' step won't appear in execution_table

Concept Snapshot

N Queens Problem:
- Place N queens on NxN board
- No two queens attack each other
- Use backtracking: place queen row by row
- Check safety before placing
- Backtrack if stuck
- Find all solutions by exploring all options

Full Transcript

The N Queens Problem places N queens on an NxN chessboard so that no two queens attack 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 safe, it places the queen and moves to the next row. If no safe position is found in a row, it backtracks by removing the queen from the previous row and tries the next column. This continues until all queens are placed, which means a solution is found. The execution table shows step-by-step how queens are placed, checked, and removed, with the board state updated visually. The variable tracker shows how queen positions change 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 queen positions, backtracking steps, and solution existence for different board sizes.