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.You can play the game here: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.The Hamiltonian path problemA Hamiltonian path in a graph is a path that visits every vertex exactly once. A Hamiltonian cycle visits every vertex and returns to the starting vertex. Both are named after William Rowan Hamilton, who studied the problem of finding such cycles on the vertices of a dodecahedron in the 1850s.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.Grid graphsA 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.Once walls are introduced, some edges are removed and the graph becomes a proper subgraph of the grid. Itai, Papadimitriou, and Szwarcfiter (1982) proved that deciding whether a Hamiltonian path exists in a grid graph with holes is NP-complete in general.[04] The puzzle sidesteps this by placing walls only on edges that are not part of the known solution path, so solvability is guaranteed by construction rather than decided at runtime.Warnsdorff’s rule and the Knight’s TourWarnsdorff’s rule originates with the Knight’s Tour: find a sequence of knight moves that visits every square of a chessboard exactly once.

The knight’s tour is itself a Hamiltonian path problem on the knight’s graph, where vertices are board squares and edges connect squares a knight move apart.H.C. von Warnsdorff described his heuristic in 1823: from the current square, always move to the unvisited square that has the fewest onward unvisited moves. The intuition is that vertices with few exits become harder to reach as the path grows, so they should be visited sooner. Delaying them risks creating isolated vertices that cannot be reached from the end of the path.The rule generalizes to any graph. At each step, rank the unvisited neighbors by their degree in the subgraph induced by all remaining unvisited vertices, then extend the path to the neighbor with the minimum degree. Ties are broken randomly to produce variety across runs.Warnsdorff’s rule is a greedy heuristic, not a complete algorithm. It can fail: on small grids or from certain start positions, it may reach a dead end with unvisited vertices remaining. The generator handles this by trying up to four corner starting positions and several random seeds before falling back to the snake path. In practice the rule succeeds on nearly all grid sizes encountered in the puzzles (5x5 through 10x10).Puzzle file formatEach puzzle is a plain-text file with three sections: metadata key-value pairs, a grid block, and a walls block.id: puzzle_042 title: Crossroads description: Eight walls. Four clues. A tight squeeze.

grid: 1 . . . . . . . . . . . . . . 3 . . . . . . . . . . . . . . . . 2 . . . . . . . . . . . . . . . 4

walls: 2,1 2,2 4,3 5,3 0,5 1,5 3,4 4,4 The grid is a space-separated square matrix. Dots are empty cells; integers are clue cells that the path must visit in ascending order. Walls are listed as pairs of adjacent row,col coordinates. A wall on 2,1 2,2 blocks movement between row 2 column 1 and row 2 column 2.This format is intentionally simple: no binary encoding, no JSON, no schema.

Puzzles can be authored in any text editor, checked into version control, and diffed line by line.ParsingThe parser is a small state machine. It reads the file line by line, switches between meta, grid, and walls modes on the section headers, and rejects anything that looks malformed before any rendering happens.for (const rawLine of text.split(/\r?\n/)) { const line = rawLine.trim(); if (!line || line.startsWith("#")) continue; // skip blank lines and comments

if (/^grid:$/i.test(line)) { section = "grid"; continue; } if (/^walls:$/i.test(line)) { section = "walls"; continue; }

if (section === "meta") { const match = line.match(/^([a-z0-9_-]+)\s*:\s*(.+)$/i); if (match) meta[match[1].toLowerCase()] = match[2].trim(); } else if (section === "grid") { gridLines.push(line); } else { wallLines.push(line); } } After collecting the lines, the grid is validated to be square and all clue numbers from 1 to max must be present and unique.

Both converge on tryVisit(cell, mode).For drag, mousedown on a cell starts a drag, then mousemove on the window calls visitPoint(clientX, clientY). That maps screen coordinates back to a grid cell:function cellFromPoint(clientX, clientY) { const rect = boardEl.getBoundingClientRect(); return { // normalize pointer to [0,1] within the board, then scale to row/column index r: Math.min(size - 1, Math.floor(((clientY - rect.top) / rect.height) * size)), c: Math.min(size - 1, Math.floor(((clientX - rect.left) / rect.width) * size)), }; } Dividing by rect.height and rect.width normalizes the pointer position to [0, 1], then multiplying by size gives the grid row and column. Clamping to size - 1 handles rare cases where the pointer is exactly on the border.Touch is handled identically via touchmove, with event.changedTouches[0] providing the coordinates.After a drag that moved at least one cell, the next click event on the cell under the pointer would otherwise double-count the final cell. The fix is a one-shot suppressClick flag:function endDrag() { if (state.dragging && state.dragMoved) { state.suppressClick = true; // defer reset past the click event that fires after mouseup window.setTimeout(() => { state.suppressClick = false; }, 0); } state.dragging = false; } The setTimeout(..., 0) defers the flag reset until after the click event fires in the same event loop turn.BacktrackingIf the user revisits a cell already in the path, tryVisit truncates rather than refusing:const existingIndex = state.path.findIndex((step) => sameCell(step, cell));

if (existingIndex !== -1) { // drag only allows one-step backtrack to prevent accidental large truncations if (mode === "click" || existingIndex === state.path.length - 2) { truncatePath(existingIndex); recomputeClueIndex(); // re-scan path to find the highest clue reached } else { setStatus("The path cannot cross itself.", "