Number of ways to go from A to I

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.

• G and C only have one output. And I has none (since a path ends when it reaches I). I don't think that that is the way to go o get a final answer, because it's difficult to keep path length in mind, and at the same time make sure that no tile is visited more than once. I don't know whether there is a nice answer, but you can brute-force systematically, by classifying paths by which of G, E and C it goes through, and in what order. For instance, no paths go through G and C but not E, and four paths go through E but neither G nor C. – Arthur Jan 17 '18 at 11:13
• @Arthur yeah! you're correct. There's only one output from G and C each. I brute forced. Since this was a 3-by-3 matrix it was easy to brute force. But once the size increases to suppose 100-by-100, then it becomes immensely difficult to compute the number of possible ways. – Shuvam Shah Jan 17 '18 at 11:23
• Does "not visit one tile more than once" include zero visits to tile(s) ? – true blue anil Jan 17 '18 at 11:32
• @trueblueanil Zero times is not more than once, so it ought to be valid. Also, it's clearly required to get the given answer of $12$, since there are only two paths that visit all of the tiles. – Arthur Jan 17 '18 at 11:33
• @trueblueanil yeah. It includes zero visit – Shuvam Shah Jan 17 '18 at 11:36

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$.

• but isn't this brute force only? What if you have a 100-by-100 matrix? How are you going to figure out paths analogous to the 3 paths from C to I in the above case? – Shuvam Shah Jan 17 '18 at 11:41

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$).

• No, this is wrong. You can go up or down, left or right – QuIcKmAtHs Jan 17 '18 at 12:19
• I am only talking about shortest paths. If you go left or down it's not the shortest. – Max Punck-Institut Jan 17 '18 at 12:22
• This is something typical where someone can just find on the internet – QuIcKmAtHs Jan 17 '18 at 12:23
• I am deeply sorry. – Max Punck-Institut Jan 17 '18 at 12:24