N Queens Problem in DSA Typescript - Time & Space Complexity

Time Complexity: N Queens Problem

O(n!)

Understanding Time Complexity

We want to understand how the time needed to solve the N Queens problem grows as the board size increases.

Specifically, how does the number of steps change when we try to place queens on larger boards?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code tries to place queens row by row, checking if each position is safe, and uses backtracking to find a solution.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop tries all columns in a row, and the recursive call tries to place queens in the next row.
• How many times: For each row, it tries up to n columns, and this repeats recursively for n rows, exploring many board states.

How Execution Grows With Input

As the board size n grows, the number of ways to place queens grows very fast because each row tries many columns and backtracks often.

Input Size (n)	Approx. Operations
4	Hundreds of checks
8	Thousands to tens of thousands of checks
12	Millions of checks

Pattern observation: The operations grow faster than just multiplying by n; it grows roughly like n factorial because of the many possible queen placements.

Final Time Complexity

Time Complexity: O(n!)

This means the time needed grows very fast, roughly like the number of ways to arrange queens on the board, making it hard for large n.

Common Mistake

[X] Wrong: "The algorithm only checks n positions per row, so it should be O(n^2)."

[OK] Correct: Because it tries many combinations recursively, the total checks multiply across rows, leading to factorial growth, not just squared.

Interview Connect

Understanding this problem's time complexity helps you explain why backtracking can be expensive and when to expect slow solutions, a useful skill in interviews.

Self-Check

"What if we added pruning to stop early when conflicts are detected? How would the time complexity change?"

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