How Many Loops Can You Slither Around?

This Week's Fiddler

Since Nikoli can only travel orthogonally and cannot revisit points (except to complete the loop) or re-traverse edges, and because a unique loop is defined to be its set of path segments (i.e., traversing backwards does not count, and starting from a different point does not count), we can reduce the problem to be picking a subset of squares in the 3x3 grid of squares. Within this subset, all squares must be well-connected (each square must connect to any other square), and there can be no "square holes" formed.

We could manually count ways to pick subsets of squares of varying sizes (and I had a lot of fun doing this at first, especially once I got to the Tetris tetrominoes!), but I decided that programming it would make the Extra Credit easier.

I decided to enumerate and iterate through all possible subsets of squares, flood-filling from inside the loop to check for continuity and flood-filling outside the loop to check against holes.

🍝 SPAGHETTI CODE ALERT 🍝 ...going to blame having covid for this one :,)

from collections import Counter, deque
from itertools import chain, combinations
from typing import Iterable, TypeVar


R, C = 3, 3
U = [(r, c) for r in range(R) for c in range(C)]
D = ((-1, 0), (0, 1), (1, 0), (0, -1))

T = TypeVar("T")


def powerset(iterable: Iterable[T]):
    return map(
        set, chain.from_iterable(combinations(iterable, k) for k in range(1, R * C + 1))
    )


def generate_neighbors(r: int, c: int, allow_border=False):
    for dr, dc in D:
        rr = r + dr
        cc = c + dc
        L = -allow_border
        UR = R + allow_border
        UC = C + allow_border
        if rr < L or rr >= UR or cc < L or cc >= UC:
            continue
        yield (rr, cc)


valid: list[set[tuple[int, int]]] = []
# S is the set of squares to include
for S in powerset(U):
    # Flood fill to ensure that all squares in S are connected
    seen = {min(S)}
    q = deque(seen)
    while len(seen) < len(S) and len(q):
        r, c = q.popleft()
        for neighbor in generate_neighbors(r, c):
            if neighbor not in S or neighbor in seen:
                continue
            seen.add(neighbor)
            q.append(neighbor)
    if seen == S:
        # Flood fill from the outside to ensure that there are no holes
        start = (-1, -1)
        seen.add(start)
        q: deque[tuple[int, int]] = deque([start])
        target = (R + 2) * (C + 2)
        while len(seen) < target and len(q):
            r, c = q.popleft()
            for neighbor in generate_neighbors(r, c, True):
                if neighbor in S or neighbor in seen:
                    continue
                seen.add(neighbor)
                q.append(neighbor)
        if len(seen) == target:
            # If all squares are connected without holes, S is valid
            valid.append(S)

print(len(valid))

I originally had a bug where I forgot to exclude loops with "holes", so I originally got 218. But after factoring in that bug with a second flood fill, it took out the 5 loops with holes in them, giving me the answer of 213. Hopefully that was the last of the bugs :)

Answer: 213

Extra Credit

Now that we have all possible loops, this part becomes a bit more straightforward.

For each valid loop, we want to generate a list of valid puzzles, which first involves finding the number of walls for each square. For squares outside the loop, we count a wall for every neighbor that is in the loop. For squares inside the loop, we count a wall for every neighbor that is out of the loop PLUS any borders we touch (e.g., if we're on the top left, we have two walls that are on the border).

Consider the "trivial puzzle", where every square has a defined number. This is trivial because we know for sure it corresponds to a unique loop. Any indexed subset of the trivial puzzle is considered a potential puzzle for this loop. We then just cache this puzzle into a counter.

In the end, we go through the counter and count the number of entries that have exactly one corresponding loop. For example, a puzzle consisting of no wall constraints will correspond to every loop and is thus not counted.

# Continue code from above
...

counter = Counter()
for S in valid:
    vals: list[int] = []
    for r in range(R):
        for c in range(C):
            vals.append(0)
            # For squares in the loop, factor in border walls
            if (r, c) in S:
                vals[-1] = (r == 0) + (r == R - 1) + (c == 0) + (c == C - 1)
            # Factor in other walls
            for rr, cc in generate_neighbors(r, c):
                vals[-1] += ((r, c) in S) != ((rr, cc) in S)
    counter.update(
        # 1-1 mapping to a puzzle configuration
        tuple(v if i in mask else None for i, v in enumerate(vals))
        for mask in powerset(range(R * C))
    )

print(sum(x == 1 for x in counter.values()))

Answer: 41433