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

How do we check if a queen placement is safe in the N Queens Problem?

We check three conditions: no other queen is in the same column, no other queen is in the same major diagonal, and no other queen is in the same minor diagonal.

intermediate

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

Backtracking is used. It tries placing queens row by row and backtracks when a conflict is found, exploring all possible safe placements.

intermediate

Why is backtracking efficient for the N Queens Problem compared to brute force?

Backtracking stops exploring a path as soon as it finds a conflict, avoiding unnecessary checks of invalid board states, unlike brute force which tries all combinations.

beginner

What is the output format when printing a solution to the N Queens Problem?

A visual board showing positions of queens, often with 'Q' for queen and '.' for empty spaces, or a list of queen positions per row.

What does the N Queens Problem require you to avoid?

A Queens attacking each other

B Queens placed in the same row only

C Queens placed in the same column only

D Queens placed only on diagonals

The problem requires placing queens so that none attack each other, meaning no two queens share the same row, column, or diagonal.

Which technique is best suited to solve the N Queens Problem?

A Backtracking

B Sorting

C Dynamic Programming

D Greedy Algorithm

Backtracking tries placing queens step-by-step and backtracks when conflicts occur, making it ideal for this problem.

When placing a queen, which of these is NOT checked for conflicts?

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 for queen attacks.

What happens when a conflict is found during backtracking?

A The algorithm tries a different position

B The queen is removed and the algorithm backtracks

C The algorithm stops completely

D The queen is moved to the next row

Backtracking removes the queen and tries other positions to find a safe placement.

How many queens are placed on the board in the N Queens Problem?

A N divided by 2

B N squared

C N

D 2N

Exactly N queens are placed on an N×N board.

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

Think about trying positions and undoing moves when stuck.

Describe how to check if a queen placement is safe on the board.

Focus on columns and diagonals since rows are handled by design.

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