N Queens Problem in DSA Javascript - Build from Scratch

N Queens Problem

📖 Scenario: You are helping a chess player place n queens on an n x n chessboard so that no two queens can attack each other. Queens can attack horizontally, vertically, and diagonally. Your task is to find one valid arrangement of queens on the board.

🎯 Goal: Build a program that finds one valid solution to the N Queens problem for a given n. The program will output the board state showing where queens are placed.

📋 What You'll Learn

Create a variable n to represent the size of the chessboard

Create a 2D array board of size n x n initialized with zeros

Write a function isSafe(row, col) to check if placing a queen at board[row][col] is safe

Write a recursive function solveNQueens(row) to place queens row by row

Print the final board with 1 representing a queen and 0 an empty cell

💡 Why This Matters

🌍 Real World

The N Queens problem is a classic example of constraint satisfaction problems used in artificial intelligence and puzzle solving.

💼 Career

Understanding backtracking algorithms and recursion is important for software engineers working on complex problem solving, optimization, and game development.

1

Create the chessboard

Create a variable called n and set it to 4. Then create a 2D array called board of size n x n filled with zeros.

DSA Javascript

const n = 4;
// Create a 2D array board of size n x n filled with zeros
// Your code here

Hint

Use Array.from with a mapping function to create a 2D array filled with zeros.

2

Write the safety check function

Write a function called isSafe(row, col) that returns true if placing a queen at board[row][col] is safe. Check the column above, the upper left diagonal, and the upper right diagonal for existing queens.

DSA Javascript

function isSafe(row, col) {
  // Check column above
  // Check upper left diagonal
  // Check upper right diagonal
  // Return true if safe, false otherwise
  // Your code here
}

Hint

Check vertically above, and diagonally upper left and upper right for queens.

3

Write the recursive solver function

Write a recursive function called solveNQueens(row) that tries to place a queen in each column of the given row. Use isSafe(row, col) to check safety. If safe, place the queen by setting board[row][col] = 1 and recurse for the next row. If no column works, backtrack by resetting board[row][col] = 0. Return true if all queens are placed, otherwise false.

DSA Javascript

function solveNQueens(row) {
  // If all rows are processed, return true
  // Loop through columns
  // Check if placing queen is safe
  // Place queen and recurse for next row
  // If recursion fails, backtrack
  // Return false if no placement possible
  // Your code here
}

Hint

Try placing queens row by row and backtrack if stuck.

4

Print the final board

Call solveNQueens(0) to start solving. Then print the board row by row, joining each row's elements with spaces.

DSA Javascript

solveNQueens(0);
// Print the board row by row
// Your code here

Hint

Use a loop to print each row joined by spaces.

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