Resurfacing the rink

The machine must cover every patch of ice once and end at the drain. Reaching the drain is easy; reaching it last is the constraint.

The problem

Between sessions the ice is resurfaced. The rink is a grid of square patches. The machine enters at the gate, leaves by the drain, and moves one patch at a time up, down, left or right. Blocked patches — goal frames, benches — are off limits.

Every open patch must be resurfaced exactly once: crossing one twice churns the ice, missing one leaves a rut. A legal run starts on the gate, ends on the drain, and covers every unblocked patch once. Count the legal runs.

Input. rink — equal-length strings: G the gate, D the drain, . open ice, # blocked.

Output. How many legal runs exist.

Example.

rink = ["G..",
        "...",
        "..D"]       ->  2

Nine open patches, two runs: one sweeps column by column, the other row by row. Every other route repeats a patch or reaches the drain early.

A second example, and one with no legal run:

rink = ["G.#",
        "..#",
        "..D"]       ->  1

rink = ["G.",
        ".D"]        ->  0

The blocked column leaves a three-by-two block with the drain off its corner, and one run covers it. The two-by-two rink has none: patches alternate colour like a chessboard, so a run of four ends on the colour opposite the gate — but the diagonal drain shares it.

Constraints.

• rows * cols <= 20, every row the same length
• exactly one G, one D, any number of #

Hints

Approach

Brute force

Try every ordering of the open patches: the first must be the gate, the last the drain, consecutive entries neighbours. Twenty open patches give 20! ≈ 2.4 × 10¹⁸ orderings, nearly all rejected at the first non-adjacent pair.

The insight

Mark a patch as the machine drives on and clear it as the machine backs off, so the marks describe the route under construction rather than everything the search has touched — and count a run only at the drain with one patch outstanding.

Clearing is what separates this from a flood fill, which marks a patch once and never returns — that answers "can the drain be reached". Here the patch must be free for the sibling branch: the route that failed through it is not the one that will succeed. The outstanding count, not arrival at the drain, decides legality.

Algorithm

1. Scan the grid: find the gate, count the unblocked patches.
2. drive(r, c, left) — runs that begin by entering (r, c), with left patches to cover, this one included.
3. Off the grid, blocked or already marked: return 0.
4. On the drain: return 1 if left == 1, else 0.
5. Otherwise mark it, sum drive over the four neighbours with left - 1, clear the mark, return the sum.
6. Answer: drive(gate_row, gate_col, open_count).

Complexity

Time O(4ᵏ) where k is the number of open patches — four moves each, and the marks kill every branch that revisits; most branches close within a few steps. Space O(k) for the stack, since the marks live in the grid.

Solution

"""Resurfacing the rink — count full-coverage routes by grid backtracking."""


def solve(rink):
    rows, cols = len(rink), len(rink[0])
    ice = [list(row) for row in rink]
    gate = None
    open_patches = 0
    for r in range(rows):
        for c in range(cols):
            if ice[r][c] != "#":
                open_patches += 1
            if ice[r][c] == "G":
                gate = (r, c)

    def drive(r, c, left):
        # `left` counts the open patches not yet resurfaced, this one included,
        # so the drain closes a run only when left == 1.
        if not (0 <= r < rows and 0 <= c < cols) or ice[r][c] in "#*":
            return 0
        if ice[r][c] == "D":
            return 1 if left == 1 else 0
        was = ice[r][c]
        ice[r][c] = "*"                  # off limits for the rest of THIS route
        runs = (drive(r + 1, c, left - 1) + drive(r - 1, c, left - 1)
                + drive(r, c + 1, left - 1) + drive(r, c - 1, left - 1))
        ice[r][c] = was                  # free again for the branches to come
        return runs

    return drive(gate[0], gate[1], open_patches)

TESTS = [
    ((["G..", "...", "..D"],), 2),
    ((["G.#", "..#", "..D"],), 1),
    ((["G.", ".D"],), 0),                 # covering all four cannot end diagonally
    ((["GD"],), 1),                       # gate next to drain, nothing else to do
    ((["G#D"],), 0),                      # the drain is walled off
    ((["G.", "..", ".D"],), 1),
    ((["G...", "....", "...D"],), 4),
]

Pitfalls

• Marking a patch and never clearing it. The first dead end takes it out of play for every later route: the three-by-three rink reports 1, not 2.
• Counting a run on arrival at the drain. Without the left == 1 test every route ending there counts, finished or not: the three-by-three rink reports 12.
• Starting left at the open count minus one, since the machine already stands on the gate. The gate needs resurfacing too, so the drain test is off by one and every rink reports 0.

Variants

• Rooftop sweep — the same choose and un-choose, with no walls to close a branch early.
• Pruning — closing branches the walls have already decided.