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

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

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

  function isSafe(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 < n && j >= 0; i++, j--) {
      if (board[i][j] === 1) return false;
    }
    return true;
  }

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

  if (solve(0)) return board;
  return null;
}

const solution = solveNQueens(4);
if (solution) {
  console.log(printBoard(solution));
} else {
  console.log('No 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 where no two queens attack each other on a 4x4 board.

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 the N Queens problem when N = 1?

A 0

B 4

C 2

D 1

💡 Hint

With only one queen and one cell, can it be placed without conflict?

With a 1x1 board, placing the single queen is trivially valid, so there is exactly 1 solution.

🔧 Debug

advanced

Identify the error in the isSafe function

What error will occur when running this isSafe function for N Queens?

DSA Typescript

function isSafe(row: number, col: number, board: 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 < board.length && j >= 0; i++, j--) {
    if (board[i][j] === 1) return false;
  }
  return true;
}

// Called with board = [[0,0],[0,0]] and row=2, col=1

A IndexError: index out of range

B Returns false incorrectly

C Returns true incorrectly

D No error, works correctly

💡 Hint

Check the loop conditions and array indexing carefully.

The function accesses board[i][j] where i can be equal to board.length (2) causing an index out of range error.

🚀 Application

advanced

Count solutions for 5 queens

How many distinct solutions exist for the N Queens problem when N = 5?

A 5

B 8

C 10

D 12

💡 Hint

Try to recall or compute the number of solutions for 5 queens using backtracking.

The known number of distinct solutions for 5 queens is 10, so option C is correct.

❓ Predict Output

expert

Output of partial board after placing 3 queens on 5x5 board

Given the following partial board after placing 3 queens on a 5x5 board, what is the printed output?

DSA Typescript

const board = [
  [0, 1, 0, 0, 0],
  [0, 0, 0, 1, 0],
  [1, 0, 0, 0, 0],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0]
];

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

console.log(printBoard(board));

A

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

B

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

C

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

D

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

💡 Hint

Look carefully at the positions of 1s in the board array and translate them to Qs.

The board has queens at positions (0,1), (1,3), and (2,0). This matches option A.