N Queens Problem in DSA Typescript - Build from Scratch

N Queens Problem

📖 Scenario: You are helping a chess player place 8 queens on a chessboard so that no two queens can attack each other. Queens can move any number of squares vertically, horizontally, or diagonally. Your task is to find one valid arrangement of queens on the board.

🎯 Goal: Build a program that finds one valid way to place 8 queens on an 8x8 chessboard so that no two queens threaten each other. The program will print the board showing queen positions.

📋 What You'll Learn

Create an 8x8 board represented as a 2D array of numbers

Use a helper function to check if placing a queen is safe

Implement a recursive function to place queens row by row

Print the final board with queens marked as 1 and empty spaces as 0

💡 Why This Matters

🌍 Real World

The N Queens problem helps understand how to solve complex puzzles using backtracking, a technique useful in scheduling, resource allocation, and game AI.

💼 Career

Backtracking algorithms and recursive problem solving are common in software engineering roles, especially in algorithm design, optimization, and coding interviews.

1

Create the chessboard

Create a variable called board that is an 8x8 two-dimensional array filled with zeros. Each zero represents an empty square on the chessboard.

DSA Typescript

const board: number[][] = Array(8).fill(0).map(() => Array(8).fill(0));
// Your code here

Hint

Use Array(8).fill(0) to create an array of length 8, then map each element to another array of 8 zeros.

2

Write the safety check function

Write a function called isSafe that takes three parameters: board, row, and col. It should return true if placing a queen at board[row][col] is safe (no other queens attack it), otherwise false. Check the column, upper left diagonal, and upper right diagonal for existing queens.

DSA Typescript

const board: number[][] = Array(8).fill(0).map(() => Array(8).fill(0));

function isSafe(board: number[][], row: number, col: number): boolean {
    // Your code here
}

Hint

Check vertically above, and diagonally left and right above the current position for any queens (1s).

3

Implement the recursive queen placement

Write a function called solveNQueens that takes board and row as parameters. It should try to place a queen in each column of the current row if it is safe. If a queen is placed, recursively call solveNQueens for the next row. Return true if all queens are placed successfully, otherwise false. Use backtracking to remove queens if needed.

DSA Typescript

const board: number[][] = Array(8).fill(0).map(() => Array(8).fill(0));

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

function solveNQueens(board: number[][], row: number): boolean {
    // Your code here
}

Hint

Try placing a queen in each column of the current row. If safe, place it and move to next row. If stuck, remove the queen and try next column.

4

Print the final board

Call solveNQueens(board, 0) to start placing queens from the first row. Then print the board array to show the final arrangement. Each row should be printed as a space-separated string of 0s and 1s.

DSA Typescript

const board: number[][] = Array(8).fill(0).map(() => Array(8).fill(0));

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

function solveNQueens(board: number[][], row: number): boolean {
    if (row === 8) return true;
    for (let col = 0; col < 8; col++) {
        if (isSafe(board, row, col)) {
            board[row][col] = 1;
            if (solveNQueens(board, row + 1)) return true;
            board[row][col] = 0; // backtrack
        }
    }
    return false;
}

solveNQueens(board, 0);
for (let row = 0; row < 8; row++) {
    // Your code here
}

Hint

After solving, print each row of the board as a string of numbers separated by spaces.

Practice

1. What is the main goal of the N Queens Problem?

easy

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

B. Count the total number of queens on the board

C. Place queens only on the main diagonal of the board

D. Find the shortest path for a queen to move across the board

Solution

1. Step 1: Understand the problem statement

   The N Queens Problem asks to place N queens on an NxN chessboard so that no two queens threaten each other.

2. Step 2: Identify the correct goal

   This means no two queens share the same row, column, or diagonal.

3. Final Answer:

   Place N queens on an NxN chessboard so that no two queens attack each other -> Option A

4. Quick Check:

   Goal = Place queens safely [OK]

Hint: Remember queens must not attack each other on rows, columns, diagonals [OK]

Common Mistakes:

• Thinking queens can share rows or columns
• Confusing the problem with counting queens
• Ignoring diagonal attacks

2. Which of the following TypeScript function signatures correctly represents a recursive function to solve the N Queens Problem?

easy

A. function solveNQueens(): string

B. function solveNQueens(board: string): void

C. function solveNQueens(row: string, board: number[]): number

D. function solveNQueens(row: number, board: number[][]): boolean

Solution

1. Step 1: Identify correct parameter types for recursion

   The recursive function usually takes the current row (number) and the board state (2D array) to place queens step-by-step.

2. Step 2: Match function signature with recursion needs

   function solveNQueens(row: number, board: number[][]): boolean uses row: number and board: number[][], suitable for recursion and board tracking.

3. Final Answer:

   function solveNQueens(row: number, board: number[][]): boolean -> Option D

4. Quick Check:

   Recursive function needs row and board parameters [OK]

Hint: Recursive solve needs current row and board state parameters [OK]

Common Mistakes:

• Using wrong parameter types like string for row
• Missing board state parameter
• Wrong return type for recursion

3. What will be the output of the following TypeScript code snippet for N=4?

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

const board = [
  [0, 0, 0, 0],
  [1, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0]
];
console.log(isSafe(board, 1, 1));

medium

A. false

B. true

C. SyntaxError

D. undefined

Solution

1. Step 1: Check row left side for queen

   For row=1, col=1, check columns 0 to 0 in row 1. board[1][0] = 1, so return false.

2. Step 2: No need to check diagonals as left row check failed

   Since a queen is found on the left in the same row, position is unsafe.

3. Final Answer:

   false -> Option A

4. Quick Check:

   Left row check finds queen = false [OK]

Hint: Check left row first; queen found means unsafe [OK]

Common Mistakes:

• Ignoring left row check
• Confusing true/false return values
• Assuming diagonals checked first

4. Identify the bug in this TypeScript snippet for placing queens:

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

// isSafe function is correct

What is the bug?

medium

A. The base case should check if col > board.length

B. No bug; the code works correctly

C. The function does not backtrack correctly

D. The function does not check all rows in the current column

Solution

1. Step 1: Analyze base case correctness

   The base case col >= board.length correctly stops recursion when all columns are processed.

2. Step 2: Check backtracking and row iteration

   The loop tries all rows in the current column, places queen if safe, recurses, and backtracks if needed.

3. Final Answer:

   No bug; the code works correctly -> Option B

4. Quick Check:

   Backtracking and base case are correct [OK]

Hint: Check base case and backtracking carefully [OK]

Common Mistakes:

• Changing base case incorrectly
• Missing backtracking step
• Assuming incomplete row checks

5. Given a 5x5 chessboard, how many distinct solutions exist for the N Queens Problem? (Assuming solutions that differ by rotation or reflection are counted separately)

hard

A. 8

B. 12

C. 10

D. 2

Solution

1. Step 1: Recall known solution counts for N=5

   For a 5x5 board, the total number of distinct solutions is known to be 10 when counting all unique placements.

2. Step 2: Confirm counting method

   Since rotations and reflections are counted separately, the count remains 10.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   N=5 solutions = 10 [OK]

Hint: Memorize small N solution counts: N=4(2), N=5(10) [OK]

Common Mistakes:

• Confusing unique solutions with symmetrical counts
• Mixing counts for N=4 and N=5
• Assuming fewer solutions than actual