Sudoku Solver Using Backtracking in DSA Javascript

Mental Model

Try placing numbers one by one in empty cells and backtrack if a number breaks Sudoku rules until the board is solved.

Analogy: It's like trying to fit puzzle pieces in a grid: if a piece doesn't fit, you remove it and try another until the puzzle is complete.

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

_ means empty cell

Dry Run Walkthrough

Input: Partially filled 9x9 Sudoku board with some empty cells represented by 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; 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 to see if it fits in the empty cell

Step 2: Check if 1 is valid in row 0, column 2; it's valid, so place it

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: Number 1 does not break Sudoku rules here

Step 3: Move to next empty cell at row 0, column 3; try number 1

5 3 1 | [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 placing 1 in next empty cell

Step 4: Check if 1 is valid in row 0, column 3; it's invalid because 1 is already in the same column

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: Number 1 conflicts with existing 1 in column

Step 5: Try number 2 in row 0, column 3; it's valid, so place it

5 3 1 | [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 2 fits without breaking rules

Step 6: Continue this process recursively until all empty cells are filled correctly

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 cells are correctly filled

Result:

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

Solved Sudoku board

Annotated Code

DSA Javascript

class SudokuSolver {
  constructor(board) {
    this.board = board;
  }

  isValid(row, col, num) {
    // Check row
    for (let x = 0; x < 9; x++) {
      if (this.board[row][x] === num) return false;
    }
    // Check column
    for (let y = 0; y < 9; y++) {
      if (this.board[y][col] === num) return false;
    }
    // Check 3x3 box
    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() {
    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; // all cells filled
  }

  printBoard() {
    for (let row = 0; row < 9; row++) {
      let line = '';
      for (let col = 0; col < 9; col++) {
        line += this.board[row][col] + (col === 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 if num already exists in the current row

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

Check if num already exists in the current column

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 if num already exists in the 3x3 box

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

Find an empty cell to fill

if (this.isValid(row, col, num)) { this.board[row][col] = num;

Try placing num if valid

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

Recursively solve rest of board

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

Backtrack if no solution found with current num

return false;

Return false if no valid number fits in this 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) for recursion stack where n is number of empty cells

vs Alternative: Backtracking is more efficient than brute force trying all combinations because it stops early when invalid states are found

Edge Cases

Empty board (all zeros)

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

DSA Javascript

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

Already solved board

Solver quickly returns true without changes

DSA Javascript

return true; // all cells filled

Board with no valid solution

Solver backtracks fully and returns false

DSA Javascript

return false; // no valid number found

When to Use This Pattern

When you need to fill a grid with constraints and try options one by one, backtracking is the pattern to explore all possibilities efficiently.

Common Mistakes

Mistake: Not resetting the cell to 0 when backtracking
Fix: Set the cell back to 0 after recursive call fails to undo the choice

Mistake: Checking only row or column but forgetting 3x3 box
Fix: Always check row, column, and 3x3 box for validity

Summary

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

Use it when you must explore many possible placements under strict rules.

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

Practice

1. What is the main idea behind using backtracking to solve a Sudoku puzzle?

easy

A. Try placing numbers one by one and backtrack if a conflict occurs

B. Fill all empty cells randomly and check if the puzzle is solved

C. Use a sorting algorithm to arrange numbers in order

D. Replace all zeros with the number 9 directly

Solution

1. Step 1: Understand backtracking approach

   Backtracking tries numbers in empty cells one by one and checks if they fit the Sudoku rules.

2. Step 2: Handle conflicts by backtracking

   If a number causes a conflict, the algorithm removes it and tries the next number, going back if needed.

3. Final Answer:

   Try placing numbers one by one and backtrack if a conflict occurs -> Option A

4. Quick Check:

   Backtracking = Try and undo [OK]

Hint: Backtracking means try, check, undo if wrong [OK]

Common Mistakes:

• Thinking backtracking fills cells randomly
• Assuming sorting solves Sudoku
• Replacing zeros without checks

2. Which of the following is the correct way to check if a number can be placed in a Sudoku cell in JavaScript?

easy

A. if isSafe(board, row, col, num) { placeNumber(); }

B. if isSafe(board, row, col, num) then placeNumber();

C. if (isSafe board, row, col, num) { placeNumber(); }

D. if (isSafe(board, row, col, num)) { placeNumber(); }

Solution

1. Step 1: Understand JavaScript if syntax

   JavaScript requires parentheses around the condition in an if statement.

2. Step 2: Check function call syntax

   Function calls need parentheses with arguments inside, like isSafe(board, row, col, num).

3. Final Answer:

   if (isSafe(board, row, col, num)) { placeNumber(); } -> Option D

4. Quick Check:

   if(condition) with parentheses [OK]

Hint: Use parentheses around conditions in if statements [OK]

Common Mistakes:

• Missing parentheses in if condition
• Using 'then' keyword in JavaScript
• Incorrect function call syntax

3. What will be the output of the following code snippet when solving a Sudoku board?

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]
];
solveSudoku(board);
console.log(board);

medium

A. An error because solveSudoku is not defined

B. The original board unchanged with zeros intact

C. A fully solved Sudoku board with no zeros

D. A partially solved board with some zeros replaced

Solution

1. Step 1: Understand solveSudoku function purpose

   solveSudoku uses backtracking to fill all empty cells correctly, solving the puzzle.

2. Step 2: Check console.log output after solving

   After solveSudoku runs, the board is fully solved with no zeros remaining.

3. Final Answer:

   A fully solved Sudoku board with no zeros -> Option C

4. Quick Check:

   Backtracking solves all cells [OK]

Hint: Backtracking fills all empty cells correctly [OK]

Common Mistakes:

• Expecting original board unchanged
• Thinking partial fill is final
• Assuming function is undefined

4. Consider this buggy code snippet for checking if a number can be placed in a Sudoku cell:

function isSafe(board, row, col, num) {
  for (let x = 0; x < 9; x++) {
    if (board[row][x] === num || board[x][col] === num) {
      return false;
    }
  }
  // Missing 3x3 box check
  return true;
}

What is the main problem here?

medium

A. It returns false too early

B. It does not check the 3x3 subgrid for duplicates

C. It uses wrong loop variable x

D. It modifies the board inside the function

Solution

1. Step 1: Analyze row and column checks

   The code correctly checks if num exists in the same row or column.

2. Step 2: Identify missing 3x3 subgrid check

   Sudoku rules require checking the 3x3 box; this code does not do that, causing errors.

3. Final Answer:

   It does not check the 3x3 subgrid for duplicates -> Option B

4. Quick Check:

   3x3 box check missing = bug [OK]

Hint: Always check row, column, and 3x3 box [OK]

Common Mistakes:

• Ignoring 3x3 box validation
• Thinking loop variable causes error
• Assuming early return is wrong

5. You want to optimize the Sudoku solver by choosing the next empty cell with the fewest possible valid numbers to try. Which technique does this describe?

hard

A. Heuristic with Minimum Remaining Value (MRV) strategy

B. Random guessing of empty cells

C. Depth-first search without pruning

D. Sorting the board rows before solving

Solution

1. Step 1: Understand MRV heuristic

   MRV chooses the empty cell with the fewest valid options to reduce branching and speed up solving.

2. Step 2: Compare with other options

   Random guessing and depth-first search without pruning are less efficient; sorting rows does not help solving.

3. Final Answer:

   Heuristic with Minimum Remaining Value (MRV) strategy -> Option A

4. Quick Check:

   MRV = choose cell with fewest options [OK]

Hint: Pick cell with fewest choices first [OK]

Common Mistakes:

• Confusing random guessing with heuristics
• Ignoring pruning benefits
• Thinking sorting helps solving