N Queens Problem in DSA Javascript - 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 queens placed

↓

If no safe place, backtrack

↓

Backtrack to previous row, try next col

↓

Continue until solution found or all options exhausted

We try to place queens row by row, checking safety. If no safe spot, we backtrack to try other columns.

Execution Sample

DSA Javascript

function solveNQueens(board, row) {
  if (row === board.length) return true;
  for (let col = 0; col < board.length; col++) {
    if (isSafe(board, row, col)) {
      board[row][col] = 'Q';
      if (solveNQueens(board, 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 Tried	Action	Board State (Q=queen, .=empty)
1	Start	-	-	Empty board	[['.', '.', '.'], ['.', '.', '.'], ['.', '.', '.']]
2	Try place queen	0	0	Safe, place Q	[['Q', '.', '.'], ['.', '.', '.'], ['.', '.', '.']]
3	Move to next row	1	-	Try columns	[['Q', '.', '.'], ['.', '.', '.'], ['.', '.', '.']]
4	Try place queen	1	0	Not safe, skip	[['Q', '.', '.'], ['.', '.', '.'], ['.', '.', '.']]
5	Try place queen	1	1	Not safe, skip	[['Q', '.', '.'], ['.', '.', '.'], ['.', '.', '.']]
6	Try place queen	1	2	Safe, place Q	[['Q', '.', '.'], ['.', '.', 'Q'], ['.', '.', '.']]
7	Move to next row	2	-	Try columns	[['Q', '.', '.'], ['.', '.', 'Q'], ['.', '.', '.']]
8	Try place queen	2	0	Not safe, skip	[['Q', '.', '.'], ['.', '.', 'Q'], ['.', '.', '.']]
9	Try place queen	2	1	Not safe, skip	[['Q', '.', '.'], ['.', '.', 'Q'], ['.', '.', '.']]
10	Try place queen	2	2	Not safe, skip	[['Q', '.', '.'], ['.', '.', 'Q'], ['.', '.', '.']]

💡 No safe column found for row 2, algorithm backtracks (undo Q at row 1 col 2 and try next option in row 1). For N=3, no solution exists.

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 9	Final
row	0	1	2	2	2
col	-	0	2	1	2
board	[['.', '.', '.'], ['.', '.', '.'], ['.', '.', '.']]	[['Q', '.', '.'], ['.', '.', '.'], ['.', '.', '.']]	[['Q', '.', '.'], ['.', '.', 'Q'], ['.', '.', '.']]	[['Q', '.', '.'], ['.', '.', 'Q'], ['.', '.', '.']]	[['Q', '.', '.'], ['.', '.', 'Q'], ['.', '.', '.']]

Key Moments - 3 Insights

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

Because placing a queen in the previous row's column led to no safe spots below, so we must try a different column in the previous row (see steps 8-10 where all columns in row 2 are unsafe, leading to backtrack).

How do we know if placing a queen is safe?

We check if no other queen is in the same column, or diagonals above the current row (refer to steps 4 and 5 where some columns are skipped as unsafe).

Why do we place queens row by row instead of randomly?

Placing queens row by row simplifies checking conflicts only in previous rows, reducing complexity (see the flow from step 2 to step 10).

Visual Quiz - 3 Questions

Look at the execution table, at which step is the first queen placed on the board?

A Step 2

B Step 4

C Step 6

D Step 9

💡 Hint

Check the 'Action' column for 'place Q' and the earliest step.

At which step does the algorithm skip to try a new column in row 2?

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

Look for 'Not safe, skip' in row 2 columns in the execution table.

If the board size was increased, how would the 'row' variable change in the variable tracker?

A It would stay the same

B It would decrease

C It would increase up to the new board size

D It would reset to zero

💡 Hint

The 'row' variable tracks which row we are placing a queen in, so it grows with board size.

Concept Snapshot

N Queens Problem:
- Place N queens on an N×N board
- No two queens share the same row, column, or diagonal
- Use backtracking: place queen row by row
- Check safety before placing
- Backtrack if stuck
- Stop when all queens placed

Full Transcript

The N Queens Problem places queens on a chessboard so none attack each other. We try placing queens row by row, checking if each position is safe by ensuring no other queen is in the same column or diagonal. If no safe spot is found in a row, we backtrack to the previous row to try a different column. This continues until all queens are placed or no solution exists. The example shows a 3x3 board where queens are placed step by step, skipping unsafe spots and backtracking when needed.

Practice

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

easy

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

B. Place N queens on an NxN board so 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 in the same column

Solution

1. Step 1: Understand the problem objective

   The N Queens Problem requires placing queens so that none can attack another. Queens attack horizontally, vertically, and diagonally.

2. Step 2: Analyze the options

   Only Place N queens on an NxN board so no two queens attack each other correctly states the goal: no two queens attack each other on an NxN board.

3. Final Answer:

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

4. Quick Check:

   Goal = safe queen placement [OK]

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

Common Mistakes:

• Thinking queens can share rows or columns
• Ignoring diagonal attacks
• Confusing attack with placement

2. Which of the following JavaScript function signatures is correct for solving the N Queens Problem recursively?

easy

A. function solveNQueens(board, row) {}

B. function solveNQueens(board, col) {}

C. function solveNQueens(row, col) {}

D. function solveNQueens(board) {}

Solution

1. Step 1: Understand recursive approach parameters

   Typically, the recursive function takes the board state and the current row to place a queen.

2. Step 2: Check options for correct parameters

   function solveNQueens(board, row) {} uses board and row, which fits the common recursive pattern.

3. Final Answer:

   function solveNQueens(board, row) {} -> Option A

4. Quick Check:

   Recursive function = board + current row [OK]

Hint: Pass board and current row for recursion [OK]

Common Mistakes:

• Using column instead of row for recursion
• Missing board parameter
• Using only one parameter

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

function isSafe(board, row, col) {
  for (let i = 0; i < row; i++) {
    if (board[i] === col || Math.abs(board[i] - col) === row - i) return false;
  }
  return true;
}

function solveNQueens(n) {
  const board = Array(n).fill(-1);
  const results = [];
  function backtrack(row) {
    if (row === n) {
      results.push(board.slice());
      return;
    }
    for (let col = 0; col < n; col++) {
      if (isSafe(board, row, col)) {
        board[row] = col;
        backtrack(row + 1);
        board[row] = -1;
      }
    }
  }
  backtrack(0);
  return results.length;
}

console.log(solveNQueens(4));

medium

A. 1

B. 4

C. 0

D. 2

Solution

1. Step 1: Understand the code logic

   The code uses backtracking to find all valid placements of 4 queens on a 4x4 board. It counts solutions by pushing valid boards to results.

2. Step 2: Recall known N Queens results

   For n=4, the number of valid solutions is 2, which matches the returned results length.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   4 Queens solutions = 2 [OK]

Hint: Remember 4 queens have exactly 2 solutions [OK]

Common Mistakes:

• Assuming 4 queens have more than 2 solutions
• Confusing board representation with count
• Misreading the backtracking logic

4. Identify the bug in this code snippet for checking if a queen placement is safe:

function isSafe(board, row, col) {
  for (let i = 0; i < row; i++) {
    if (board[i] === col || Math.abs(board[i] - col) === row + i) return false;
  }
  return true;
}

medium

A. The function should return true inside the loop

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

C. The diagonal check uses 'row + i' instead of 'row - i'

D. The equality check for columns is incorrect

Solution

1. Step 1: Analyze the diagonal attack condition

   The diagonal attack is checked by comparing absolute difference of columns to difference of rows. It should be row - i, not row + i.

2. Step 2: Identify the incorrect expression

   The code uses row + i, which is wrong and causes incorrect safety checks.

3. Final Answer:

   The diagonal check uses 'row + i' instead of 'row - i' -> Option C

4. Quick Check:

   Diagonal check = row - i [OK]

Hint: Diagonal difference = current row minus previous row [OK]

Common Mistakes:

• Using addition instead of subtraction for diagonal check
• Looping one extra iteration
• Returning true too early

5. Given a 5x5 board, how many distinct solutions does the N Queens Problem have, and what is the main reason for this number compared to smaller boards?

hard

A. 5 solutions because each queen must be in a unique row and column

B. 10 solutions because more rows allow more queen placements without conflict

C. 0 solutions because 5x5 boards cannot place 5 queens safely

D. 1 solution because only one arrangement avoids attacks on 5x5

Solution

1. Step 1: Recall known solution counts for N Queens

   For n=5, the known number of distinct solutions is 10.

2. Step 2: Understand why solution count increases

   With larger boards, more safe placements exist because queens can be spread out more easily without attacking each other.

3. Final Answer:

   10 solutions because more rows allow more queen placements without conflict -> Option B

4. Quick Check:

   5 Queens solutions = 10 [OK]

Hint: More board size means more safe queen arrangements [OK]

Common Mistakes:

• Assuming no solutions for 5x5
• Confusing unique rows with total solutions
• Underestimating solution count