Building a Hamiltonian Path Puzzle
Number Trail is a path-filling puzzle built entirely in plain HTML, CSS, and a single JavaScript module with no frameworks and no bundler. The player draws one continuous path that visits every cell of a square grid exactly once, touching numbered clue cells in ascending order.
The core constraint is a Hamiltonian path problem: find a path through a graph that visits every vertex exactly once. The numbered clues force the path through fixed waypoints in a fixed sequence, which dramatically shrinks the search space and makes the puzzle tractable.
This post walks through the full implementation: puzzle file format, board rendering, wall gradients, drag interaction, path validation, and random puzzle generation with Warnsdorff’s heuristic.
Deciding whether a Hamiltonian path exists in a given graph is NP-complete. Richard Karp listed it among his 21 NP-complete problems in 1972. This means no polynomial-time algorithm is known for the general case, and all known exact solvers scale exponentially in the worst case.
A grid graph places vertices at integer coordinates (i, j) and connects horizontally and vertically adjacent pairs with edges. A full rectangular grid always has a Hamiltonian path: traverse the first row left to right, the second right to left, and alternate direction for each subsequent row. This is known as boustrophedon (snake) traversal and is the fallback in the puzzle generator.