Loop the loops - Hard

Computer Science Level 5

In the world of pencil puzzles, there are many puzzle types where you have to draw a loop on a lattice grid, including Country Road , Masyu , Pure Loop , Slalom , and Yajilin . In most of these puzzles (and all of the linked above), the loop visits some of the cells, passing through the cells' centers, and may not use a cell more than once (which also means no intersections, no touching itself, etc).

Formally, on a polyomino $P$ , a loop is a sequence of $n \ge 4$ squares $(a_1, a_2, a_3, \ldots, a_n)$ such that all squares $a_i$ are in $P$ , $a_i$ and $a_{i+1}$ share a side for all valid $i$ , $a_n$ and $a_1$ also share a side, and all squares in the loop are distinct. Loops are cyclic (it can start from any square in the loop) and don't have any orientation (reversing the loop doesn't matter), thus $(a_1, a_2, a_3, a_4), (a_2, a_3, a_4, a_1), (a_4, a_3, a_2, a_1)$ all describe the same loop.

Determine the number of loops on a $3 \times 30$ rectangle.

Too difficult? Go back to the medium difficulty . Want a harder challenge? Try the insane difficulty .

The answer is 443365544387.

2 solutions

Laurent Shorts
Apr 25, 2016

I computed values for $3\times n$ rectangles until $n=15$ and found that it was always very close to $\displaystyle \frac{(\sqrt{2}+1)^{n+2}-8n-6}{4}$ . Pluging $n=30$ in it gives 443'365'544'386.9993, rounded to 443'365'544'387.

Also, see OEIS A059020 .

Arjen Vreugdenhil
Oct 5, 2015

We consider the crossings of the grid in the interior of the rectangle. They form a rectangle of 29 x 2.

For each column of two crossings, there are only three possibilities: (0) both crossings are in the interior of the loop; (1) the top crossing is in the interior of the loop; (2) the bottom crossing is in the interior of the loop. The condition of connectivity prohibit (1) and (2) to occur next to each other. All other possibilities are allowed.

We count the possible patterns of $n$ columns wide. However, instead of adding them all together, we separate them out based on the shape of the first column. Thus, $s[5][1]$ is the number of patterns that are five columns wide and start with a column with the top crossing in the interior of the loop. This allows us to move from width $n$ to width $n+1$ while respecting the rule that columns of types (1) and (2) may not be combined. (In the code below, this is the condition $d + dd \neq 3$ .)

Example: The 17 patterns of length 3 are counted as follows:

s[3][0]: ### | ### | ##  | ### | ### | # # | #   
         ### | ##  | ### | # # | #   | ### | ###

s[3][1]: ### | ### | ##  | ### | ###
          ## |  #  |  ## |   # |     

s[3][2]:  ## |  ## |  #  |   # |     
         ### | ##  | ### | ### | ###

Finally, when placed in a rectangle of $N = 29$ columns, each pattern of $n$ columns wide can start in $N + 1 - n$ possible positions. We implement this in the last part, when determining the grand total of possible patterns.

final int N = 29;
long s[][] = new long[N+1][3];

for (int d = 0; d < 3; d++) s[1][d] = 1;

for (int n = 2; n <= N; n++)
    for (int d = 0; d < 3; d++) {
        s[n][d] = 0;

        for (int dd = 0; dd < 3; dd++) if (d + dd != 3) {
            s[n][d] += s[n-1][dd];
        }
    }

long total = 0;

for (int n = 1; n <= N; n++)
    for (int d = 0; d < 3; d++)
        total += s[n][d] * (1 + N - n);

out.println(total);

The output is the solution $\boxed{443365544387}$ .

Incidentally, running the program with N = 4 gives the solution to the "easy" loops-the-loops problem.

Loop the loops - Hard

Too difficult? Go back to the medium difficulty . Want a harder challenge? Try the insane difficulty .

The answer is 443365544387.

2 solutions

0 pending reports