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.

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 the board

C. Place queens only on the main diagonal of the board

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

Solution

1. Step 1: Understand the problem statement

   The N Queens Problem asks to place 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 A

4. Quick Check:

   Goal = Place queens safely [OK]

Hint: Remember queens must not attack each other on rows, columns, diagonals [OK]

Common Mistakes:

• Thinking queens can share rows or columns
• Confusing the problem with counting queens
• Ignoring diagonal attacks

2. Which of the following TypeScript function signatures correctly represents a recursive function to solve the N Queens Problem?

easy

A. function solveNQueens(): string

B. function solveNQueens(board: string): void

C. function solveNQueens(row: string, board: number[]): number

D. function solveNQueens(row: number, board: number[][]): boolean

Solution

1. Step 1: Identify correct parameter types for recursion

   The recursive function usually takes the current row (number) and the board state (2D array) to place queens step-by-step.

2. Step 2: Match function signature with recursion needs

   function solveNQueens(row: number, board: number[][]): boolean uses row: number and board: number[][], suitable for recursion and board tracking.

3. Final Answer:

   function solveNQueens(row: number, board: number[][]): boolean -> Option D

4. Quick Check:

   Recursive function needs row and board parameters [OK]

Hint: Recursive solve needs current row and board state parameters [OK]

Common Mistakes:

• Using wrong parameter types like string for row
• Missing board state parameter
• Wrong return type for recursion

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

function isSafe(board: number[][], row: number, col: number): boolean {
  for (let i = 0; i < col; i++) {
    if (board[row][i] === 1) return false;
  }
  for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
    if (board[i][j] === 1) return false;
  }
  for (let i = row, j = col; i < 4 && j >= 0; i++, j--) {
    if (board[i][j] === 1) return false;
  }
  return true;
}

const board = [
  [0, 0, 0, 0],
  [1, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0]
];
console.log(isSafe(board, 1, 1));

medium

A. false

B. true

C. SyntaxError

D. undefined

Solution

1. Step 1: Check row left side for queen

   For row=1, col=1, check columns 0 to 0 in row 1. board[1][0] = 1, so return false.

2. Step 2: No need to check diagonals as left row check failed

   Since a queen is found on the left in the same row, position is unsafe.

3. Final Answer:

   false -> Option A

4. Quick Check:

   Left row check finds queen = false [OK]

Hint: Check left row first; queen found means unsafe [OK]

Common Mistakes:

• Ignoring left row check
• Confusing true/false return values
• Assuming diagonals checked first

4. Identify the bug in this TypeScript snippet for placing queens:

function placeQueens(board: number[][], col: number): boolean {
  if (col >= board.length) return true;
  for (let i = 0; i < board.length; i++) {
    if (isSafe(board, i, col)) {
      board[i][col] = 1;
      if (placeQueens(board, col + 1)) return true;
      board[i][col] = 0;
    }
  }
  return false;
}

// isSafe function is correct

What is the bug?

medium

A. The base case should check if col > board.length

B. No bug; the code works correctly

C. The function does not backtrack correctly

D. The function does not check all rows in the current column

Solution

1. Step 1: Analyze base case correctness

   The base case col >= board.length correctly stops recursion when all columns are processed.

2. Step 2: Check backtracking and row iteration

   The loop tries all rows in the current column, places queen if safe, recurses, and backtracks if needed.

3. Final Answer:

   No bug; the code works correctly -> Option B

4. Quick Check:

   Backtracking and base case are correct [OK]

Hint: Check base case and backtracking carefully [OK]

Common Mistakes:

• Changing base case incorrectly
• Missing backtracking step
• Assuming incomplete row checks

5. Given a 5x5 chessboard, how many distinct solutions exist for the N Queens Problem? (Assuming solutions that differ by rotation or reflection are counted separately)

hard

A. 8

B. 12

C. 10

D. 2

Solution

1. Step 1: Recall known solution counts for N=5

   For a 5x5 board, the total number of distinct solutions is known to be 10 when counting all unique placements.

2. Step 2: Confirm counting method

   Since rotations and reflections are counted separately, the count remains 10.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   N=5 solutions = 10 [OK]

Hint: Memorize small N solution counts: N=4(2), N=5(10) [OK]

Common Mistakes:

• Confusing unique solutions with symmetrical counts
• Mixing counts for N=4 and N=5
• Assuming fewer solutions than actual