Menu

Build a Sudoku solver in TypeScript

By Sudoku Online Editorial Team ·

A Sudoku solver needs three ideas: a table of which cells see each other, a way to work out which digits a cell can still take, and a backtracking search that always branches on the cell with the fewest options.

This tutorial builds all three in about 90 lines of TypeScript, adds a solution counter that proves a puzzle has exactly one solution by stopping at two, and ends with a short clue-removal routine. The code was run and tested for this page, and it is original to this tutorial.

What will you build?

By the end you will have one file, solver.ts, and one test file. The solver reads a puzzle as an 81-character string, finds up to a chosen number of solutions, and tells you whether the puzzle is unique. A final function removes clues from a solved grid while keeping the puzzle unique, which is the core of how a puzzle generator works.

This is a teaching version. The site’s own engine, described in how puzzles are generated and verified unique, uses the same ideas but is more general. It handles the variants, caps the number of search steps, and keeps its data in typed arrays. The code here is written for clarity, and it is not the site’s source.

What do you need?

You need Node.js 22.18 or newer. From that version Node runs TypeScript files directly by stripping the type annotations, so node solver.ts works with no build step and no packages. The code here was checked on Node 22.22 and also passes the TypeScript compiler in strict mode. It uses only plain type annotations, which is why type stripping is enough.

Step 1: how do you represent the grid?

Use a flat array of 81 numbers, with 0 meaning an empty cell. Cell number row * 9 + col holds the digit at that row and column, counting from zero. A flat array is simple to copy, which matters because a search will try thousands of positions. The parse function turns a puzzle string, with a dot for each blank, into this array and rejects strings of the wrong length.

export type Grid = number[]; // 81 cells, 0 means empty

export function parse(text: string): Grid {
  if (text.length !== 81) throw new Error('A puzzle needs exactly 81 characters');
  return [...text].map((ch) => (ch === '.' ? 0 : Number(ch)));
}

Step 2: how do you know which cells see each other?

Two cells “see” each other when they share a row, a column or a box, and a digit placed in one rules that digit out of the other. Every cell sees exactly 20 others: eight in its row, eight in its column and four more in its box that are not already counted. Work these lists out once, when the file loads, and reuse them everywhere.

// For every cell, the 20 other cells that share its row, column or box.
const PEERS: number[][] = Array.from({ length: 81 }, (_, cell) => {
  const row = Math.floor(cell / 9);
  const col = cell % 9;
  const peers: number[] = [];
  for (let other = 0; other < 81; other++) {
    if (other === cell) continue;
    const r = Math.floor(other / 9);
    const c = other % 9;
    const sameBox = Math.floor(r / 3) === Math.floor(row / 3) && Math.floor(c / 3) === Math.floor(col / 3);
    if (r === row || c === col || sameBox) peers.push(other);
  }
  return peers;
});

The box test compares integer-divided row and column numbers: two cells are in the same box when both divide by three to the same values. This list of peers is also the only place the rules of classic Sudoku appear. To support a variant such as diagonal Sudoku, you would add the diagonal cells to the peers of cells on a diagonal, and the rest of the solver would work unchanged.

Step 3: how do you find the digits a cell can take?

A cell can hold a digit unless one of its peers already holds it. Rather than build an array of candidates for each cell, keep them in a single integer in which bit d is set when digit d is still possible. Combining the peers’ digits is then one bitwise OR per peer, and counting the result is cheap.

// Bit d of the result is set when digit d is still possible in the cell.
function candidates(grid: Grid, cell: number): number {
  let used = 0;
  for (const peer of PEERS[cell]) used |= 1 << grid[peer];
  return ~used & 0b1111111110;
}

function bitCount(mask: number): number {
  let n = 0;
  for (; mask; mask &= mask - 1) n++;
  return n;
}

The line used |= 1 << grid[peer] sets the bit for each peer’s digit. An empty peer holds 0 and sets bit 0, which is harmless, because the final mask 0b1111111110 keeps only bits 1 to 9. Inverting used and applying the mask leaves the digits nobody has taken. bitCount counts the set bits by clearing the lowest one each time round the loop.

Step 4: how does the search work?

The solver is a backtracking search with one important choice: it always branches on the empty cell with the fewest candidates. That rule is called minimum remaining values. A cell with one candidate is forced, so the search takes it with no branching, and a cell with zero candidates is a dead end that is abandoned at once. Picking the tightest cell first keeps the search tree small, even on puzzles with few clues.

// Finds up to `limit` solutions. Two are enough to tell "unique" from "not unique".
export function solve(puzzle: Grid, limit = 2): Grid[] {
  const grid = puzzle.slice();
  const solutions: Grid[] = [];
  for (let cell = 0; cell < 81; cell++) {
    if (grid[cell] && PEERS[cell].some((p) => grid[p] === grid[cell])) return solutions; // givens clash
  }
  const search = (): void => {
    let best = -1;
    let bestMask = 0;
    let bestCount = 10;
    for (let cell = 0; cell < 81; cell++) {
      if (grid[cell]) continue;
      const mask = candidates(grid, cell);
      const count = bitCount(mask);
      if (count < bestCount) {
        best = cell;
        bestMask = mask;
        bestCount = count;
        if (count <= 1) break;
      }
    }
    if (best === -1) {
      solutions.push(grid.slice());
      return;
    }
    for (let digit = 1; digit <= 9 && solutions.length < limit; digit++) {
      if (!(bestMask & (1 << digit))) continue;
      grid[best] = digit;
      search();
    }
    grid[best] = 0;
  };
  search();
  return solutions;
}

