Watch Your Step!

Let $s_{i,j}$ be the unit square at column $i$ and row $j$ (So we want to go from $s_{1,3}$ to $s_{1,1}$ ). And define $a_n$ be the number of ways to reach $s_{1,1}$ from $s_{1,3}$ that contains rightward movement exactly $n-1$ times (note that this is equivalent to the maximum column being reached is column $n$ ). Let $b_n$ be the number of ways to reach $s_{1,1}$ from $s_{1,3}$ that contains rightward movement exactly $n-1$ times and passes through $s_{1,2}$ . Let $c_n$ be the complement of $b_n$ in $a_n$ , so $a_n = b_n+c_n$ .

Note that, the first step of $c_n$ must be $s_{1,3}\rightarrow s_{2,3}\rightarrow\ldots$ and the last step must be $\ldots\rightarrow s_{2,1}\rightarrow s_{1,1}$ . Therefore it is the same as the number of ways to go from $s_{2,3}$ to $s_{2,1}$ , by only moving right exactly $n-2$ times, which is $a_{n-1}$ . So $c_n=a_{n-1}$ where $c_1:=0$

For $b_n$ , we have $b_1=1$ and if $n>1$ then either we pass through $s_{1,2}$ in the first step or in the last step exclusively, that is, either $s_{1,3}\rightarrow s_{1,2}\rightarrow s_{2,2}\rightarrow\ldots$ (call it $p_n$ ) or $\ldots\rightarrow s_{2,2}\rightarrow s_{1,2}\rightarrow s_{1,1}$ (call it $q_n$ ). By reflection on horizontal line, we see that $p_n=q_n$ which implies $b_n=2p_n$ .

Now for $1<i\leq n$ , let $r_i$ denotes the number of ways in $p_n$ that move downward for the first time at column $i$ (actually $r_n$ represents the case where it doesn't go down at all, which there is only one way to do that). Note that the first $i+2$ steps in $r_i$ is $s_{1,3}\rightarrow s_{1,2} \rightarrow s_{2,2}\rightarrow s_{3,2}\rightarrow\ldots\rightarrow s_{i,2} \rightarrow s_{i,3}\rightarrow s_{i+1,3}\rightarrow\ldots$ and so it is the same as the number of ways to reach $s_{i+1,1}$ from $s_{i+1,3}$ by moving right $n-i-1$ times (because we have moved right $i$ times), which is $a_{n-i}$ . So by defining $a_0=1$ we have $p_n = \sum_{i=2}^nr_i = \sum_{i=0}^{n-2}a_i$ and so $b_n=2\sum_{i=0}^{n-2}a_i$ .

Combining above results, we have $a_n = b_n + c_n = 2\sum_{i=0}^{n-2}a_i + a_{n-1}$ , which implies $a_n = (a_{n-1}+a_{n-2})+a_{n-1} = 2a_{n-1}+a_{n-2}$ . And so since $a_1=1$ and $a_2=3$ , we have $a_3=7, a_4=17, a_5=41, a_6=99, a_7=239, a_8=577$ . What we are looking for is $\sum_{n=1}^8 a_n = 1+3+7+17+41+99+239+577 = 984$ .

[Edits by Aldrian]

We consider that each column can be in 3 states:

• State 1: The output pins (the right side of column) is located at the top and the bottom squares.
• State 2: The output pins is located at the middle and a top or bottom squares.
• State 3: The output pins is none (the path is closed in this column).

Note : since the grid has 3 rows, and the path is begin from the first column (the left most), there are only two output pins each column.

• State 1 can lead to one case of state 1 and state 3, two cases of state 2.
• State 2 can lead to one case of each state.
• State 3 can only lead to state 3 (the path has been closed).

Then, use the stochastic matrix to solve this Markov chain:

$A = \begin{bmatrix} 1 & 2 & 1 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}$

Initially, the input state is state 1 (the path ends at the top and bottom left squares) and the last state must be state 3 (the path must be closed at last). So the solution of this problem is:

$(A^{8})_{1,3} = 984$

Note : you only need to track $A_{1,1}^n, A_{1,2}^n, A_{1,3}^n$ rather than whole matrix when powering.

We can try a simple programing solution using backtracking since the total number of possible paths is bounded by 2^24.

