N Queens Problem in DSA Javascript

Mental Model

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

Analogy: Imagine placing N friends at a round table where no two friends can sit directly opposite or next to each other.

Board 4x4 empty:
. . . .
. . . .
. . . .
. . . .

Dry Run Walkthrough

Input: board size: 4

Goal: Place 4 queens on a 4x4 board so none attack each other

Step 1: Place queen at row 0, column 1

. Q . .
. . . .
. . . .
. . . .

Why: Start placing first queen in first row

Step 2: Try to place queen at row 1, column 3

. Q . .
. . . Q
. . . .
. . . .

Why: Place second queen where it is safe from first queen

Step 3: Try to place queen at row 2, column 0 fails, try column 2 succeeds

. Q . .
. . . Q
. . Q .
. . . .

Why: Find safe spot for third queen avoiding attacks

Step 4: Place queen at row 3, column 0 fails, column 1 fails, column 2 fails, column 3 fails; backtrack

. Q . .
. . . Q
. . Q .
. . . .

Why: No safe place in last row, must backtrack

Step 5: Remove queen from row 2, column 2; try row 2, column 0

. Q . .
. . . Q
Q . . .
. . . .

Why: Backtrack and try next possible position

Step 6: Place queen at row 3, column 2

. Q . .
. . . Q
Q . . .
. . Q .

Why: Found safe place for last queen

Result:

Final board:
. Q . .
. . . Q
Q . . .
. . Q .

Annotated Code

DSA Javascript

class NQueens {
  constructor(n) {
    this.n = n;
    this.board = Array.from({ length: n }, () => Array(n).fill('.'));
    this.solutions = [];
  }

  isSafe(row, col) {
    for (let i = 0; i < row; i++) {
      if (this.board[i][col] === 'Q') return false; // same column
    }
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (this.board[i][j] === 'Q') return false; // upper left diagonal
    }
    for (let i = row - 1, j = col + 1; i >= 0 && j < this.n; i--, j++) {
      if (this.board[i][j] === 'Q') return false; // upper right diagonal
    }
    return true;
  }

  solve(row = 0) {
    if (row === this.n) {
      this.solutions.push(this.board.map(r => r.join(' ')).join('\n'));
      return;
    }
    for (let col = 0; col < this.n; col++) {
      if (this.isSafe(row, col)) {
        this.board[row][col] = 'Q'; // place queen
        this.solve(row + 1); // move to next row
        this.board[row][col] = '.'; // backtrack
      }
    }
  }
}

const nQueens = new NQueens(4);
nQueens.solve();
console.log('Number of solutions:', nQueens.solutions.length);
console.log('One solution:\n' + nQueens.solutions[0]);

for (let i = 0; i < row; i++) { if (this.board[i][col] === 'Q') return false; }

check column above for queen to avoid vertical attack

for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (this.board[i][j] === 'Q') return false; }

check upper left diagonal for queen to avoid diagonal attack

for (let i = row - 1, j = col + 1; i >= 0 && j < this.n; i--, j++) { if (this.board[i][j] === 'Q') return false; }

check upper right diagonal for queen to avoid diagonal attack

if (this.isSafe(row, col)) { this.board[row][col] = 'Q'; this.solve(row + 1); this.board[row][col] = '.'; }

place queen if safe, recurse to next row, then backtrack

if (row === this.n) { this.solutions.push(this.board.map(r => r.join(' ')).join('\n')); return; }

all queens placed, save solution

Output

Number of solutions: 2

One solution:

. Q . .

. . . Q

Q . . .

. . Q .

Complexity Analysis

Time: O(N!) because each row tries all columns and backtracks on conflicts

Space: O(N^2) for the board storage and recursion stack up to N levels

vs Alternative: Brute force tries all board configurations (O(2^(N^2))) which is much slower

Edge Cases

N = 1

One queen placed on single cell, one solution

DSA Javascript

if (row === this.n) { this.solutions.push(this.board.map(r => r.join(' ')).join('\n')); return; }

N = 2 or N = 3

No solutions found, code returns zero solutions

DSA Javascript

if (row === this.n) { this.solutions.push(this.board.map(r => r.join(' ')).join('\n')); return; }

When to Use This Pattern

When asked to place items on a grid with constraints that no two threaten each other, use backtracking to try positions row by row and backtrack on conflicts.

Common Mistakes

Mistake: Not checking all three directions (column and both diagonals) for queen attacks
Fix: Add checks for column, upper left diagonal, and upper right diagonal before placing queen

Mistake: Not backtracking after recursive call, leaving queens placed incorrectly
Fix: Reset the board cell to empty after recursive call to explore other options

Summary

It finds all ways to place N queens on an NxN board so none attack each other.

Use it when you need to arrange items with mutual exclusion constraints on a grid.

The key is to place queens row by row, checking safety, and backtracking when stuck.

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