I had to solve this riddle from my book but so far I'm stuck at by doing several attempts and I felt it is like counting grains of sugar or some kind of sisyphean task. Can somebody help me with this?
The problem is as follows:
Using the figure from below, find the number of different routes which exist to go from point B to point A by traveling only in the directions indicated, being upwards, to the left, and in upward diagonals.
The existing alternatives given were:
$\begin{array}{ll} 1.&63\\ 2.&39\\ 3.&48\\ 4.&56\\ 5.&52\\ \end{array}$
Well for this one I'm totally lost. The only thing that I could come up with was to draw what it was the obvious choice, or in other words to draw the figure as depicted in orange line. But that was only one path that I could find. I tried to go in with another route which is colored as pear color, but that's how far I went.
Does it exist a way to solve this riddle more systematically and not just guessing or playing around with different combinations?.
An answer which would help me the most is one which could include perhaps an improved graphics or some sort of redrawing in Asymptote or any program showing a path or a way to solve this perhaps graphically if required.
I'd like somebody could help me with this question as I tried much effort and has not yet yielded results. Hence require assistance. Can somebody guide me on this?.
You can do this using dynamic programming. You will label each node with the number of legal paths from $B$ to that node. Initially, $B$ itself is labeled with $1$. Starting with the nodes which are closer to $B$, write label each node with the sum of the labels of its neighbors in the $\to,\searrow,\downarrow$ and $\swarrow$ directions. If there are no nodes in those direction, skip them in the sum. If you try to add up the label of an unlabeled node, first find the label of that earlier node. This works because every path to a node is preceded by a path to one of its $\to,\searrow,\downarrow,\swarrow$ neighbors. Adding the numbers of these paths gives the number of paths to the original node.
If I compute correctly, the answer is $52.$