Image by Kjell-Jostein Sivertsen retrieved from Unsplash
Hashi (short for Hashiwokakero, which means building bridges) is a popular logic puzzle played on a rectangular grid featuring islands represented by numbered circles. The goal of the game is to connect all the islands using bridges while satisfying a set of formal constraints:
Alignment: Bridges can only be drawn horizontally or vertically between islands aligned in the same row or column, with no other islands in between.
Connection capacity: At most two bridges can be built between any pair of neighboring islands.
No intersection: Bridges cannot cross each other.
Fixed degree: Each island must have a total number of connected bridges exactly equal to the number indicated inside it.
Single connected network: All islands must end up connected within a single connected component (a continuous transportation network).
Below is an example of a Hashi board consisting of $52$ islands:
Would you like to try connecting the islands logically before checking the solution and the optimization model formulation?
Challenge solution
The complete network of bridges that solves the board above is given by:
The Hashi puzzle can be formulated as a mixed-integer linear programming model using a network flow approach to guarantee full connectivity.
To structure the model mathematically, we represent the islands as a set of vertices and the potential connections between adjacent islands as edges.
Index sets
\(\mathcal{V} = \{1, \dots, N\}\): Set of islands on the board.
\(\mathcal{E} = \{(i,j) : i < j\}\): Set of valid segments (without intermediate islands) between horizontally or vertically aligned islands.
\(\mathcal{C}\): Set of pairs of perpendicular segments that intersect in the grid space, i.e., $((i,j), (k,l)) \in \mathcal{C}$.
Parameters
\(d_i\): Numerical degree fixed inside island $i \in \mathcal{V}$.
\(N\): Total number of islands ($N = \vert{}\mathcal{V}\vert{}$).
Decision variables
\(x_{ij} \in \{0, 1, 2\}\): Number of bridges built on segment $(i,j) \in \mathcal{E}$.
\(y_{ij} \in \{0, 1\}\): Binary variable equal to $1$ if at least one bridge exists between $i$ and $j$, and $0$ otherwise.
\(f_{ij} \geqslant 0, \; f_{ji} \geqslant 0\): Directed auxiliary flow circulating between $i$ and $j$ to ensure network connectivity.
Since this is a mathematical feasibility problem, the objective function is arbitrary:
Objective function
\[\min z = 0\]
We define the formal constraints of the model below:
Global network connectivity (Single-Commodity Flow Model):
We fix a root island (for instance, island $1$). The root island acts as a source demanding $N - 1$ units of flow that it distributes to the remaining $N - 1$ islands on the board:
Want to keep exploring the world of Operations Research? Discover more posts on the topic here.
If you found this useful, please cite this as:
Martín-Campo, F. Javier (Jul 2026). Building bridges with linear optimization, the Hashi puzzle. https://www.fjmartincampo.com/blog/2026/hashi/.
or as a BibTeX entry:
@misc{martín-campo2026building-bridges-with-linear-optimization-the-hashi-puzzle,title={Building bridges with linear optimization, the Hashi puzzle},author={Martín-Campo, F. Javier},year={2026},month={Jul},url={https://www.fjmartincampo.com/blog/2026/hashi/}}
Enjoy Reading This Article?
Here are some more articles you might like to read next:
