Backtracking: Solving Problems by Guessing Systematically

An empty Sudoku grid has 81 cells and 9 possible values each. That’s 9⁸¹ — around 10⁷⁷ — grids, comparable to the number of atoms in the observable universe. Yet a laptop solves Sudoku in milliseconds.

The gap between those two facts is backtracking, and once I understood it I started seeing it everywhere. It’s how you search a space too large to enumerate: not by being clever about which answer is right, but by being disciplined about abandoning wrong ones early.

I built a Sudoku solver in the browser mainly so I could watch it happen — the grid updates cell by cell as the algorithm guesses, gets stuck and reverses out. Code: gitlab.com/rustam.niraula90/sudoku-solver.

These are my notes from building it.

---

Concept 1: A solution space is a tree, and most of it is dead

The reframing that made this click: stop thinking about 10⁷⁷ complete grids and think about partial ones. Fill the first cell — 9 branches. Fill the second — 9 more each. That’s a tree, and a path from the root to depth 81 is a candidate solution.

The crucial part is that the tree is mostly dead on arrival. If the first two cells both hold a 5 in the same row, every one of the 9⁷⁹ grids below that node is invalid. You never visit them; you don’t even need to know how many there are. Cutting a branch at depth 2 discards an astronomical subtree for the cost of one comparison.

That’s the whole trick. Backtracking is depth-first search plus the discipline of testing validity at every step rather than at the end. The exponential space never materialises because you’re never holding more than one partial candidate at a time.

Concept 2: The constraint check is the real engine

Everything depends on cheaply answering one question: can this value go in this cell? For Sudoku the rules are row, column and 3×3 box uniqueness:

function possible(x, y, n) {
    for (let i = 0; i < 9; i++) {
        if (puzzle[x][i] == n || puzzle[i][y] == n) {
            return false;
        }
    }
    let x0 = Math.floor(x / 3) * 3;
    let y0 = Math.floor(y / 3) * 3;
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            if (puzzle[x0 + i][y0 + j] == n) {
                return false;
            }
        }
    }
    return true;
}

Two details I’ve reused many times since:

Row and column share one loop. puzzle[x][i] walks the row while puzzle[i][y] walks the column — same index, two constraints, one pass. Constraint checks run millions of times, so this is the one place in a backtracking solver where micro-optimisation genuinely pays for itself.

The box origin is integer division. Math.floor(x / 3) * 3 snaps any coordinate to the top-left corner of its 3×3 block. Mapping a point to the region containing it by rounding down to a multiple of the region size turns out to be a pattern that shows up constantly — tiling, spatial hashing, pagination.

Concept 3: Guess, recurse, undo

With a validity test in hand, the solver is remarkably short. Find an empty cell, try each candidate, recurse, and undo the guess if the recursion doesn’t pan out:

async function solve() {
    for (let x = 0; x < 9; x++) {
        for (let y = 0; y < 9; y++) {
            if (puzzle[x][y] == 0) {
                for (let n = 1; n < 10; n++) {
                    if (sudokuSolver.possible(x, y, n)) {
                        puzzle[x][y] = n;                        // guess
                        sudokuSolver.updateViewValue();
                        await new Promise(r => setTimeout(r, sudokuSolver.bufferTime));
                        await sudokuSolver.solve();              // recurse
                        if (!sudokuSolver.isSolved()) {
                            puzzle[x][y] = 0;                    // undo
                        } else {
                            return;                              // done
                        }
                    }
                }
                return;   // no candidate worked — dead end, unwind
            }
        }
    }
}

Three lines carry the idea:

1. puzzle[x][y] = n — commit to a guess.
2. await solve() — explore everything that follows from it.
3. puzzle[x][y] = 0 — restore the state exactly as it was before trying the next candidate.

