Counting unique-loop configurations on a $3 \times n$ grid

We first claim that there can be no $3\times 3$ grid of unremoved squares in the final configuration. Assume otherwise: we now look at the number of disconnected parts of the loop that pass through the $3\times 3$ grid.

• $1$ part: The Hamiltonian path the loop takes through the $3\times 3$ grid is not unique, contradiction.
• $2$ parts: The loop satisfies one of the two configurations shown below (up to vertical/horizontal reflection). But these can be modified into each other, so the entire loop is not unique.
• $3$ parts: Each part of the loop must be a horizontal line across the $3\times 3$ grid; this is not possible.

Now we enumerate $C_t$. The only way a configuration can work is if we remove a square in each $3k$-th column, as otherwise there will be a $3\times 3$ grid. FTSOC, assume there is a removed square in the middle row. Then, if a consecutive removal is not in the middle row, then a loop is not possible (left image below); if a consecutive removal is in the middle row, then the loop is not unique, since we can swap the loop between the middle and right images below. Thus, all removed squares must be in the top or bottom rows. This leaves us with $2^t$ possibilities since there are $2$ possible removals for each of the $t$ columns. Each of these configurations work in the same manner as the $n=11$ example below, where each removed square must have the loop wrap tightly around it, and the remaining portions of the loop are fixed. Thus, $C_t=2^t$.

For $A_t$ and $B_t$, we find a recursive definition. We know the rightmost $3\times 3$ grid must contain a removed square. It's easy to check that this square cannot be on an edge or a loop isn't possible. We now do casework on where this square is:

• If it is the right-side corner, recurse to $n-1$.
  • $A_t$ reduces to $C_{t-1}$ (first image). From our classification of $C$-configurations, the rightmost edge in the must have the loop going directly from top to bottom. This means we there are $2$ possible ways to recurse, which is $2\cdot 2^{t-1}=2^t$ configurations.
  • $B_t$ reduces to $A_t$. If the $n-1$ grid has a removed right corner, which happens in $2^t$ ways, there is $1$ way to recurse (since only one corner removal yields a valid loop). Otherwise, there are $2$ ways. This gives $2A_t-2^t$ configurations.
• If it is the center, recurse to $n-3$ for $A_t$ and $n-2$ for $B_t$.
  • $A_t$ reduces to $A_{t-1}$ (second image). If the $n-3$ grid has a removed right corner, which occurs in $2^{t-1}$ ways, there is $1$ way to recurse; otherwise, the resulting loop can be checked to not be unique. This gives $2^{t-1}$ configurations.
  • $B_t$ reduces to $C_{t-1}$ (third image), which gives $2^{t-1}$ configurations.
• If it is the left-side corner, recurse to $n-3$ (fourth image).
  • $A_t$ reduces to $A_{t-1}$. If the $n-3$ case has a removed right corner, which happens in $2^{t-1}$ ways, there is $1$ way to recurse. Otherwise there are $2$. This gives $2A_{t-1}-2^{t-1}$ configurations.
  • $B_t$ reduces to $B_{t-1}$. Using the same logic, this gives $2B_{t-1}-(2A_{t-1}-2^{t-1})$ configurations.

Adding up all the cases for $A_t$ and $B_t$, we have $$A_t=2A_{t-1}+2^t$$ $$B_t=2B_{t-1}+2(A_t-A_{t-1})$$ Solving from the initial values $A_1=5$ and $B_1=13$, or just using induction, yields solutions of $A_t=(2t+3)2^{t-1}$ and $B_t=(2t^2+7t+4)2^{t-1}$, as desired.