N Queens Problem in DSA Typescript

Mental Model

Place N queens on an NxN chessboard so that no two queens attack each other. We try positions row by row, backtracking when conflicts arise.

Analogy: Imagine seating N guests at N tables in a row, where no two guests can see each other directly across or diagonally. You seat one guest per table and move to the next, changing seats if conflicts happen.

Board (4x4) empty:
. . . .
. . . .
. . . .
. . . .

Legend:
Q = Queen
. = Empty space

Dry Run Walkthrough

Input: N=4, find all ways to place 4 queens on 4x4 board

Goal: Find all valid arrangements where 4 queens do not attack each other

Step 1: Place queen at row 0, column 1

. Q . .
. . . .
. . . .
. . . .

Why: Start with first queen in first row at column 1 to begin exploring placements

Step 2: Place queen at row 1, column 3

. Q . .
. . . Q
. . . .
. . . .

Why: Second queen placed where it does not attack first queen

Step 3: Try placing queen at row 2, column 0 - conflict found, backtrack

. Q . .
. . . Q
Q . . . (conflict)
. . . .

Why: Queen at (2,0) attacks queen at (0,1), so we remove and try next column

Step 4: Place queen at row 2, column 2

. Q . .
. . . Q
. . Q .
. . . .

Why: Safe position found for third queen

Step 5: Place queen at row 3, column 0

. Q . .
. . . Q
. . Q .
Q . . .

Why: Fourth queen placed safely, one solution found

Step 6: Backtrack to find other solutions by moving last queen

. Q . .
. . . Q
. . Q .
. . . .

Why: Remove last queen to try other columns in last row

Step 7: Eventually find second solution with queens at (0,2), (1,0), (2,3), (3,1)

. . Q .
Q . . .
. . . Q
. Q . .

Why: Backtracking explores all valid configurations

Result:

Two solutions found:
1) . Q . .
   . . . Q
   . . Q .
   Q . . .

2) . . Q .
   Q . . .
   . . . Q
   . Q . .

Annotated Code

DSA Typescript

class NQueens {
  size: number;
  board: number[];
  solutions: string[][];

  constructor(n: number) {
    this.size = n;
    this.board = new Array(n).fill(-1); // board[row] = col of queen
    this.solutions = [];
  }

  isSafe(row: number, col: number): boolean {
    for (let prevRow = 0; prevRow < row; prevRow++) {
      const prevCol = this.board[prevRow];
      if (prevCol === col || Math.abs(prevCol - col) === row - prevRow) {
        return false; // same column or diagonal conflict
      }
    }
    return true;
  }

  solve(row: number = 0): void {
    if (row === this.size) {
      this.addSolution();
      return;
    }
    for (let col = 0; col < this.size; col++) {
      if (this.isSafe(row, col)) {
        this.board[row] = col; // place queen
        this.solve(row + 1); // move to next row
        this.board[row] = -1; // backtrack
      }
    }
  }

  addSolution(): void {
    const solution = this.board.map(col => {
      return '.'.repeat(col) + 'Q' + '.'.repeat(this.size - col - 1);
    });
    this.solutions.push(solution);
  }

  printSolutions(): void {
    this.solutions.forEach((sol, i) => {
      console.log(`Solution ${i + 1}:`);
      sol.forEach(row => console.log(row));
      console.log('');
    });
  }
}

const nQueens = new NQueens(4);
nQueens.solve();
nQueens.printSolutions();

for (let prevRow = 0; prevRow < row; prevRow++) {

check all previously placed queens for conflicts

if (prevCol === col || Math.abs(prevCol - col) === row - prevRow) {

detect column or diagonal attacks

if (this.isSafe(row, col)) {

only place queen if safe

this.board[row] = col;

place queen in current row

this.solve(row + 1);

recurse to next row

this.board[row] = -1;

remove queen to backtrack

const solution = this.board.map(col => { return '.'.repeat(col) + 'Q' + '.'.repeat(this.size - col - 1); });

convert board array to string rows for output

Output

Solution 1:

.Q..

...Q

..Q.

Q...



Solution 2:

..Q.

Q...

...Q

.Q..

Complexity Analysis

Time: O(N!) because we try placing queens row by row and prune invalid columns, but worst case explores factorial possibilities

Space: O(N) for board array and recursion stack depth equal to number of rows

vs Alternative: Naive brute force tries all N^N placements, which is much slower than backtracking pruning invalid positions early

Edge Cases

N=1 (smallest board)

One queen placed trivially, one solution

DSA Typescript

if (row === this.size) { this.addSolution(); return; }

N=2 or N=3 (no solutions)

Backtracking finds no valid placements, solutions array remains empty

DSA Typescript

if (this.isSafe(row, col)) { ... }

Large N (e.g., N=8)

Algorithm finds all solutions but takes longer due to combinatorial complexity

DSA Typescript

for (let col = 0; col < this.size; col++) { ... }

When to Use This Pattern

When a problem asks to place items on a grid with constraints that no two items attack or conflict, use backtracking to try positions row by row and undo choices when conflicts appear.

Common Mistakes

Mistake: Not checking diagonal conflicts correctly
Fix: Check if absolute difference of columns equals difference of rows to detect diagonal attacks

Mistake: Not backtracking by resetting the board state after recursive call
Fix: Reset the queen position to -1 after recursive call to explore other options

Mistake: Trying to place more than one queen per row
Fix: Place exactly one queen per row and move to next row

Summary

Find all ways to place N queens on an NxN board so none attack each other.

Use when you need to explore all valid configurations with constraints on placement.

Try placing queens row by row, backtrack when conflicts arise to explore all solutions.

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