Loop the loops - Insane

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 $4 \times 30$ rectangle.

Too difficult? Go back to the hard difficulty . Want a harder challenge? Try doing 5x30 rectangle; nothing new, though. Want an extreme challenge? Try doing a 10x10 square; I haven't solved it.

The answer is 89433609066753781838.

1 solution

Arjen Vreugdenhil
Oct 5, 2015

So the solution is $\boxed{89433609066753781838}$ .

Here is my code. However, the 'long' datatype is too small to contain the results for N > 27. I used two 'longs' for the variables s[][] and total, but that cluttered my code, so I left that out here.

My method is as follows: s[n][x] keeps track of the number of patterns of length n starting with column of type x. The values of x are defined as follows:

x = 0, 1, 2: The loop includes the top, middle, bottom 1/3 of the column.
x = 3, 4: The loop includes the top, bottom 2/3 of the column.
x = 5: The loop includes the entire column.
x = 6, 7: The loop includes both the top and the bottom of the column. The difference is, that x = 6 if the pattern is closed toward the right, and x = 7 if the pattern is not closed.

Patterns starting with x = 6 are valid, but run the risk of including "islands", which is not allowed in a loop. Patterns starting with x = 7 are not (yet) valid because the top and bottom are disconnect, but they may be used to grow longer patterns. In the final total, we exclude the patterns with x = 7.

The array stitch[x from][x to] describes which kinds of column may be legitimately combined with each other. The array is symmetric except for the last two rows/columns, which are designed to prevent both islands and disconnected shapes.

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

int stitch[][] = { { 1, 0, 0, 1, 0, 1, 1, 0 },
                   { 0, 1, 0, 1, 1, 1, 0, 0 },
                   { 0, 0, 1, 0, 1, 1, 1, 0 },
                   { 1, 1, 0, 1, 1, 1, 0, 0 }, 
                   { 0, 1, 1, 1, 1, 1, 0, 0 }, 
                   { 1, 1, 1, 1, 1, 1, 0, 1 },
                   { 0, 0, 0, 0, 0, 1, 1, 0 },
                   { 1, 0, 1, 0, 0, 0, 0, 1 } };

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

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

        for (int dd = 0; dd < 8; dd++) if (stitch[d][dd] > 0)
            s[n][d] += s[n-1][dd];
    }

long total = 0;

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

out.println(total);

As for the "extreme" challenge, 10x10: I think I found a solution that produces results in a reasonable amount of time. Have to code it yet. Maybe I'll post it in a few days.

Arjen Vreugdenhil - 5 years, 8 months ago

Loop the loops - Insane

Too difficult? Go back to the hard difficulty . Want a harder challenge? Try doing 5x30 rectangle; nothing new, though. Want an extreme challenge? Try doing a 10x10 square; I haven't solved it.

The answer is 89433609066753781838.

1 solution

0 pending reports