Chapter 9

Slitherlink

Slitherlink draws a single closed loop on a lattice of dots. The grid is a rectangle of cells; some cells carry a small clue digit between $0$ and $3$ . The solver’s task is to draw a non-self-crossing closed curve along the lattice edges between dots, such that for every clue cell the number of edges on the curve incident to that cell exactly equals the clue. A clue of $0$ forbids any of the cell’s four edges from being on the loop; a $3$ forces three of them on; a $1$ or $2$ leaves exactly one or two free.

The puzzle was published in $1989$ in Nikoli’s puzzle magazine under the name Suri-rinku (Japanese for “slitherlink”), designed by an editor going by the handle Renin. It travelled to the West in the late $1990$ s and is now solved by aficionados in several languages, often under the names Loop the Loop or Fences. Of all Nikoli puzzles, Slitherlink is perhaps the purest of the loop-puzzle family: the entire content of a solution is a single closed curve.

The new modelling ingredient is the curve itself. Up to this chapter the puzzles in this book have placed labels in cells. Here the unknowns live on the edges between dots, and the non-trivial constraint is that the chosen edges form a single closed loop, not two or more. CP-SAT supports this directly through its AddCircuit primitive, which lets a CP model declare that a set of directed arcs must form a Hamiltonian circuit; we use it via the standard trick that lets vertices “skip” the loop with a self-loop arc.

Rules and a small instance

A Slitherlink puzzle is an $R \times C$ rectangle of cells. Vertices sit at lattice points $(r, c)$ with $0 \le r \le R$ and $0 \le c \le C$ ; edges connect each pair of horizontally or vertically adjacent vertices. A subset of cells carries a clue: an integer from $0$ to $3$ .

Each edge is either on the loop or off.
For each clue cell, the number of its four bounding edges that are on the loop equals the clue.
The set of on-edges forms a single closed loop: a non-self-crossing closed curve on the edge graph.

Equivalently, every vertex in the lattice has degree $0$ or $2$ in the on-edge graph (degree $0$ if not on the loop, $2$ if on), and the on-edges form a single connected component.

Figure 9.1 is a $6 \times 6$ instance with eleven clues, generated and checked for uniqueness by the solver of this chapter.

*A $6 \times 6$ Slitherlink with eleven clues. Lattice dots mark the vertices; clues sit in cell interiors. The task is to thread a single closed loop along the dot lattice satisfying every clue.*

*The unique closed loop. The lone $3$ forces three of its four edges on, pinning the loop’s tightest corner; each $0$ keeps the loop entirely off that cell.*

The programming model

Let $h_{r, c}$ denote the boolean for the horizontal edge from vertex $(r, c)$ to vertex $(r, c+1)$ , and $v_{r, c}$ for the vertical edge from $(r, c)$ to $(r+1, c)$ . A cell at $(r, c)$ has bounding edges $h_{r, c}$ (top), $h_{r+1, c}$ (bottom), $v_{r, c}$ (left), and $v_{r, c+1}$ (right).

The clue constraint is direct: $h_{r, c} + h_{r+1, c} + v_{r, c} + v_{r, c+1} \;=\; \text{clue}(r, c) \quad \text{for each clue cell.}$

The vertex degree constraint, for each lattice vertex $(r, c)$ , is that the sum of its incident edges is $0$ or $2$ . CP-SAT expresses this with a Boolean indicator: a variable $\mathit{in}_{r, c}$ that is $1$ iff the vertex is on the loop, with $\sum_{e \text{ incident}} e = 2 \mathit{in}_{r, c}$ .

The single-loop constraint

The clue and degree constraints alone admit configurations with multiple disjoint loops. To rule those out, the model uses CP-SAT’s AddCircuit primitive. The trick: turn each undirected edge into two directed arcs (one per direction); add a self-loop arc at every vertex that is enabled iff the vertex is off the loop; then AddCircuit on the union of arcs forces the active set to be a single Hamiltonian circuit on the vertex set, where “Hamiltonian” visits every vertex but uses the self-loop for vertices not on the actual loop.

Concretely, for each undirected edge $\{u, v\}$ we introduce two arc booleans $a_{u \to v}$ and $a_{v \to u}$ with the constraint $a_{u \to v} + a_{v \to u} = e_{uv}$ , so exactly one is true when the edge is on the loop, and both are false otherwise. For each vertex $w$ we introduce a self-loop arc $s_w$ with the constraint $s_w = 1$ iff vertex $w$ has degree $0$ in the loop. AddCircuit on the resulting arc list does the rest.

A solver in forty lines

from ortools.sat.python import cp_model

def solve_slitherlink(R, C, clues):
    """clues: {(r, c): k} for clued cells, k in 0..3."""
    m = cp_model.CpModel()
    h = {(r, c): m.NewBoolVar("")
         for r in range(R+1) for c in range(C)}
    v = {(r, c): m.NewBoolVar("")
         for r in range(R) for c in range(C+1)}
    for (r, c), k in clues.items():
        m.Add(h[(r, c)] + h[(r+1, c)]
              + v[(r, c)] + v[(r, c+1)] == k)

    arcs = []
    vid = lambda r, c: r * (C+1) + c
    for (r, c), e in h.items():
        f = m.NewBoolVar(""); b = m.NewBoolVar("")
        m.Add(f + b == e)
        arcs.append((vid(r, c), vid(r, c+1), f))
        arcs.append((vid(r, c+1), vid(r, c), b))
    for (r, c), e in v.items():
        f = m.NewBoolVar(""); b = m.NewBoolVar("")
        m.Add(f + b == e)
        arcs.append((vid(r, c), vid(r+1, c), f))
        arcs.append((vid(r+1, c), vid(r, c), b))
    for r in range(R+1):
        for c in range(C+1):
            edges = []
            if c > 0: edges.append(h[(r, c-1)])
            if c < C: edges.append(h[(r, c)])
            if r > 0: edges.append(v[(r-1, c)])
            if r < R: edges.append(v[(r, c)])
            d = sum(edges)
            sl = m.NewBoolVar("")
            m.Add(d == 0).OnlyEnforceIf(sl)
            m.Add(d == 2).OnlyEnforceIf(sl.Not())
            arcs.append((vid(r, c), vid(r, c), sl))
    m.AddCircuit(arcs)

    s = cp_model.CpSolver()
    s.Solve(m)
    return ({(r, c): s.Value(h[(r, c)]) for (r, c) in h},
            {(r, c): s.Value(v[(r, c)]) for (r, c) in v})

The toy of Figure 9.1 solves in about $5$ milliseconds.

A hard instance

Figure 9.3 is a $10 \times 10$ instance, again generated and checked for uniqueness by this chapter’s solver. Thirty-five clues sit on $100$ cells, a little over a third; the loop must thread $66$ edges through the lattice without intersecting itself. The same solver code returns the unique loop in a few milliseconds.

*A $10 \times 10$ Slitherlink with thirty-five clues, generated and verified unique by this chapter’s solver.*

*The unique closed loop. It satisfies every clue cell and visits no vertex more than once.*

Sources. Slitherlink was first published by Nikoli in $1989$ in the magazine Puzzle Communication Nikoli under the Japanese name Suri-rinku, attributed to the editor Renin. The puzzle is also known in English as Loop the Loop or Fences. The toy and hard instances shown here were generated and checked for a unique solution by the AddCircuit model of this chapter. The AddCircuit-with-self-loops technique used in the model is documented in the OR-Tools reference and is the standard CP modelling trick for connectivity-with-skip on undirected graphs.