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.