A Sudoku Solver in JavaScript Without Backtracking

The Codewars kata reads: write a function that takes a 9x9 sudoku grid as a 2D array, with 0 for unknowns, and return the solved board. Buried in the prose: the puzzles will be easy, i.e. determinable.

That word — determinable — is the whole problem. It says every empty cell can, eventually, be filled by elimination alone. No guessing. No "try a 5 here and see if the rest of the board breaks." If you read past it too quickly you end up writing a general sudoku solver, and a general sudoku solver means backtracking.

The obvious approach

The textbook answer to "solve any sudoku" is recursive backtracking. Pick an empty cell, try each legal digit, recurse, and if the recursion comes back as a dead end, undo and try the next digit. It works on every solvable sudoku in existence — including the genuinely hard ones where multiple candidates remain at every cell and the only way forward is hypothesis-and-rollback.

It also does a lot of pointless work on this kata. The puzzles are stated to be determinable, which means at every step of the solve there exists at least one empty cell with exactly one possible value. You never need to branch. You never need to undo. The "search" tree is a straight line.

What actually works here

For each empty cell, look at three things:

• the row it sits in
• the column it sits in
• the 3x3 box it sits in

Union those into a set of "digits already used in this cell's neighbourhood." If the set contains eight distinct digits from 1 to 9, then the ninth — the missing one — is forced. That's the value. Write it in.

Repeat the sweep until the board is full.

That's the whole algorithm. No candidate lists per cell, no naked-pairs, no hidden-singles, no DLX. Just: "is exactly one digit missing from this cell's row + column + box?" If yes, fill it.

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

function sudoku(puzzle) {
  for (const y of vals) {
    for (const x of vals) {
      if (puzzle[y][x] !== 0) continue;

      const row = puzzle[y];
      const col = puzzle.map(r => r[x]);

      const sqX = ~~(x / 3) * 3;
      const sqY = ~~(y / 3) * 3;
      const square = vals.map(i => puzzle[sqY + ~~(i / 3)][sqX + (i % 3)]);

      const seen = new Set([...row, ...col, ...square].filter(Boolean));

      if (seen.size === 8) {
        puzzle[y][x] = [1, 2, 3, 4, 5, 6, 7, 8, 9].find(n => !seen.has(n));
        return sudoku(puzzle);
      }
    }
  }
  return puzzle;
}

A few notes on what's happening there.

The set is the trick. Spread the row, the column and the nine box cells into a single Set, filter out the zeros (those are "unknown" not "used"), and ask size === 8. A set deduplicates for free, which is exactly what you want — a digit that appears in both the row and the box should count once.

~~ is Math.floor in disguise — double bitwise NOT truncates toward zero. Stylistic, slightly horrendous, do what you like. Math.floor(x / 3) * 3 reads the same.

The recursion is doing nothing clever. After filling one cell, the board state has changed, so re-sweep from the top. When a full sweep completes without finding any forced cell, the board is solved and we fall through to the return.

Why this works on Codewars and nowhere else

The honest version of this post: the algorithm above will hang or return an incomplete board on any sudoku that requires lookahead. If you ever reach a sweep where every empty cell has two or more legal candidates, seen.size never hits 8, nothing gets filled, and the function returns the puzzle as-is.

Most real sudokus — the hard ones in newspapers, the "evil" tier on apps — are not determinable in this sense. They require you to provisionally place a digit, follow the consequences, and roll back if it contradicts. That's backtracking, and it's unavoidable.

Codewars guarantees determinable inputs. Within that guarantee, search is wasted code. The lesson generalises beyond sudoku.

The actual lesson

When the search space has enough structure, constraint propagation can replace search entirely.

Most problems live somewhere on a spectrum. At one end: pure search, where you have no information beyond "is this state valid?" and the only move is to try things. At the other end: pure deduction, where every step is forced by what you already know. Backtracking is the universal hammer for the first end. Constraint propagation is the scalpel for the second.

The mistake is to default to the hammer because it always works. The thing worth noticing is the shape of the problem. The word "determinable" in a kata description is a load-bearing word. So is "unique solution," "well-formed input," "guaranteed to converge." When the problem statement tells you the inputs are nice, the solution can be nicer too.

In practice it looks like this: a function that would have been thirty lines of recursion-with-state becomes ten lines of "sweep and fill." It runs faster. It's easier to read. And it fails loudly and immediately on inputs that violate the assumption — which, if you're being honest about your inputs, is a feature.

The general solver still exists. Keep it in your back pocket for the day someone hands you a real sudoku.