Let $v_1$, $\ldots$, $v_N$ be the vertical streets and let $h_{1,j}$, $\ldots$, $h_{4,j}$ be the horizontal edges between $v_{j-1}$ and $v_j$. An admissible path $\gamma$ induces a coloring of the horizontal edges as follows: Consider a vertical street $v_j$. The path $\gamma$ uses either one or three of the incoming edges $h_{k,j}$ $(1\le k\le 4)$. If $\gamma$ uses one edge, color it black and the three other edges white. If $\gamma$ uses three edges, two of them are linked to each other by a part of $\gamma$ extending only to the left of $v_j$. Color these two edges red, the third edge black and the unused edge white. In all, there are 16 possible colorings $c:\lbrace 1,2,3,4\rbrace\to\lbrace b, r, w\rbrace$ that can result in this way. There is a $16\times 16$ transition matrix $T$ that encodes the possible matchings between the coloring $c$ of the edges $h_{k,j}$ and the coloring $c'$ of the edges $h_{k,j+1}$ (e.g., circles must be avoided). This matrix $T$ has to be determined "the hard way", i.e., by listing for each $c$ the possible $c'$. The number of admissible paths $\gamma$ is then obtained by applying $T^{N-1}$ to a suitable starting vector; so there is indeed a linear recurrence for the number of these paths.

An example: If $c$ contains a black and two red edges, then using the vertical edges on $v_j$ in an admissible way one may

(a) continue the black and the two red edges into the next column individually, maybe at a different level,

or

(b) connect the black end of $c$ to either one of the red ends by a vertical segment creating a $\supset$ and continue the other red edge of $c$ into the next column, but as a black edge,

and, if room on $v_j$ permits, one may

(c) throw in two red edges beginning on $v_j$ which are connected by a vertical segment creating a $\subset$.

Let $v_1$, $\ldots$, $v_N$ be the vertical streets and let $h_{1,j}$, $\ldots$, $h_{4,j}$ be the horizontal edges between $v_{j-1}$ and $v_j$. An admissible path $\gamma$ induces a coloring of the horizontal edges as follows: Consider a vertical street $v_j$. The path $\gamma$ uses either one or three of the incoming edges $h_{k,j}$ $(1\le k\le 4)$. If $\gamma$ uses one edge, color it black and the three other edges white. If $\gamma$ uses three edges, two of them are linked to each other by a part of $\gamma$ extending only to the left of $v_j$. Color these two edges red, the third edge black and the unused edge white. In all, there are 16 possible colorings $c:\lbrace 1,2,3,4\rbrace\to\lbrace b, r, w\rbrace$ that can result in this way. There is a $16\times 16$ transition matrix $T$ that encodes the possible matchings between the coloring $c$ of the edges $h_{k,j}$ and the coloring $c'$ of the edges $h_{k,j+1}$ (e.g., circles must be avoided). This matrix $T$ has to be determined "the hard way", i.e., by listing for each $c$ the possible $c'$. The number of admissible paths $\gamma$ is then obtained by applying $T^{N-1}$ to a suitable starting vector; so there is indeed a linear recurrence for the number of these paths.

An example: If $c$ contains one black and two red edges, then using the vertical edges on $v_j$ in an admissible way one may

(a) continue the black and the two red edges into the next column individually, maybe at a different level,

or

(b) connect the black end of $c$ to either one of the red ends by a vertical segment creating a $\supset$ and continue the other red edge of $c$ into the next column, but as a black edge,

and, if room on $v_j$ permits, one may

(c) throw in two red edges beginning on $v_j$ which are connected by a vertical segment creating a $\subset$.

Here is a pictorial list (hopefully complete) of the possible transitions $c\to c'$:

http://www.math.ethz.ch/~blatter/grid.pdf

Let $v_1$, $\ldots$, $v_N$ be the vertical streets and let $h_{1,j}$, $\ldots$, $h_{4,j}$ be the horizontal edges between $v_{j-1}$ and $v_j$. An admissible path $\gamma$ induces a coloring of the horizontal edges as follows: Consider a vertical street $v_j$. The path $\gamma$ uses either one or three of the incoming edges $h_{k,j}$ $(1\le k\le 4)$. If $\gamma$ uses one edge, color it black and the three other edges white. If $\gamma$ uses three edges, two of them are linked to each other by a part of $\gamma$ extending only to the left of $v_j$. Color these two edges red, the third edge black and the unused edge white. In all, there are 16 possible colorings $c:\lbrace 1,2,3,4\rbrace\to\lbrace b, r, w\rbrace$ that can result in this way. There is a $16\times 16$ transition matrix $T$ that encodes the possible matchings between the coloring $c$ of the edges $h_{k,j}$ and the coloring $c'$ of the edges $h_{k,j+1}$ (e.g., circles must be avoided). This matrix $T$ has to be determined "the hard way", i.e., by looking at all 256 cases. The number of admissible paths $\gamma$ is then obtained by applying $T^{N-1}$ to a suitable starting vector; so there is indeed a linear recurrence for the number of these paths.

Let $v_1$, $\ldots$, $v_N$ be the vertical streets and let $h_{1,j}$, $\ldots$, $h_{4,j}$ be the horizontal edges between $v_{j-1}$ and $v_j$. An admissible path $\gamma$ induces a coloring of the horizontal edges as follows: Consider a vertical street $v_j$. The path $\gamma$ uses either one or three of the incoming edges $h_{k,j}$ $(1\le k\le 4)$. If $\gamma$ uses one edge, color it black and the three other edges white. If $\gamma$ uses three edges, two of them are linked to each other by a part of $\gamma$ extending only to the left of $v_j$. Color these two edges red, the third edge black and the unused edge white. In all, there are 16 possible colorings $c:\lbrace 1,2,3,4\rbrace\to\lbrace b, r, w\rbrace$ that can result in this way. There is a $16\times 16$ transition matrix $T$ that encodes the possible matchings between the coloring $c$ of the edges $h_{k,j}$ and the coloring $c'$ of the edges $h_{k,j+1}$ (e.g., circles must be avoided). This matrix $T$ has to be determined "the hard way", i.e., by listing for each $c$ the possible $c'$. The number of admissible paths $\gamma$ is then obtained by applying $T^{N-1}$ to a suitable starting vector; so there is indeed a linear recurrence for the number of these paths.

An example: If $c$ contains a black and two red edges, then using the vertical edges on $v_j$ in an admissible way one may

(a) continue the black and the two red edges into the next column individually, maybe at a different level,

or

(b) connect the black end of $c$ to either one of the red ends by a vertical segment creating a $\supset$ and continue the other red edge of $c$ into the next column, but as a black edge,

and, if room on $v_j$ permits, one may

(c) throw in two red edges beginning on $v_j$ which are connected by a vertical segment creating a $\subset$.