N Queens Problem in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the N Queens Problem?

To place N queens on an N×N chessboard so that no two queens attack each other. This means no two queens share the same row, column, or diagonal.

beginner

Which data structure is commonly used to represent the chessboard in the N Queens Problem?

A 2D array or matrix of size N×N, where each cell can be marked to show if a queen is placed or not.

intermediate

How do we check if placing a queen at a position is safe in the N Queens Problem?

We check three directions: the same column above, the upper left diagonal, and the upper right diagonal for any existing queens.

intermediate

What algorithmic technique is mainly used to solve the N Queens Problem?

Backtracking, which tries placing queens row by row and backtracks when a conflict is found.

intermediate

Why is backtracking suitable for the N Queens Problem?

Because it systematically explores all possible placements and abandons paths that lead to conflicts early, saving time.

In the N Queens Problem, what does a 'safe' position mean?

A No other queen is in the same diagonal only

B No other queen is in the same row only

C No other queen is in the same row, column, or diagonal

D No other queen is in the same column only

A safe position means no queen attacks the new queen horizontally, vertically, or diagonally.

Which technique is used to solve the N Queens Problem efficiently?

A Backtracking

B Dynamic Programming

C Sorting

D Greedy Algorithm

Backtracking tries placing queens step-by-step and removes them if conflicts arise.

How many queens do you place on the board in the N Queens Problem?

A N/2 queens

B N queens

C 2N queens

D N squared queens

The problem requires placing exactly N queens on an N×N board.

Which of these is NOT checked when placing a queen safely?

A Same row

B Same column

C Same diagonal

D Same color square

The color of the square is irrelevant; only rows, columns, and diagonals matter.

What happens when backtracking finds a conflict in the N Queens Problem?

A It removes the last placed queen and tries a new position

B It stops the entire process

C It places another queen anyway

D It restarts from the first row

Backtracking removes the last queen and tries a different position to find a solution.

Explain how backtracking helps solve the N Queens Problem step-by-step.

Think about trying and undoing queen placements.

Describe how to check if a queen can be safely placed on the board.

Focus on directions where queens can attack.

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