DEV Community

SEN LLC
SEN LLC

Posted on

Building a Sudoku Puzzle Game With Constraint Propagation, Backtracking, and a Hint Engine That Fell Out For Free

#javascript #webdev #gamedev #algorithms

Building a Sudoku Puzzle Game With Constraint Propagation, Backtracking, and a Hint Engine That Fell Out For Free

Sudoku's rules fit in one sentence, but implementing a solver opens the door to constraint satisfaction, and once you have a solver, a hint engine is almost free. Here's a zero-dependency puzzle game with puzzle generation, three difficulty levels, and human-style hints โ€” all built on pure functions.

This is entry #33 in my SEN portfolio series. The goal: a playable Sudoku with generated puzzles, real-time conflict highlighting, a hint system that explains solving techniques in plain language, and confetti when you win.

๐Ÿ”— Live demo: https://sen.ltd/portfolio/sudoku/
๐Ÿ“ฆ GitHub: https://github.com/sen-ltd/sudoku

Screenshot

  • Three difficulty levels (Easy / Medium / Hard) with auto-generated puzzles
  • Keyboard navigation + number pad
  • Real-time conflict highlighting
  • Hint button detecting Naked Single, Hidden Single, and Pointing Pair techniques
  • Confetti animation + timer on completion
  • Bilingual UI (Japanese / English)
  • Zero dependencies, no build step

Constraint propagation: prune before you search

A brute-force sudoku solver faces 9^81 possibilities. But "eliminate digits that already appear in the same row, column, or box" collapses the search space dramatically.

export function candidates(board) {
  const cands = new Array(81);
  for (let i = 0; i < 81; i++) {
    if (board[i] !== 0) {
      cands[i] = null;
      continue;
    }
    const possible = new Set([1, 2, 3, 4, 5, 6, 7, 8, 9]);
    for (const p of PEERS_CACHE[i]) {
      possible.delete(board[p]);
    }
    cands[i] = possible;
  }
  return cands;
}
Enter fullscreen mode Exit fullscreen mode

The key optimization: cache peers (cells sharing a row, column, or box). The 81 ร— ~20 peer relationships are structural constants, computed once at startup.

Pick the cell with fewest candidates

When backtracking, choosing the cell with the minimum remaining values (MRV heuristic) is the standard trick. A cell with one candidate is determined without branching. A cell with two candidates branches at most twice.

let minIdx = -1;
let minSize = 10;
for (let i = 0; i < 81; i++) {
  if (cands[i] && cands[i].size < minSize) {
    minSize = cands[i].size;
    minIdx = i;
  }
}
Enter fullscreen mode Exit fullscreen mode

This alone makes medium-difficulty puzzles solve near-instantly.

Puzzle generation: build a complete board, then carve

The generator strategy is straightforward:

  1. Fill an empty board randomly using the solver's backtracker (fillBoard)
  2. Remove cells one at a time in random order
  3. After each removal, check countSolutions(puzzle, 2) โ€” if it's not 1, put the cell back
  4. Stop when the target clue count is reached 
for (const idx of indices) {
  if (clues <= targetClues) break;

  const backup = puzzle[idx];
  puzzle[idx] = 0;

  if (countSolutions(puzzle, 2) !== 1) {
    puzzle[idx] = backup;
  } else {
    clues--;
  }
}
Enter fullscreen mode Exit fullscreen mode

The max = 2 argument to countSolutions is the trick โ€” "stop as soon as you find a second solution." We only need to know if the solution is unique, not enumerate all of them.

Difficulty is controlled by clue count:

Difficulty Clues
Easy 36โ€“42
Medium 28โ€“35
Hard 22โ€“27

The hint engine falls out of the solver for free

Since candidates() already returns the candidate set for every cell, the hint engine just needs to describe patterns in those candidates in human-readable terms.

Naked Single โ€” a cell with exactly one candidate:

function findNakedSingle(board) {
  const cands = candidates(board);
  for (let i = 0; i < 81; i++) {
    if (cands[i] && cands[i].size === 1) {
      const value = [...cands[i]][0];
      return {
        technique: 'naked-single',
        cell: i,
        value,
        message: {
          ja: `่กŒ${r}ๅˆ—${c}ใฏๅ€™่ฃœใŒ ${value} ใฎ1ใคใ ใ‘ใงใ™๏ผˆNaked Single๏ผ‰`,
          en: `Row ${r}, Col ${c} has only one candidate: ${value} (Naked Single)`,
        },
      };
    }
  }
  return null;
}
Enter fullscreen mode Exit fullscreen mode

Hidden Single โ€” a digit that can only go in one place within a unit (row, column, or box).

Pointing Pair โ€” when a digit within a box is confined to a single row or column, it can be eliminated from the rest of that row or column.

The three techniques are tried in priority order; the first hit is returned:

export function nextHint(board) {
  return findNakedSingle(board)
    || findHiddenSingle(board)
    || findPointingPair(board)
    || null;
}
Enter fullscreen mode Exit fullscreen mode

Because the hint engine is built on the solver's candidates(), there's almost no duplicated logic.

Conflict highlighting is O(n) thanks to peer caching

When the player places a digit, cells sharing the same row/column/box that already contain that digit light up red. With the peer cache, checking each cell is O(20) = O(1):

export function conflicts(board, index, value) {
  const result = [];
  if (value === 0) return result;
  for (const p of PEERS_CACHE[index]) {
    if (board[p] === value) result.push(p);
  }
  return result;
}
Enter fullscreen mode Exit fullscreen mode

Checking all 81 cells costs 81 ร— 20 = 1,620 comparisons. No need for anything clever.

Why a flat array instead of a 2D grid

The board is board[i] (81-element flat array) rather than board[row][col]:

  • Copying is one call: board.slice() vs. board.map(r => r.slice())
  • Index math is cheap: row = (i / 9) | 0, col = i % 9
  • Passing data is simple: generator, UI, and solver all share the same format

2D is more readable for board[r][c], but flat wins on performance and ergonomics when you're constantly slicing, iterating, and passing boards between modules.

Tests 

npm test
Enter fullscreen mode Exit fullscreen mode

44 cases on node --test, all passing:

  • solver (22 tests): row/col/box math, peer computation, candidate generation, validation, solving, unique/multiple solution counting
  • generator (11 tests): complete board validity, clue count ranges per difficulty, unique-solution guarantee, difficulty rating
  • hints (11 tests): Naked Single/Hidden Single detection, message content, consistency with the solution

Everything is pure functions โ€” no DOM, no timers, no mocks. Just input-output equality checks.

Series

This is entry #33 in my 100+ public portfolio series.

Constraint propagation + backtracking isn't sudoku-specific โ€” it generalizes to any constraint satisfaction problem: scheduling, graph coloring, crossword generation. Sudoku just happens to have the simplest rules, making it the best entry point for exploring CSP techniques hands-on.

Top comments (0)