I have gone in a very round about way, and my explanation might not be clear. Apparently, this is a very standard combinatorics problem and can be answered at sight. Well, I did not know that, and did a few things which made me realize the combinatorial answer.
The latest problem that I solved was is Problem 15. Given a grid of 20 x 20 squares, the question asked was to find the number of routes from the top left hand corner of the grid to the bottom rightmost corner without ever backtracking.
This was an easy one too. I started out by writing at every meeting point of lines, the number of extra lines that spring out of the point. For example, at the starting point 2 lines start. Select for example the horizontal one. At the first point that it comes across, it forks into 2 lines, which is 1 extra. So I wrote 1 at this point. The same is done at all points except those on the rightmost vertical and the bottommost horizontal which contains the total number of lines passing through it.
Below is a diagram showing the same thing.
Notice the similarity with Pascal’s triangle.
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
The center element of Pascal’s triangle is given by 
Thus our answer for 20 x 20 grid is 
Popularity: 16% [?]
Related posts:
- Project Euler : Sum Of Both Diagonals In A 1001 By 1001 Spiral
- Project Euler : Maximum Sum Traversing Top To Bottom In A Triangle
- Project Euler : Finding The nth Digit Of The Fractional Part Of Irrational Number
- Project Euler : Greatest Product of 4 Numbers In A 20×20 Grid
- Project Euler : Fractions With Unorthodox Cancelling Method
0 Responses to “Project Euler : Number Of Routes From One Corner To Another In A Grid”