Sudoku Solver Using Backtracking in DSA Typescript

Mental Model

Try placing numbers one by one in empty cells and backtrack if a number leads to a conflict.

Analogy: Like trying keys on a locked door one by one, and if a key doesn't fit, you go back and try another key until the door opens.

5 3 _ | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9
↑ empty cells marked as _

Dry Run Walkthrough

Input: Partially filled 9x9 Sudoku board with some empty cells marked as 0

Goal: Fill all empty cells with numbers 1-9 so that each row, column, and 3x3 box contains all digits without repetition

Step 1: Find first empty cell at row 0, column 2 and try number 1

5 3 [1] | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Try smallest number first to find a valid placement

Step 2: Check if number 1 is valid at row 0, column 2; it conflicts with number 1 in column 3, so try next number 2

5 3 [2] | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Number 1 conflicts, so try next number

Step 3: Number 2 is valid at row 0, column 2; move to next empty cell at row 0, column 3

5 3 2 | [_] 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Placed valid number, proceed to next empty cell

Step 4: Try numbers 1 to 9 at row 0, column 3; numbers 1, 2, 3 conflict; number 4 is valid

5 3 2 | [4] 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Find first valid number for this cell

Step 5: Continue this process recursively, backtracking when no valid number found for a cell

Fully filled Sudoku board with no conflicts:
5 3 4 | 6 7 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | 7 6 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9

Why: Backtracking ensures all possibilities are explored until solution is found

Result:

Fully solved Sudoku board:
5 3 4 | 6 7 8 | 9 1 2
6 7 2 | 1 9 5 | 3 4 8
1 9 8 | 3 4 2 | 5 6 7
------+-------+------
8 5 9 | 7 6 1 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 1 3 | 9 2 4 | 8 5 6
------+-------+------
9 6 1 | 5 3 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
3 4 5 | 2 8 6 | 1 7 9

Annotated Code

DSA Typescript

class SudokuSolver {
  board: number[][];

  constructor(board: number[][]) {
    this.board = board;
  }

  isValid(row: number, col: number, num: number): boolean {
    // Check row for duplicate
    for (let x = 0; x < 9; x++) {
      if (this.board[row][x] === num) return false;
    }

    // Check column for duplicate
    for (let y = 0; y < 9; y++) {
      if (this.board[y][col] === num) return false;
    }

    // Check 3x3 box for duplicate
    const startRow = Math.floor(row / 3) * 3;
    const startCol = Math.floor(col / 3) * 3;
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        if (this.board[startRow + i][startCol + j] === num) return false;
      }
    }

    return true;
  }

  solve(): boolean {
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        if (this.board[row][col] === 0) {
          for (let num = 1; num <= 9; num++) {
            if (this.isValid(row, col, num)) {
              this.board[row][col] = num; // place num

              if (this.solve()) {
                return true; // solved
              }

              this.board[row][col] = 0; // backtrack
            }
          }
          return false; // no valid number found
        }
      }
    }
    return true; // no empty cells left
  }

  printBoard(): void {
    for (let i = 0; i < 9; i++) {
      let line = '';
      for (let j = 0; j < 9; j++) {
        line += this.board[i][j] + (j === 8 ? '' : ' ');
      }
      console.log(line);
    }
  }
}

const board = [
  [5,3,0,0,7,0,0,0,0],
  [6,0,0,1,9,5,0,0,0],
  [0,9,8,0,0,0,0,6,0],
  [8,0,0,0,6,0,0,0,3],
  [4,0,0,8,0,3,0,0,1],
  [7,0,0,0,2,0,0,0,6],
  [0,6,0,0,0,0,2,8,0],
  [0,0,0,4,1,9,0,0,5],
  [0,0,0,0,8,0,0,7,9]
];

const solver = new SudokuSolver(board);
if (solver.solve()) {
  solver.printBoard();
} else {
  console.log('No solution exists');
}

for (let x = 0; x < 9; x++) { if (this.board[row][x] === num) return false; }

Check row for duplicate number

for (let y = 0; y < 9; y++) { if (this.board[y][col] === num) return false; }

Check column for duplicate number

for (let i = 0; i < 3; i++) { for (let j = 0; j < 3; j++) { if (this.board[startRow + i][startCol + j] === num) return false; } }

Check 3x3 box for duplicate number

if (this.board[row][col] === 0) { for (let num = 1; num <= 9; num++) { if (this.isValid(row, col, num)) { this.board[row][col] = num;

Try numbers 1-9 in empty cell and place if valid

if (this.solve()) { return true; }

Recursively solve next cells; if solved, return true

this.board[row][col] = 0;

Backtrack by resetting cell if no number leads to solution

return false;

Return false if no valid number found for current cell

Output

5 3 4 6 7 8 9 1 2

6 7 2 1 9 5 3 4 8

1 9 8 3 4 2 5 6 7

8 5 9 7 6 1 4 2 3

4 2 6 8 5 3 7 9 1

7 1 3 9 2 4 8 5 6

9 6 1 5 3 7 2 8 4

2 8 7 4 1 9 6 3 5

3 4 5 2 8 6 1 7 9

Complexity Analysis

Time: O(9^(n)) where n is number of empty cells, because each empty cell tries up to 9 numbers recursively

Space: O(n) due to recursion stack for n empty cells

vs Alternative: Backtracking is more efficient than brute force trying all board configurations because it prunes invalid paths early

Edge Cases

Empty board (all zeros)

Solver tries all possibilities, may take longer but still finds solution or reports none

DSA Typescript

if (this.board[row][col] === 0) {

Already solved board

Solver quickly returns true without changes

DSA Typescript

return true; // no empty cells left

Board with no valid solution

Solver backtracks fully and returns false

DSA Typescript

return false; // no valid number found

When to Use This Pattern

When you see a problem requiring filling a grid with constraints and trial/error, reach for backtracking because it tries options and undoes wrong choices systematically.

Common Mistakes

Mistake: Not checking all constraints (row, column, box) before placing a number
Fix: Implement isValid function to check all three constraints before placing

Mistake: Not resetting cell to zero when backtracking
Fix: Set cell back to zero after recursive call fails to undo placement

Mistake: Stopping after first empty cell without trying all numbers
Fix: Try all numbers 1 to 9 in each empty cell before backtracking

Summary

It fills empty Sudoku cells by trying numbers and backtracking on conflicts.

Use it when you need to solve puzzles with constraints and multiple choices.

The key insight is to try a choice, move forward, and undo if it leads to a dead end.