Hashiwokakero

Hashiwokakero is the puzzle of bridges between islands. An archipelago of circular islands sits on a grid; each island carries a small integer in its centre. The solver’s task is to draw a network of straight horizontal and vertical bridges between islands such that each island has exactly the declared number of incident bridges, no two bridges cross, between any two islands lies at most a double bridge, and the resulting network is connected: any island can be reached from any other by following bridges.

The puzzle was first published in $1990$ in Nikoli’s magazine Puzzle Communication Nikoli, designed by editor Yamamoto. The Japanese name, hashi-wo-kakero, means “build bridges”; in English-language sources the puzzle goes by Hashi or Bridges. It joins the family of graph-style Nikoli puzzles whose solutions are determined by local degree counts and a global connectivity condition; in this respect it is a close cousin of Slitherlink, with islands replacing lattice corners and bridges replacing loop edges.

The model has three constraint families: a local degree equation per island, a no-crossing constraint per intersecting pair of candidate bridges, and a single-component connectivity constraint enforced through a flow on the candidate-bridge graph.

Rules and a small instance

A Hashiwokakero puzzle is an $R \times C$ grid with a set of islands, each at a cell $(r, c)$ and carrying a positive integer degree $d_{r,c} \in \{1, \ldots, 8\}$. A bridge is a pair of horizontally or vertically aligned islands with no other island between them, plus a number of parallel lines connecting them: $0$, $1$, or $2$. The puzzle’s constraints:

1. Each island’s incident bridge total equals its degree.

2. No two bridges cross: a horizontal bridge and a vertical bridge whose lines intersect cannot both have positive count.

3. The graph of islands joined by positive-count bridges is connected.

Figure 10.1 is a small constructed instance with nine islands on a $7 \times 7$ grid, arranged on a coarse $3 \times 3$ lattice. The three islands along the top each have degree $1$; the six islands across the middle and bottom carry larger degrees, with the centre island demanding $4$ incident bridges. Several of the demands can only be met by double bridges, so the solver must decide not just where bridges go but how many run between each connected pair.

The programming model

For each pair of islands $(p, q)$ that lie in the same row or column with no other island between them, introduce an integer variable $b_{p, q} \in \{0, 1, 2\}$ counting the bridges on that pair. Call this set of pairs $E$.

The degree constraint is one equation per island: $$\sum_{q : (p, q) \in E} b_{p, q} \;+\; \sum_{q : (q, p) \in E} b_{q, p} \;=\; d_p \quad \text{for every island } p.$$

The no-crossing constraint is one Boolean implication per intersecting pair $(h, v)$ where $h$ is a horizontal candidate bridge and $v$ a vertical one whose line segments cross: $$b_h \ge 1 \;\Rightarrow\; b_v = 0, \quad b_v \ge 1 \;\Rightarrow\; b_h = 0,$$ encoded by reified booleans on the strict positivity of $b_h$ and $b_v$ together with $\mathbf{1}[b_h \ge 1] + \mathbf{1}[b_v \ge 1] \le 1$.

Connectivity by flow

The degree and no-crossing constraints alone permit solutions in which the islands break into two or more disjoint bridge components, each internally consistent. To force a single component we enforce a flow network on the candidate-bridge graph. Pick one island $p_0$ as the root. For every other island $p$, the model must route one unit of flow from $p$ to $p_0$ along positive-count bridges. We aggregate these into a single signed flow $f_e$ per candidate bridge $e$: $f_e$ may range in $[-N, N]$ (where $N$ is the island count) and must vanish whenever $b_e = 0$. Conservation at each non-root island demands net incoming flow $= 1$; at the root, net incoming flow $= N - 1$.

Flow exists between every pair of islands iff the bridge graph is connected, so a satisfying flow guarantees a single component.

A solver in fifty lines

from ortools.sat.python import cp_model

def solve_hashi(R, C, islands):
    """{(r,c): degree} -> {(p,q): bridges}."""
    iso = list(islands)
    iso_set = set(iso)
    pairs = set()
    for (r, c) in iso:
        for cc in range(c+1, C):
            if (r, cc) in iso_set:
                pairs.add(((r, c), (r, cc))); break
        for rr in range(r+1, R):
            if (rr, c) in iso_set:
                pairs.add(((r, c), (rr, c))); break
    pairs = sorted(pairs)
    m = cp_model.CpModel()
    b = {p: m.NewIntVar(0, 2, "") for p in pairs}
    for (r, c), d in islands.items():
        m.Add(sum(b[p] for p in pairs if (r, c) in p) == d)
    H = [p for p in pairs if p[0][0] == p[1][0]]
    V = [p for p in pairs if p[0][1] == p[1][1]]
    for h in H:
        (r, c1), (_, c2) = h
        for v in V:
            (r1, c), (r2, _) = v
            if r1 < r < r2 and c1 < c < c2:
                bh = m.NewBoolVar(""); bv = m.NewBoolVar("")
                m.Add(b[h] >= 1).OnlyEnforceIf(bh)
                m.Add(b[h] == 0).OnlyEnforceIf(bh.Not())
                m.Add(b[v] >= 1).OnlyEnforceIf(bv)
                m.Add(b[v] == 0).OnlyEnforceIf(bv.Not())
                m.Add(bh + bv <= 1)
    N = len(iso); root = iso[0]
    f = {p: m.NewIntVar(-N, N, "") for p in pairs}
    for p in pairs:
        bp = m.NewBoolVar("")
        m.Add(b[p] >= 1).OnlyEnforceIf(bp)
        m.Add(b[p] == 0).OnlyEnforceIf(bp.Not())
        m.Add(f[p] == 0).OnlyEnforceIf(bp.Not())
    for u in iso:
        s = []
        for p in pairs:
            if p[0] == u: s.append(-f[p])
            elif p[1] == u: s.append(f[p])
        m.Add(sum(s) == (N - 1 if u == root else -1))
    sv = cp_model.CpSolver()
    sv.Solve(m)
    return {p: sv.Value(b[p])
            for p in pairs if sv.Value(b[p]) > 0}

The toy of Figure 10.1 solves in about $4$ milliseconds.

A hard instance

Figure 10.3 is puzzle $539$ from the janko.at Hashiwokakero archive, a $14 \times 14$ instance by Otto Janko graded at difficulty $7$. It carries sixty-four islands; the unique bridge network has sixty-five bridges, with several double bridges and a long-running connectivity that threads across most of the grid. The same solver code returns the solution in about $4$ milliseconds.

Sources. Hashiwokakero was first published by Nikoli in $1990$. The puzzle is also known as Hashi, Bridges, or Chopsticks. The hard instance is puzzle $539$ from the janko.at Hashiwokakero archive, by Otto Janko. The flow-based connectivity formulation is standard for network-design integer programs; for a thorough treatment of single-commodity flow as a connectivity constraint see Magnanti and Wolsey, Optimal trees, in Handbooks in Operations Research and Management Science, vol. $7$ ($1995$).