char seen[8][3];
int cnt=0;
int neigh[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

bool valid(int x,int y)
{
  return (x>=0)&&(y>=0)&&(x<8)&&(y<3)&&(!seen[x][y]);
}

void work(int x,int y)
{
  if((x==0)&&(y==2))
  {
    cnt++;
    return;
  }
  seen[x][y]=1;
  for(int i=0;i<4;i++)
  {
    int xx=x+neigh[i][0],yy=y+neigh[i][1];
    if(valid(xx,yy))work(xx,yy);
  }
  seen[x][y]=0;
}

int main()
{
  work(0,0);
  printf("%d\n",cnt);
  return 0;
}

This gives the answer as 984.

In general for 3 rows and n columns the number of self avoiding walks can be calculated via a recurrence relation. Let $W(n)$ be the total number of self avoiding walks on 3 rows and n columns. Let us label the squares of G by $(x,y)$ where $x = 1,2,\ldots, n$ and $y = 1,2,3$ , the bottom left is (1,1) and the top left is (1,3).

$W(n+1)$ is the number of walks that use n columns or less plus the number of walks that make use of the (n+1)th column. So $W(n+1) = W(n)$ + "Number of paths that use the (n+1)th column".

We will work out how many paths go through the (n+1)th column by extending those that go through the nth column. There are $W(n) - W(n-1)$ paths that go through the nth column: (i) $(n-1,1)\to (n,1) \to (n,2) \to (n-1,2)$ (ii) $(n-1,2) \to (n,2) \to (n,3) \to (n-1,3)$ (iii) $(n-1,1) \to (n,1) \to (n,2) \to (n,3) \to (n-1,3)$

The paths can be extended to the (n+1)th column in the following ways (a) from (i): $(n-1,1) \to (n,1) \to (n+1,1) \to (n+1,2) \to (n,2) \to (n-1,2)$ (b) from (i): $(n-1,1) \to (n,1) \to (n+1,1) \to (n+1,2) \to (n+1,3) \to (n,3) \to (n,2) \to (n-1,2)$ (c) from (ii): $(n-1,2) \to (n,2) \to (n+1,2) \to (n+1,3) \to (n,3) \to (n-1,3)$ (d) from (ii): $(n-1,2)\to (n,2) \to (n,1) \to (n+1,1) \to (n+1,2) \to (n+1,3) \to (n,3) \to (n-1,3)$ (e) from (iii): $(n-1,1) \to (n,1) \to (n+1,1) \to (n+1,2) \to (n+1,3) \to (n,3) \to (n-1,3)$ (f) from (iii): $(n-1,1) \to (n,1) \to (n+1,1) \to (n+1,2) \to (n,2) \to (n,3) \to (n-1,3)$ (g) from (iii): $(n-1,1) \to (n,1) \to (n,2) \to (n+1,2) \to (n+1,3) \to (n,3) \to (n-1,3)$

This means if there are $p, q, r$ paths of type (i), (ii), (iii) respectively we'll get $2p+2q+3r$ paths going through the (n+1)th column. Since there are $W(n) - W(n-1)$ paths going through the n-column we know $p+q+r = W(n) - W(n-1)$ We can see that $r = W(n-1)-W(n-2)$ (the paths of type (iii) are simply the paths going through (n-1)th column extended similar to (b) (d) and (e)).

So $W(n+1) = W(n) + 2p + 2q + 3r= W(n) + 2(p + q + r) + r$ . $W(n+1)= W(n) + 2(W(n) - W(n-1)) + W(n-1) - W(n-2)$ . $W(n+1)=3W(n) - W(n-1) - W(n-2)$

We can solve this recurrence relation using W(1) = 1, W(2) = 4, W(3) = 11. However, for this problem, only W(8) is needed. By substitution, $W(8)=984$ .

In general for 3 rows and n columns the number of self avoiding walks can be calculated via a recurrence relation. Let W(n) be the total number of self avoiding walks on 3 rows and n columns. Let us label the squares of G by (x,y) where x = 1, 2, ..., n, and y = 1, 2, 3, the bottom left is (1,1) and the top left is (1,3).

W(n+1) is the number of walks that use n columns or less plus the number of walks that make use of the n+1 column. So W(n+1) = W(n) + "Number of paths that use n+1 column".

We will work out how many paths go through the n+1 column by extending those that go through the n column. There are W(n) - W(n-1) paths that go through the n-column. They can go through the n column in the following ways (i) ... (n-1, 1) -> (n, 1) -> (n, 2) -> (n-1, 2) ...

(ii) ... (n-1, 2) -> (n, 2) -> (n, 3) -> (n-1, 3) ...

(iii) ... (n-1, 1) -> (n, 1) -> (n, 2) -> (n, 3) -> (n-1, 3) ...

The paths can be extended to the n+1 column in the following ways: (a) (i) turns to ... (n-1, 1) -> (n, 1) -> (n+1, 1) -> (n+1, 2) -> (n, 2) -> (n-1, 2) ...

(b) (i) turns to ... (n-1, 1) -> (n, 1) -> (n+1, 1) -> (n+1, 2) -> (n+1, 3) -> (n, 3) -> (n, 2) -> (n-1, 2) ...

(c) (ii) turns to ... (n-1, 2) -> (n, 2) -> (n+1, 2) -> (n+1, 3) -> (n, 3) -> (n-1, 3) ...

(d) (ii) turns to ... (n-1, 2) -> (n, 2) -> (n, 1) -> (n+1, 1) -> (n+1, 2) -> (n+1, 3) -> (n, 3) -> (n-1, 3) ...

(e) (iii) turns to ... (n-1, 1) -> (n, 1) -> (n+1, 1) -> (n+1, 2) -> (n+1, 3) -> (n, 3) -> (n-1, 3) ...

(f) (iii) turns to ... (n-1, 1) -> (n, 1) -> (n+1, 1) -> (n+1, 2) -> (n, 2) -> (n, 3) -> (n-1, 3) ...

(g) (iii) turns to ... (n-1, 1) -> (n, 1) -> (n, 2) -> (n+1, 2) -> (n+1, 3) -> (n, 3) -> (n-1, 3) ...

This means if there are p, q, r paths of type (i), (ii), (iii) respectively, we'll get 2p+2q+3r paths going through the n+1 column. Since there are W(n) - W(n-1) paths going through the n-column we know that

$p + q + r = W(n) - W(n-1).$

We can see that $r = W(n-1)-W(n-2).$

( The paths of type (iii) are simply the paths going through n-1 column extended via extensions similar to (b), (d) and (e) ).

So W(n+1) = W(n) + "Number of paths that use n+1 column"

$= W(n) + 2p + 2q + 3r$

$= W(n) + 2(p + q + r) + r$

$= W(n) + 2(W(n) - W(n-1)) + W(n-1) - W(n-2)$

$= 3W(n) - W(n-1) - W(n-2)$

We can solve this recurrence relation using W(1) = 1, W(2) = 4, W(3) = 11, to get $\frac{1}{4}(2 + \sqrt{2})(1+ \sqrt{2})^n + \frac{1}{4}(2 - \sqrt{2})(1-\sqrt{2})^n - 1$

Plugging in n = 8, since n is the number of columns, we get a grand total of 984 self-avoiding walks.