Background/Motivation
My interest in this problem traces back to an 11 year old girl who really took to one-way path counting problems. After doing several
configurations of streets, she decided to come up with a problem of her own. She presented a $3 \times 3$ gridwork
of two-way streets (forming 4 blocks in a $2 \times 2$ arrangement) and added the condition that a street could be
traversed at most once. She asked how many such paths are there from upper left to lower right? (Answer: 16.)
Stirred by her enthusiasm, we tried generalizing in various directions. If you have 2 long horizontal streets
with $N$ verticals, and let $a_N$ be the number of edge-disjoint paths from upper left to lower right and $b_N$ be
the number of edge-disjoint paths from upper left to upper right, then $a_{N+1} = b_{N+1} = a_N + b_N$ for $N > 1$ and $a_1 = b_1 = 1$.
The $3 \times N$ case is trickier, but the number of edge-disjoint paths from upper left to lower right still satisfies a finite linear recurrence relation.
Naturally, I turned to OEIS and found sequences A013991-A013997, where Dan Hoey gives the number of edge-disjoint paths between opposite corners of $K \times N$ grids for $K = 3, 4, 5, …, 9$ and small $N$. He also provides the first few values for the $N \times N$ cases (sequence A013990). (Note, his numbering counts blocks, not streets.) For $K=3$, he provides a generating function. In a recent communication, he explained the computer algorithm he used to compute the values but indicates that he did not find a recurrence relation for these sequences, so as far as I know, there is no known way to determine the answer to the title question for large $N$.
I've also spoken with Gregg Musiker, Bjorn Poonen, and Tim Chow about this problem. Although none knew how to do the $4 \times N$ case, Gregg simplified my recurrence relations for the $3 \times N$ case, Bjorn suggested many related questions and suggested an asymptotic formula for the $N \times N$ case, and Tim suggested looking at the related literature on self-avoiding walks, such as the book by Neal Madras and Gordon Slade, though it's not clear to me how related edge-disjoint and self-avoiding are with respect to counting them.
Because there are finite linear recurrence relations for the $2 \times N$ and $3 \times N$ cases, it seems natural to also ask:
Is there a finite linear recurrence relation for the number of edge-disjoint paths between opposite corners of a $4 \times N$ gridwork of streets?
Are these problems intractable?
Best Answer
To amplify on Christian's answer, the problem on a $K \times N$ grid for fixed $K$ and varying $N$ admits a finite-state transition model, so in particular is given by a linear recurrence.
The key is to find the right set of states. If you take an edge-disjoint path on a $K \times N$ grid and slice it on a vertical line through the middle passing through a set of horizontal edges, you'll see the path crossing along some odd number of these edges ($\le K$). On both the left and right we'll see a collection of paths with these endpoints. There's another constraint, that we end up with a single, connected path without disjoint loops; to take that in to account, also record a matching: which endpoints are paired up on the right hand side. All but one of the endpoints are paired up in this way. (You could also choose the left, and end up with a slightly different matrix.)
For instance, in the $3 \times N$ case, there are $6$ states. If we record an occupied edge by $\times$ and an unoccupied edge by $\circ$ and turn everything on its side, the states are $$ \times\circ\circ\quad\circ\times\circ\quad\circ\circ\times\quad\times_1\times_1\times \quad\times_1\times\times_1\quad\times\times_1\times_1 $$ where the subscript indicates the matching. (In this case, there is at most one matched pair.)
Next consider the transitions. If you consider two adjacent vertical slicings of a path, you'll see two possibly different states. The set of edges that are occupied in the middle is determined by which edges are occupied in the two different states. There is sometimes a choice about how the strands are connected up. However, some of these choices will be ruled out by the constraints on the connectivity; usually you will end up with just $0$ or $1$ possibilities.
For instance, in the $3 \times N$ case, with the states in the order above, I get the following matrix of possibilities: $$ M =\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} $$
For the ultimate answer, you want to look at paths that start at the upper-left and go to the lower-right. You can incorporate that nicely by adding an extra slice to the left of the entire diagram, with only the top slot occupied, and another to the right of the diagram, with only tho lower slot occupied.
Concretely, in the $3 \times N$ case, the number of paths is given by the $(1,3)$ entry of $M^N$.
For the $4 \times N$ case, you would get a $16 \times 16$ matrix, which is straightforward but somewhat tedious to work out. As a result, the answer will satisfy a linear recurrence of order $16$.
An interesting variation is to consider only crossingless paths. In this case, the matching must be crossingless, so we only get 5 states in the $3 \times N$ case and $12$ in the $4 \times N$ case.
Update Jan 7: The matrix above is wrong: it should be $$ M =\begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 2 & 2 & 2\\ 1 & 1 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} $$
Update 2: And here's an image illustrating what is actually being counted:
I permuted the entries slightly, but they're labelled along the sides. The dotted paths are there to help in the counting: the non-allowed configurations would form a closed loop.