How Many Loops Can You Slither Around?

Nikoli the snake wants to slither along a loop through a four-by-four grid of points. To form a loop, Nikoli can join any two horizontally or vertically adjacent points with a line segment. Nikoli has standards: the loop may never cross over itself, no two corners of the loop may meet at the same point, and once a segment between two points has been used it cannot be used again, in either direction. How many different loops can Nikoli make? (A loop travelled in the two directions counts once.)

The Fiddler, Zach Wissner-Gross, February 9, 2024(original post)

The official solution appeared in the post of February 16, 2024 and gives $213$ loops, agreeing with the answer below. The Extra Credit half of that post is paywalled, so the count of $41{,}433$ puzzles is my own.

Solution

Nikoli’s three rules say one thing between them: the loop is a single closed path along the grid lines that never visits a point twice. Crossing itself, touching itself at a corner and reusing a segment all require some point to be visited a second time, and a closed path that visits no point twice does none of them.

Such a path is hard to count directly, because it can wander. The idea that makes it easy is to stop looking at the path and look at what it fences in. A closed path on the grid lines encloses a set of the nine unit squares, and the path is exactly the boundary of that set. So each loop corresponds to one set of squares, and different loops enclose different sets. The question becomes: for which sets of squares is the boundary a single loop of the allowed kind?

A set qualifies when its squares hang together edge to edge, it has no hole, and no two of its squares meet only at a corner with the other two squares around that point left out (that would make the boundary touch itself, as in the figure). With nine squares these conditions are easy to check by size.

• One square: any of the $9$ positions, so $9$ loops.

• Two squares: a domino lying flat in one of $3 \times 2 = 6$ places, or standing up in $6$ more, so $12$.

• Three squares: a straight piece in $3$ rows or $3$ columns, so $6$, or an L-shape, which sits in one of the four $2 \times 2$ blocks in one of $4$ orientations, so $16$. That makes $22$.

• Four squares: the $2\times 2$ square in $4$ places, the T-shape in $4$ orientations and $2$ positions each ($8$), the L-shape in $8$ orientations and $2$ positions each ($16$), and the skew shape in $4$ orientations and $2$ positions each ($8$). The straight piece of four does not fit. That makes $36$.

• Nine squares: the whole grid, $1$ loop.

• Eight squares: leave out one square. Leaving out the centre makes a hole, so the missing square is one of the other $8$, giving $8$ loops.

• Seven squares: leave out two. If the centre is one of them, the other must be next to it (otherwise the centre is a hole), giving $4$. If both are outer squares, the centre keeps the rest joined up, and the only way to go wrong is to strand a corner square: removing the two edge squares on either side of the same corner cuts that corner off. That rules out $4$ of the $\binom{8}{2} = 28$ pairs and leaves $24$, for $4 + 24 = 28$ in all.

The sets of five and six squares are counted the same way but with many more shapes, and the computation below does that bookkeeping: $49$ and $48$. Adding up, $$9 + 12 + 22 + 36 + 49 + 48 + 28 + 8 + 1 = 213 ,$$ $$\boxed{\ 213 \text{ loops}. \ }$$

The computation

The program does not use the squares at all. It encodes the puzzle as stated: the sixteen points, the segments between neighbours, and a loop as a closed path that never revisits a point. It grows every such path from its smallest point (in a fixed order), so each loop is found starting there, once in each direction, and a set of edge sets removes the duplicate direction. For each loop it also measures the enclosed area with the shoelace formula, which gives the table by size.

from itertools import product
from collections import Counter

pts = list(product(range(4), repeat=2))

def nbrs(p):
    x, y = p
    for q in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
        if q in pts:
            yield q

def area(path):
    s = 0
    for (a, b), (c, d) in zip(path, path[1:] + path[:1]):
        s += a * d - b * c
    return abs(s) // 2

loops = {}
def grow(path):
    for q in nbrs(path[-1]):
        if q == path[0] and len(path) >= 4:
            ring = zip(path, path[1:] + path[:1])
            key = frozenset(frozenset(e) for e in ring)
            loops[key] = area(path)
        elif q not in path and q > path[0]:
            grow(path + [q])

for s in pts:
    grow([s])
print("loops:", len(loops))
for k, n in sorted(Counter(loops.values()).items()):
    print(f"loops enclosing {k}: {n}")

It prints

loops: 213
loops enclosing 1: 9
loops enclosing 2: 12
loops enclosing 3: 22
loops enclosing 4: 36
loops enclosing 5: 49
loops enclosing 6: 48
loops enclosing 7: 28
loops enclosing 8: 8
loops enclosing 9: 1

The total and every entry of the table agree with the count by enclosed squares.

Extra Credit

In a Slitherlink puzzle, some of the nine spaces between grid points carry a number from $0$ to $4$: how many of the four sides of that space the loop uses. The solver must draw the loop. How many distinct Slitherlink puzzles can be made on the four-by-four grid of points, where a puzzle is a placement of numbers that has exactly one loop as its solution? Different puzzles may share the same solution loop.

Solution

Every loop gives a full grid of nine numbers: for each space, the number of its sides on the loop. A puzzle shows some of these spaces and hides the rest. If its numbers are consistent with exactly one loop, they must be that loop’s numbers on the shown spaces. So every valid puzzle comes from one loop $L$ and one set $S$ of shown spaces, and the puzzle is valid exactly when no other loop has the same numbers as $L$ on every space of $S$.

Different pairs $(L, S)$ give different puzzles. Two pairs with different sets $S$ show numbers in different places. Two pairs with the same $S$ and different loops cannot both be valid and give the same numbers, since then the puzzle would have two solutions. So if $u(L)$ is the number of sets $S$ on which no other loop agrees with $L$, the number of puzzles is $$\sum_{\text{loops } L} u(L) .$$

There are $2^9 = 512$ possible sets $S$ for each of the $213$ loops, so this is a finite check with no closed form. Some features can be seen by hand. Showing all nine numbers does not always work: three pairs of loops have identical full grids of numbers, so those six loops have no puzzle at all. At the other end, the loop around a single square has the most puzzles, $402$ of the $512$ sets, because a single $4$ already pins it down. The total comes from the exact count in the computation that follows: $$\boxed{\ 41{,}433 \text{ puzzles}. \ }$$

The computation

With the loops from The computation above, the program works out each loop’s nine numbers, then counts the pairs $(L, S)$ for which no other loop matches $L$ on $S$. It also lists the full grids shared by two loops.

cells = list(product(range(3), repeat=2))

def sides(c):
    x, y = c
    return [frozenset(e) for e in (
        ((x, y), (x+1, y)), ((x, y+1), (x+1, y+1)),
        ((x, y), (x, y+1)), ((x+1, y), (x+1, y+1)))]

grids = [tuple(sum(e in L for e in sides(c)) for c in cells)
         for L in loops]

def unique(i, shown):
    return not any(j != i and all(g[k] == grids[i][k]
                                  for k in shown)
                   for j, g in enumerate(grids))

total = 0
for i in range(len(grids)):
    for mask in range(512):
        shown = [k for k in range(9) if mask >> k & 1]
        total += unique(i, shown)
print("puzzles:", total)
shared = Counter(grids)
print("shared full grids:", sum(n > 1 for n in shared.values()))

It prints

puzzles: 41433
shared full grids: 3