Number of ways to go from A to I

Question

Suppose I have to go from $A$ to $I$ in such a way that I should not visit one tile more than once, in my path, and only horizontal and vertical movements are allowed. I brute forced the solution and found that there are $12$ possible ways to reach $I$ starting from $A$. I am wondering if there is any combinatorics method to solve the problem.

My analysis is that every tile except $E$ has $1$ input and $2$ possible outputs. $E$ has $1$ input $3$ possible outputs. So, all possible paths from $A$ will be $(2^7) + (3^1) = 131$. Thus, I am over-counting.

Answer 1

After moving at $A$, you can choose to branch out at $B, C, D, or G$. At $C$, you have $3$ paths: $CFI$, $CFEHI$ and $CFEDGHI$. This means at $G$, there are also $3$ paths. At $B$, there are also $3$ paths, and the same for $D$. Hence, it is $3+3+3+3=12$.

Answer 2

This is only a solution to a subtask of your question. But at least it is purely combinatoric, and maybe you have an idea to expand it.

The number of shortest paths from $A$ to $I$ is $4!\over2!2!$ $=6$

In a $n\times n$-square the number of shortest paths is $(2n-2)!\over(n-1)!(n-1)!$

'Proof': In a $n\times n$-square your shortest path is $n-1$ steps right ('$r$') and $n-1$steps up ('$u$'). Hence, the number of shortest paths in your square is the numberof permutations of ($rruu$).