Creating a Sudoku Solver Using Backtracking in JavaScript

Sudoku is one of the world’s most popular logic puzzles. While solving it by hand is fun, building a program that can solve any valid Sudoku puzzle is an excellent way to learn recursion, backtracking, and algorithmic thinking.

In this tutorial, we’ll build a Sudoku solver in JavaScript using the Backtracking Algorithm. This approach is simple, elegant, and widely used to teach recursive problem-solving.

By the end of this article, you’ll understand:

• How the Backtracking algorithm works
• How to validate Sudoku moves
• How recursion solves the puzzle
• Time complexity and possible optimizations
• Where backtracking is used in real-world software

📖 What Is Sudoku?

Sudoku is played on a 9×9 grid divided into nine 3×3 boxes.

The objective is simple:

• Every row must contain the numbers 1–9 exactly once.
• Every column must contain the numbers 1–9 exactly once.
• Every 3×3 box must contain the numbers 1–9 exactly once.

A properly designed Sudoku puzzle has one unique solution, making it a perfect candidate for algorithmic solving.

🤔 Why Use Backtracking?

Backtracking is a recursive search algorithm that tries every valid possibility until it finds the correct solution.

The process looks like this:

1. Find an empty cell.
2. Try numbers 1–9.
3. Check if the number is valid.
4. If valid, place it.
5. Recursively solve the remaining puzzle.
6. If no solution is found, undo the move and try another number.

This “try → verify → undo” process is what gives the algorithm its name: Backtracking.

🔄 Algorithm Flow

Find Empty Cell
        │
        ▼
 Try Numbers 1–9
        │
        ▼
 Is Number Valid?
     │        │
    Yes      No
     │
     ▼
 Place Number
     │
     ▼
 Solve Next Cell
     │
     ▼
Solved?
 │        │
Yes      No
 │
 ▼
Done
         ▲
         │
   Backtrack

🗂 Step 1: Represent the Sudoku Board

We’ll store the puzzle in a two-dimensional array.

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]
];

A value of 0 represents an empty cell.

🔍 Step 2: Find an Empty Cell

function findEmpty(board) {
    for (let row = 0; row < 9; row++) {
        for (let col = 0; col < 9; col++) {
            if (board[row][col] === 0) {
                return [row, col];
            }
        }
    }

    return null;
}

If this function returns null, the puzzle has been solved.

✅ Step 3: Check Whether a Number Is Valid

Before placing a number, we must ensure it doesn’t violate any Sudoku rules.

function isValid(board, row, col, num) {

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

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

    // Check 3×3 box
    const startRow = Math.floor(row / 3) * 3;
    const startCol = Math.floor(col / 3) * 3;

    for (let r = startRow; r < startRow + 3; r++) {
        for (let c = startCol; c < startCol + 3; c++) {
            if (board[r][c] === num)
                return false;
        }
    }

    return true;
}

This function validates all three Sudoku constraints before allowing a move.

🚀 Step 4: Solve the Puzzle

Now we combine everything with recursion.

function solve(board) {

    const empty = findEmpty(board);

    if (!empty) {
        return true;
    }

    const [row, col] = empty;

    for (let num = 1; num <= 9; num++) {

        if (isValid(board, row, col, num)) {

            board[row][col] = num;

            if (solve(board)) {
                return true;
            }

            // Backtrack
            board[row][col] = 0;
        }
    }

    return false;
}

The key line is:

board[row][col] = 0;

If a choice leads to a dead end, we erase it and try the next number.

▶️ Run the Solver

if (solve(board)) {
    console.table(board);
} else {
    console.log("No solution found.");
}

Once the function completes, the board array contains the solved Sudoku.

📊 Time Complexity

The worst-case time complexity is:

O(9ⁿ)

Where n is the number of empty cells.

Although this appears expensive, Sudoku constraints eliminate many invalid paths early, so most real puzzles solve in milliseconds.

Complexity Summary

⚡ Performance Optimizations

The basic solver works well, but advanced techniques can improve performance significantly.

• ✅ Minimum Remaining Values (MRV)
• ✅ Candidate Lists
• ✅ Bitmasking
• ✅ Constraint Propagation
• ✅ Forward Checking
• ✅ Dancing Links (Algorithm X)

Professional Sudoku engines combine several of these optimizations to solve even the hardest puzzles almost instantly.

🚨 Common Mistakes

1. Forgetting to Backtrack

Always reset the cell if the current path fails.

board[row][col] = 0;

2. Incorrect 3×3 Box Calculation

Always calculate the starting position correctly.

const startRow = Math.floor(row / 3) * 3;
const startCol = Math.floor(col / 3) * 3;

3. Returning Too Early

Test every possible number before deciding that no solution exists.

4. Infinite Recursion

Always make sure your recursive call moves toward the base case by filling an empty cell.

🌍 Real-World Applications

Backtracking is used in many areas of computer science.

Examples include:

• Sudoku Solvers
• Crossword Puzzle Generators
• Maze Solvers
• N-Queens Problem
• Timetable Scheduling
• Constraint Satisfaction Problems (CSP)
• AI Search Algorithms
• Path Finding

Learning Sudoku is one of the best ways to understand recursion and backtracking.

🚀 What’s Next?

Now that you’ve built a Sudoku solver, try these projects next:

• Build a Sudoku Generator
• Generate puzzles with a unique solution
• Add difficulty ratings
• Create a visual solving animation
• Optimize with Bitmasks
• Learn Dancing Links (Algorithm X)

Each project introduces new algorithmic concepts and helps improve your programming skills.

🎯 Conclusion

Backtracking is one of the simplest yet most powerful algorithms for solving Sudoku. With fewer than 100 lines of JavaScript, you can build a solver that demonstrates recursion, depth-first search, state management, and constraint checking.

I recently applied many of these ideas while building MySudokuWorld, an online Sudoku platform featuring daily challenges, multiple difficulty levels, and learning resources.

If you’d like to test your own solver or practice on real Sudoku puzzles, you can explore it here:

👉 https://www.mysudokuworld.com/

If you enjoyed this article, my next post will cover Generating Infinite Sudoku Puzzles with JavaScript, where we’ll build a puzzle generator that always produces a unique solution.

Happy Coding! 🚀