N Queens Problem in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of placing queens on a 4x4 board

What is the printed board state after placing queens in the first valid solution for 4 queens?

DSA Javascript

function printBoard(board) {
  return board.map(row => row.map(cell => cell ? 'Q' : '.').join(' ')).join('\n');
}

function solveNQueens(n) {
  const board = Array.from({ length: n }, () => Array(n).fill(0));
  const solutions = [];

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

  function backtrack(row) {
    if (row === n) {
      solutions.push(board.map(r => r.slice()));
      return true;
    }
    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        board[row][col] = 1;
        if (backtrack(row + 1)) return true;
        board[row][col] = 0;
      }
    }
    return false;
  }

  backtrack(0);
  return solutions[0];
}

const solution = solveNQueens(4);
console.log(printBoard(solution));

A

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

B

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

C

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

D

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

💡 Hint

Think about the first valid arrangement of queens on a 4x4 board where no two queens attack each other.

The first valid solution for 4 queens places queens at positions (0,1), (1,3), (2,0), and (3,2). This corresponds to option B.

🧠 Conceptual

intermediate

Number of solutions for 1 queen

How many distinct solutions exist for placing 1 queen on a 1x1 chessboard?

A 1

B 0

C 2

D 4

💡 Hint

With only one cell, placing one queen is straightforward.

There is exactly one way to place one queen on a 1x1 board.

🔧 Debug

advanced

Identify the error in the N Queens safety check

What error does this code produce when checking if a queen can be placed safely? function isSafe(board, row, col) { for (let i = 0; i <= row; i++) { if (board[i][col]) return false; } for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j]) return false; } for (let i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) { if (board[i][j]) return false; } return true; } const board = [[0,0],[0,0]]; console.log(isSafe(board, 2, 1));

A TypeError: Cannot read property '1' of undefined

B Returns false incorrectly

C SyntaxError: Unexpected token

D Returns true incorrectly

💡 Hint

Check the indices used when accessing the board array.

The code tries to access board[2][1] but board has only 2 rows (indices 0 and 1), causing an undefined access and TypeError.

🚀 Application

advanced

Count solutions for 5 queens

How many distinct solutions exist for placing 5 queens on a 5x5 chessboard so that no two queens attack each other?

A 5

B 12

C 10

D 8

💡 Hint

The number of solutions for 5 queens is a known classic result.

There are exactly 10 distinct solutions for the 5-queens problem.

❓ Predict Output

expert

Output of partial board after placing 3 queens on 5x5

Given the following code placing queens on a 5x5 board, what is the printed board state after placing queens at (0,0), (1,2), and (2,4)? Print 'Q' for queen and '.' for empty cell.

DSA Javascript

const board = Array.from({ length: 5 }, () => Array(5).fill('.'));
board[0][0] = 'Q';
board[1][2] = 'Q';
board[2][4] = 'Q';

for (let row = 0; row < 5; row++) {
  console.log(board[row].join(' '));
}

A

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

B

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

C

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

D

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

💡 Hint

Check the exact positions where queens are placed.

Queens are placed at (0,0), (1,2), and (2,4), so only those cells have 'Q'.

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