Numbrix

Numbrix is the puzzle of Hamiltonian numbering. The grid is an $N \times N$ square in which every cell receives a distinct integer from $1$ to $N^2$. The solver must arrange the numbers so that consecutive values are orthogonally adjacent: for every $k \in \{1, 2, \ldots, N^2 - 1\}$, the cells holding $k$ and $k + 1$ share an edge (never a corner). Some cells are pre-filled as clues, typically along the border, and the solver threads the single Hamiltonian path through the grid that respects every clue.

Numbrix was introduced by Marilyn vos Savant in her Parade column in $2008$; the name is a portmanteau of “number” and “matrix.” Structurally it is a rigid cousin of the much older Hidato (also known as Hidoku) and of the sliding-tile $15$-puzzle. The defining feature is the orthogonal-only neighbour rule: unlike Hidato, which admits diagonal adjacency, Numbrix threads a strict rook’s path, and the strictness makes every clue near the corners exceptionally informative.

Among the solver-friendly puzzles in this volume, Numbrix is the first that asks the engine to reason about a permutation of $N^2$ distinct values rather than a fill of small integers. The constraint model mirrors the path-finding structure literally: each value $k$ gets a position variable, and consecutive-value positions are forced to be one unit apart in Manhattan distance.

Rules and a small instance

A Numbrix puzzle is an $N \times N$ grid of cells, some of which carry pre-filled positive-integer clues between $1$ and $N^2$. A solution assigns to every cell a distinct integer from $1$ to $N^2$ such that:

1. Every clue is preserved.

2. Every value in $\{1, 2, \ldots, N^2\}$ appears in exactly one cell.

3. For every $k \in \{1, 2, \ldots, N^2 - 1\}$, the cells holding $k$ and $k + 1$ are orthogonal neighbours (share a full edge).

Figure 24.1 is a $5 \times 5$ Numbrix with five clues at corners and at the centre, forcing a snake-shaped Hamiltonian path to thread the entire grid.

The programming model

The natural encoding inverts the usual “value per cell” framing. Instead of assigning to each cell a value, we assign to each value a position, and enforce adjacency on consecutive positions.

For each $k \in \{1, 2, \ldots, N^2\}$ let $p_k \in \{0, 1, \ldots, N^2 - 1\}$ be the linear index of the cell containing $k$, so that row $r_k = \lfloor p_k / N \rfloor$ and column $c_k = p_k \bmod N$.

Distinctness

All values occupy distinct cells: $$\operatorname{AllDifferent}(p_1, p_2, \ldots, p_{N^2}).$$

Clue preservation

For every pre-filled cell $(r, c)$ with clue $k$, $$p_k \;=\; r \cdot N + c.$$

Consecutive adjacency

For every $k \in \{1, 2, \ldots, N^2 - 1\}$, $$|r_k - r_{k + 1}| + |c_k - c_{k + 1}| \;=\; 1.$$ The Manhattan-distance-equals-one constraint is CP-SAT-native via $\texttt{AddAbsEquality}$ on each of $r_k - r_{k + 1}$ and $c_k - c_{k + 1}$, followed by a linear sum.

A solver in thirty-five lines

from ortools.sat.python import cp_model

def solve_numbrix(board):
    """board[r][c] = 0 for empty, positive int for clue.
       Fills board with a Hamiltonian numbering 1..N^2."""
    N = len(board); T = N * N
    m = cp_model.CpModel()
    pos = {k: m.NewIntVar(0, T - 1, "")
           for k in range(1, T + 1)}
    m.AddAllDifferent(list(pos.values()))
    for r in range(N):
        for c in range(N):
            if board[r][c] != 0:
                m.Add(pos[board[r][c]] == r * N + c)
    for k in range(1, T):
        r1 = m.NewIntVar(0, N - 1, "")
        c1 = m.NewIntVar(0, N - 1, "")
        r2 = m.NewIntVar(0, N - 1, "")
        c2 = m.NewIntVar(0, N - 1, "")
        m.AddDivisionEquality(r1, pos[k], N)
        m.AddModuloEquality (c1, pos[k], N)
        m.AddDivisionEquality(r2, pos[k+1], N)
        m.AddModuloEquality (c2, pos[k+1], N)
        adr = m.NewIntVar(0, N - 1, "")
        adc = m.NewIntVar(0, N - 1, "")
        m.AddAbsEquality(adr, r1 - r2)
        m.AddAbsEquality(adc, c1 - c2)
        m.Add(adr + adc == 1)
    s = cp_model.CpSolver()
    s.Solve(m)
    grid = [[0] * N for _ in range(N)]
    for k in range(1, T + 1):
        p = s.Value(pos[k])
        grid[p // N][p % N] = k
    return grid

The toy of Figure 24.1 solves uniquely in about $50$ milliseconds.

A hard instance

Figure 24.3 is a $9 \times 9$ Numbrix with clues along the perimeter and the cardinal axes, $16$ clues in total. CP-SAT returns the unique solution in about $14$ milliseconds.

Sources. Numbrix was created by Marilyn vos Savant for her Parade column in $2008$ and has since been syndicated in many English-language newspapers. The hard instance of Figure 24.3 is a classic $9 \times 9$ harvested from the Parade archive. The puzzle is closely related to Hidato (Gyora Benedek, $2008$), which relaxes the orthogonal adjacency rule to king-move adjacency; both are NP-complete to decide (Katagiri et al., $2009$), since they embed Hamiltonian-path problems. Although Numbrix is not of Japanese origin, its structural kinship to Masyu and its amenability to the same CP-SAT machinery earn it a place in this volume.