Ykhjuy

QUESTION: Given an $mtimes n$ grid of squares, is a formula known for the number of closed loops that can be drawn along the perimeters of these squares? For a better description of what I mean, see the link below.

MOTIVATION: I have been considering the puzzle game "Slitherlink" in which the solution to the puzzle consists of a closed loop drawn in a square lattice grid satisfying certain constraints. So, given an $mtimes n$ grid of squares, I would like to calculate the number of closed loops that one can draw in that grid.

Does anyone know of a formula that computes this, or a quick algorithm that one can use to determine this number in terms of $m,n$? Are there any special cases that are easier to determine than others? Where can I read more about this problem?

An equivalent problem: given a graph $G$, how can one calculate the number of cyclic subgraphs it contains?

EDIT: I would like to note that OEIS mentions all largest known values are found by means of a transfer matrix method. Hence, I like to believe the algorithm I present here is asymptotically very close to the best known algorithm.

Here is an $mathcal{O}(f(n)^3log m)$ time algorithm where $f(n)=mathcal{O}(3^n/n)$. The idea is to define an $f(n)times f(n)$ transition matrix $M$ and calculate $M^m$. This takes $mathcal{O}(f(n)^3log m)$ time using the standard matrix multiplication algorithm, but can be sped up to $mathcal{O}(f(n)^{2.807}log m)$ using Strassen's algorithm. There are asymptotically faster matrix multiplication algorithms to speed this up to $mathcal{O}(f(n)^{2.373}log m)$, but don't bother with that.

Note that this means we can calculate the answer for a $5times 10^{18}$ grid in mere seconds, while the answer for a $10times10$ grid would take forever. Pretty funny, if you ask me :) This does assume that multiplication is a constant time operation, which is far from true with such big numbers, unless you only want to know the last few digits of the answer.

So the idea is to use a transition matrix. The state we will consider is the set of horizontal segments that the closed path uses in a certain strip. Consider the following image.

The state of this closed path is $110110$ in the second column and $111010$ in the fourth. What you need to do is define a matrix $M$ where every row and every column represents a state. The entry at row $x$ and column $y$ should be $1$ if you can go from state $y$ to state $x$ and $0$ otherwise.

The point of this technique is described by the following fact. The entry at row $x$ and column $y$ of $M^i$ is the amount of ways to go from state $y$ to state $x$ in $i$ columns. This concludes the theory. The rest of the work is in the implementation. I will note some very important pitfalls for this technique.

Pitfall 1: You might have notices the purple stars in the image. The point is that the set of horizontal segments that the closed path uses in a certain strip is not enough information. Some horizontal segments are allowed to be combined, while others are not. This is to prevent to get two disjoint closed paths count as one. In the image I drew stars between segments that are not allowed to be combined. You need to come up with a way to encode this in your state.

Pitfall 2: Actually calculating $M$ is not easy. For example, note that you can not go from state $1100$ to state $0011$ because vertical line segments will need to cross.

Pitfall 3: To prevent getting two disjoint closed paths, you will also need two extra states. A start state and an end state. They both have no horizontal line segments, but they need to be distinguished between to prevent getting two disjoint closed paths. To read the final answer, just look at the entry of $M^m$ at the start state row and end state column.

The number of cycles with an exact length of $n$, meaning and max height of 2 is this:

$$ S(n,2) = 1 + sum_{m=1}^n sum_{k=1}^m binom{n-m-k+1}{k}binom{m}{k} cdot 2^k $$

Here, $m$ represents the number of columns with 1 square in them, and $k$ represents the number of groups of columns which have 1 square in them. It's very reminiscent of multichoose, except there's two options for each group of columns (either the squares are on the bottom, or top).

Thus, for the total number of cycles in a $n times 2$ board is:

$$ f(n,2) =sum_{i=1}^n (n-i+1) cdot S(i,2) $$

$S(n,3)$ is where things get ugly. Basically, you consider every possible configuration of columns with three squares in them, and then calculate the number of possible ways to connect these columns without creating another in between. I'd suggest a recursive formula dependent upon the squares visible at one end. Let $g(n,3)(b,b,b)$ be the number of cycles with exact width $n$, and the second part is binary conditions on where or not the $j$-th highest square in the rightmost column is in the cycle. The recursion would look something like this:

$$ g(n,3)(1,0,0) = g(n-1,3)(1,1,1)+g(n-1,3)(1,1,0) $$

We'd also want to include a clause about $g(n,3)(1,0,1)$, which sorta of depends on what cycles are allowed.