That third line is the one I’d underestimated. Your state has to be restorable. Here it’s trivial, because a guess writes one cell and undoing is one assignment — and that’s not luck, it’s a consequence of representing the puzzle as a plain mutable grid. In harder problems (graph colouring, N-queens with incremental constraint tables, dependency resolution) you either design the mutation to be cheaply reversible or you pay to copy state at every branch. Picking a representation you can undo is the actual design work.

The bare return at the end of the cell loop is subtle and load-bearing: if no value fits an empty cell, this branch is unsolvable, so stop immediately. That early return is the pruning.

Concept 4: How a recursive search reports success

My version detects completion by scanning the grid for empty cells:

function isSolved() {
    for (let x = 0; x < 9; x++) {
        for (let y = 0; y < 9; y++) {
            if (puzzle[x][y] == 0) return false;
        }
    }
    return true;
}

Design note. This checks a global condition — “is the whole grid full?” — after each recursive call, rather than having solve() return a boolean that propagates up the stack. Both terminate correctly, and pruning dominates the runtime either way, so the visible behaviour is the same. The difference is in how the stack unwinds: a boolean return lets each of the ~81 frames exit immediately, while a global check re-derives the answer at every frame and restarts its cell scan from (0,0) on each descent.

Writing it the second way and then reasoning about the first is what gave me the principle I now apply by reflex: a recursive function should report its own outcome rather than have its caller re-derive it from shared state. Threading the answer through the return value is what keeps unwinding O(depth) instead of O(depth × grid). It’s a one-word change here, and a habit worth having before the problem is bigger.

Concept 5: Animating a recursive algorithm in a single-threaded language

This is the part I actually built the project to explore. JavaScript has one thread running both my code and the DOM. A synchronous recursive solve finishes in a few milliseconds and repaints exactly once — you’d see an empty grid, then a finished one, and learn nothing about the search.

To watch it, the algorithm has to hand control back to the browser between steps:

sudokuSolver.updateViewValue();
await new Promise(r => setTimeout(r, sudokuSolver.bufferTime));

new Promise(r => setTimeout(r, ms)) is the idiomatic sleep — a promise that resolves on a timer. Awaiting it suspends the function, returns control to the event loop so the browser can lay out and paint, and resumes where it left off. Cooperative yielding: the algorithm volunteers the thread rather than being preempted.

What makes this practical is that async/await composes through recursion. await solve() inside solve() means a pause at depth 40 correctly suspends all 40 frames above it, and they resume in order. Doing the same with callbacks would mean turning the recursion inside out into an explicit state machine with a manual stack. Coroutines let me keep the natural recursive shape and get the pause, and that realisation has outlived the project — it’s the same reason generators and async iterators feel so useful for streaming work.

The delay is a slider bound to bufferTime, 0 to 500 ms. At 0 the search rips through the grid; at 250 ms you can follow individual guesses and watch it reverse out of a dead end. Making speed a control instead of a constant is what turned this from a visualisation into something I learned from — seeing it stall and unwind is what made the concept concrete in a way pseudocode never did.

Where this idea showed up next

Sudoku was the friendly introduction. The same four-part structure — candidate generation, constraint check, recursive descent, undo — turned out to be the backbone of:

• N-Queens and other placement puzzles
• Graph colouring and scheduling under conflict constraints
• Regular expression backtracking (also where catastrophic blowup comes from, when the pruning isn’t effective)
• SAT solvers, where DPLL is backtracking plus much smarter propagation
• Dependency resolution in package managers, picking versions under compatibility constraints

And the natural next step is the same in all of them: better ordering. My solver takes cells in reading order and values in ascending order. Choose the most constrained cell first — fewest legal candidates remaining — and you fail faster, which means you prune higher in the tree. That single heuristic (MRV, minimum remaining values) typically cuts the search by orders of magnitude without changing the structure of the algorithm at all. Adding it is the obvious next iteration here, and it’s cheap: sort the empty cells by candidate count instead of scanning them in order.

Backtracking isn’t a trick for one puzzle. It’s a general answer to “the space is too big to enumerate,” and the answer is: don’t enumerate it — walk it, and leave early.