Sudoku Solver: Backtracking with MRV Heuristic and Live Visualization

JavaScript Algorithms Data Structures Tutorial

Master Sudoku solving with JavaScript using backtracking and the MRV heuristic. Learn constraint satisfaction problem techniques with interactive visualization to see the algorithm in action.

Solving Sudoku combines the elegance of backtracking algorithms with constraint satisfaction problem (CSP) techniques. While a basic backtracking approach works, adding the Minimum Remaining Values (MRV) heuristic transforms it from a brute-force solution into an intelligent, efficient solver.

In this guide, we'll implement a complete Sudoku solver in JavaScript and explore how optimization heuristics can dramatically improve performance.

Problem Overview

We're solving a standard 9×9 Sudoku board where empty cells are represented by ".". The goal is to fill the board so that each row, column, and 3×3 subgrid contains digits 1–9 exactly once.

Sudoku always has exactly one valid solution in this problem setting, making it a perfect example of a constraint satisfaction problem.

The fundamental approach follows a systematic backtracking strategy:

  1. Try filling digits in empty cells
  2. Check constraints (row, column, box validity)
  3. Backtrack when no valid option exists
  4. Repeat until the board is completely solved

This is similar to other backtracking problems you might have seen, like the Two Pointers technique for array manipulation, but applied to constraint satisfaction.

The MRV Optimization

The MRV (Minimum Remaining Values) heuristic is what transforms our solver from good to exceptional:

  • Standard approach: Scan cells sequentially (row by row)
  • MRV approach: Always pick the cell with the fewest possible digits

This focuses the search on the "most constrained" cells first, dramatically reducing the search tree branching factor.

Why MRV works:

  • Constrained cells are more likely to fail quickly if the path is wrong
  • Early failure detection prevents wasted exploration of invalid branches
  • The algorithm becomes much more efficient on "hard" puzzles

JavaScript Implementation

Here's the complete implementation with MRV optimization:

var solveSudoku = function(board) {
  const rows = Array.from({ length: 9 }, () => Array(10).fill(false));
  const cols = Array.from({ length: 9 }, () => Array(10).fill(false));
  const boxes = Array.from({ length: 9 }, () => Array(10).fill(false));
  const empties = [];
 
  const boxId = (r, c) => Math.floor(r / 3) * 3 + Math.floor(c / 3);
 
  // Initialize constraint tracking
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const ch = board[r][c];
      if (ch === '.') {
        empties.push([r, c]);
      } else {
        const d = Number(ch);
        rows[r][d] = cols[c][d] = boxes[boxId(r, c)][d] = true;
      }
    }
  }
 
  function dfs(k) {
    if (k === empties.length) return true;
 
    // MRV: pick the cell with the fewest candidates
    let minIdx = k, minCnt = 10;
    for (let i = k; i < empties.length; i++) {
      const [r, c] = empties[i];
      let cnt = 0;
      for (let d = 1; d <= 9; d++) {
        if (!rows[r][d] && !cols[c][d] && !boxes[boxId(r, c)][d]) cnt++;
      }
      if (cnt < minCnt) {
        minCnt = cnt;
        minIdx = i;
      }
    }
 
    // Swap the most constrained cell to current position
    [empties[k], empties[minIdx]] = [empties[minIdx], empties[k]];
    const [r, c] = empties[k];
 
    // Try each valid digit
    for (let d = 1; d <= 9; d++) {
      if (!rows[r][d] && !cols[c][d] && !boxes[boxId(r, c)][d]) {
        board[r][c] = String(d);
        rows[r][d] = cols[c][d] = boxes[boxId(r, c)][d] = true;
 
        if (dfs(k + 1)) return true;
 
        // Backtrack
        board[r][c] = '.';
        rows[r][d] = cols[c][d] = boxes[boxId(r, c)][d] = false;
      }
    }
    return false;
  }
 
  dfs(0);
  return board;
};

Key Implementation Details

Constraint Tracking: We use boolean arrays to track which digits are already used in each row, column, and 3×3 box. This gives us O(1) constraint checking.

Box ID Calculation: Math.floor(r / 3) * 3 + Math.floor(c / 3) maps any cell position to its corresponding 3×3 box index.

MRV Selection: For each recursive call, we find the empty cell with the minimum number of valid digits and solve it first.

Live Visualization 🎥

Understanding backtracking algorithms becomes much clearer when you can see them in action. I've created an interactive visualization that shows:

  • Real-time backtracking: Watch cells being filled and unfilled as the algorithm explores different paths

  • MRV heuristic in action: See how the algorithm intelligently picks the most constrained cells first

  • Final solution: The complete board once all constraints are satisfied

  • GitHub Repository: sudoku-visualizer

  • Live Demo: Sudoku Visualizer

The visualization makes it clear why MRV is so effective—you'll see the algorithm immediately attack the hardest cells, pruning invalid branches early.

Performance Impact of MRV

The difference between naive backtracking and MRV-optimized backtracking is dramatic:

Without MRV: The algorithm may branch widely, testing many unnecessary paths across "easy" cells while leaving difficult constraints for later.

With MRV: It always attacks the hardest cells first, causing invalid paths to fail quickly and reducing the overall search space.

This optimization can transform a solver that takes seconds on hard puzzles into one that solves them in milliseconds. The technique is particularly powerful when combined with other algorithmic approaches you might recognize from problems like sliding window optimization.

Extensions and Advanced Techniques

Once you've mastered the basic MRV approach, consider these advanced optimizations:

Bitmasking

Replace boolean arrays with bitmasks for faster constraint checks:

// Instead of: if (!rows[r][d] && !cols[c][d] && !boxes[boxId][d])
// Use: if ((rows[r] | cols[c] | boxes[boxId]) & (1 << d)) === 0)

Constraint Propagation

When a cell has only one possible value, fill it immediately and propagate the constraints. This reduces the search space before backtracking even begins.

Hybrid Solving

Combine human-style solving heuristics (like naked singles, hidden singles) with backtracking for even faster performance on typical puzzles.

Conclusion

This Sudoku solver demonstrates how intelligent heuristics can transform algorithmic performance. The MRV optimization shows that how you explore a search space is often more important than what you're searching for.

The combination of:

  • Clean JavaScript implementation
  • Efficient constraint tracking
  • MRV heuristic optimization
  • Interactive visualization for learning

...makes this not just an effective solver, but a perfect tool for understanding backtracking algorithms in action.

Whether you're preparing for coding interviews or simply want to understand constraint satisfaction problems better, this approach provides both theoretical insight and practical implementation skills.