The Hidato Number Maze

Image by Onur Kurt from Unsplash

Hidato (also known as Hidoku) is a popular logic puzzle invented by Israeli mathematician Dr. Gyora Benedek. At first glance, it might remind you of Sudoku or a number maze, but its core dynamic relies on constructing a continuous path through a grid.

The challenge is to fill a $9 \times 9$ board with consecutive numbers from 1 to 81 such that each number is an immediate neighbor of the next—horizontally, vertically, or diagonally.

Given a board of dimensions $R \times C$ (in our case $9 \times 9$, with $N=F \cdot C=81$ cells) where some cells already contain fixed initial values, we must determine the placement of the remaining numbers while satisfying the following rules:

Number range: Each cell must contain a unique integer belonging to the set ${1, 2, \dots, N}$.
8-neighbor connectivity: Two consecutive numbers $k$ and $k+1$ must be placed in adjacent cells horizontally, vertically, or diagonally (Chebyshev distance equal to 1).
Initial clues: Pre-filled numbers on the starting board must strictly remain in their original positions.
Uniqueness: Each cell contains exactly one number, and each number appears on the board exactly once.

The key question we need to answer is: Is there a valid assignment of positions for the entire sequence from 1 to 81, and how can we find it automatically?

Consider the following example:

Do you dare to solve it logically before taking on the model?

This logic game can be formulated elegantly and systematically as a Binary Linear Optimization problem. Care to give it a try?

To model Hidato as a binary linear optimization problem, we represent the placement of each number on the board using three-indexed binary variables: vertical position, horizontal position, and the assigned numerical value.

Index sets

$\mathcal{I} = \{1, 2, \dots, R\}$: Board rows.

$\mathcal{J} = \{1, 2, \dots, C\}$: Board columns.

$\mathcal{K} = \{1, 2, \dots, N = R \times C\}$: Sequence of consecutive numbers to place.

$\mathcal{N}(i,j) = \{(r,c) \in \mathcal{I} \times \mathcal{J} : (r,c) \neq (i,j), \; |r-i| \leqslant 1, \; |c-j| \leqslant 1\}$: Set of adjacent cells (8-neighbor neighborhood) to cell $(i,j)$.

Parameters

$F_{ijk} = 1$ if cell $(i,j)$ has number $k$ fixed as an initial clue, and $0$ otherwise.

Decision variables

$x_{ijk} = 1$ if cell $(i,j) \in \mathcal{I} \times \mathcal{J}$ contains number $k \in \mathcal{K}$, and $0$ otherwise.

Since this is a feasibility problem (finding any configuration that satisfies all the game rules), the objective function is arbitrary:

Objective function
\[\min z = 0\]

We define Hidato’s rules as linear constraints:

Unique assignment per cell:

Each cell on the board must contain exactly one number:
\[\sum_{k \in \mathcal{K}} x_{ijk} = 1 \quad \forall i \in \mathcal{I}, \; \forall j \in \mathcal{J}\]

Unique assignment per number:

Each number in the sequence must appear in exactly one cell:
\[\sum_{i \in \mathcal{I}} \sum_{j \in \mathcal{J}} x_{ijk} = 1 \quad \forall k \in \mathcal{K}\]

Fixed initial clues:

We enforce the pre-filled numbers at their specified positions:
\[x_{ijk} = 1 \quad \forall (i,j,k) : F_{ijk} = 1\]

Consecutive adjacency (8-neighbor connectivity):

If cell $(i,j)$ contains number $k$, number $k+1$ must be placed in one of the adjacent cells to $(i,j)$:
\[x_{ijk} \leqslant \sum_{(r,c) \in \mathcal{N}(i,j)} x_{r,c,k+1} \quad \forall i \in \mathcal{I}, \; \forall j \in \mathcal{J}, \; \forall k \in \{1, 2, \dots, N-1\}\]

Variable domain
\[x_{ijk} \in \{0, 1\} \quad \forall i \in \mathcal{I}, \; \forall j \in \mathcal{J}, \; \forall k \in \mathcal{K}\]

Source code

The Python implementation using the Gurobipy library to solve this optimization problem is available on GitHub.

GitHub Repository: fjmartincampo/Hidato

Want to keep exploring the world of Operations Research? Discover more posts on this topic here.

Puzzle solution

Source code

Enjoy Reading This Article?