enter image description here

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.

  • $\begingroup$ 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. $\endgroup$ – Arthur Jan 17 '18 at 11:13
  • $\begingroup$ @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. $\endgroup$ – Shuvam Shah Jan 17 '18 at 11:23
  • $\begingroup$ Does "not visit one tile more than once" include zero visits to tile(s) ? $\endgroup$ – true blue anil Jan 17 '18 at 11:32
  • $\begingroup$ @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. $\endgroup$ – Arthur Jan 17 '18 at 11:33
  • $\begingroup$ @trueblueanil yeah. It includes zero visit $\endgroup$ – 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$.

  • $\begingroup$ 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? $\endgroup$ – 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$).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.