export const isUnique = (puzzle: Grid): boolean => solve(puzzle, 2).length === 1;

Several details deserve attention.

Step 5: how do you prove a puzzle is unique?

To prove a puzzle has exactly one solution you do not need to know how many it has in total. You only need to know whether the count is one. So the solver is asked for at most two solutions. If it finds two, the puzzle is not unique. If it finds one and the search then finishes without a second, the puzzle is unique. The one-line isUnique helper at the bottom of the solver does exactly this. It is the same idea the site’s verification gate applies to every stored puzzle, and the same property a 2012 computer search had to test to show that no puzzle has fewer than 17 clues, as described in how many Sudoku puzzles exist.

Step 6: how do you test it?

A solver that has never been tested against known answers is not trustworthy. The test file uses Node’s built-in test runner, so there is nothing to install. It covers the cases that matter: a known puzzle with a known solution, an empty grid where the search must stop at the limit, a puzzle built to have two solutions, clashing givens, and the clue-removal routine from the next step. The puzzle is one taken from this site’s Easy pool, and the two-solution puzzle was made by blanking the four corners of a rectangle of digits that could be swapped.

import { test } from 'node:test';
import assert from 'node:assert/strict';
import { carve, isUnique, mulberry32, parse, solve } from './solver.ts';

const PUZZLE = '46....2...53.14..77....6.39.....7.9.8....2.5.53..6......5.4..71.4..8.9...9.....4.';
const SOLUTION = '468973215953214687712856439124537896876492153539168724285649371341785962697321548';
const TWO_SOLUTIONS = '4689..2159532146877128564391245..896876492153539168724285649371341785962697321548';

test('solves a puzzle and finds exactly one solution', () => {
  const found = solve(parse(PUZZLE));
  assert.equal(found.length, 1);
  assert.equal(found[0].join(''), SOLUTION);
});

test('stops at the limit on a grid with many solutions', () => {
  assert.equal(solve(new Array(81).fill(0), 2).length, 2);
});

test('detects a puzzle with two solutions', () => {
  assert.equal(solve(parse(TWO_SOLUTIONS), 5).length, 2);
  assert.equal(isUnique(parse(TWO_SOLUTIONS)), false);
});

test('rejects givens that clash', () => {
  const clash = parse(PUZZLE);
  clash[2] = 4; // a second 4 in row 1
  assert.equal(solve(clash).length, 0);
});

test('carve keeps the puzzle unique, removes clues, and is repeatable', () => {
  const a = carve(parse(SOLUTION), mulberry32(7));
  const b = carve(parse(SOLUTION), mulberry32(7));
  assert.deepEqual(a, b);
  assert.ok(isUnique(a));
  assert.ok(a.filter(Boolean).length < 40);
});

Run the tests with node --test solver.test.ts. On Node 22.22 all five pass. If you change the solver, run them again, since an error in a solver tends to show up as a wrong count and not as a crash.

Step 7: how do you turn a solver into a generator?

A generator needs the solver for one job: deciding whether a clue can be removed. The routine below starts from a solved grid, visits the cells in random order, blanks each one and puts it back if the puzzle is no longer unique. It uses a small seeded random number generator, so a given seed always produces the same puzzle, which is what makes generation testable.

// Small seeded generator so the same seed always gives the same shuffle.
export function mulberry32(seed: number): () => number {
  let a = seed >>> 0;
  return () => {
    a = (a + 0x6d2b79f5) >>> 0;
    let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

// Blank cells in random order, keeping each removal only if the puzzle stays unique.
export function carve(solution: Grid, random: () => number): Grid {
  const puzzle = solution.slice();
  const order = Array.from({ length: 81 }, (_, i) => i);
  for (let i = 80; i > 0; i--) {
    const j = Math.floor(random() * (i + 1));
    [order[i], order[j]] = [order[j], order[i]];
  }
  for (const cell of order) {
    const kept = puzzle[cell];
    puzzle[cell] = 0;
    if (!isUnique(puzzle)) puzzle[cell] = kept;
  }
  return puzzle;
}

Starting from the solution of the puzzle used in this tutorial with seed 7, the routine produced a unique puzzle with 24 clues. That is in line with the 21 to 30 clues found in the site’s classic pools, but the comparison is loose, because this routine grades nothing and aims for no particular level. A real generator also builds a fresh random solution each time, and grades what it makes with a technique solver, as in how Sudoku difficulty is graded.

What are the common bugs when writing your own?

What does this solver leave out?

It does not explain itself. It finds the answer by trying digits and backing out, which is different from the way a person solves, and it cannot tell you why a move is right. It has no notion of difficulty either, since a puzzle that needs advanced reasoning from a human may be trivial for a search. That gap is the reason this site builds a second solver, the technique engine, that applies the named techniques in order. The grading guide describes it, and the frequency guide shows what it found across the site’s puzzles.

How fast is it?

On the machine used to check this tutorial, solving the example puzzle took about 0.17 milliseconds on average over 100 runs, and the first call took longer, around 9 milliseconds, while the engine warmed up. Asking for two solutions of an empty grid took under 3 milliseconds. These figures depend on your hardware and on the puzzle, and puzzles with few clues and no easy moves can be much slower. They are measurements of this code only, and they are not a benchmark of the site.

The site never runs a search like this in your browser while you play. Puzzles are generated and checked offline and shipped as data, because a hard search on a phone could freeze the page.

Where can you take it next?

More tutorials are on the guides hub.