Last November I have solved Problem 15 of Project Euler (a counting problem involving paths in square grids), and, although the problem admits a simple solution, some of the solutions presented in their forums are very complicated. Thus, I thought it would be a good idea to present my solution, as I consider it very simple.
Problem statement
Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.
How many routes are there through a 20×20 grid?
My solution
In order to make the problem more interesting, let us investigate the more general problem of counting the number of routes in a n×n grid. Our argument is based on three observations:
- all the paths have size 2×n (the reason is obvious: you have to go right n positions and down another n positions);
- since we can only go right or down, we can identify every path by a string of Rs and Ds, where a R means going right and a D means going down; as an example, the paths illustrated in the problem statement are (from left to right and from top to bottom): RRDD, RDRD, RDDR, DRRD, DRDR and DDRR;
- the strings mentioned above must contain the same number of Rs and Ds.
From these three observations, we can transform the problem to the following:
How many different strings of size 2×n, consisting of n Rs and n Ds, there are?
The solution is now very simple, because the positioning of n Ds (or Rs) determines the positioning of the other n Rs (or Ds). Hence, the number we are interested in is the number in which we can choose n positions from 2×n available. The answer, using the traditional notation for the binomial coefficient, is:
Instantiating n with 20, we get the answer to the initial problem of the 20×20 grid.
Generalization to m×n grids
The generalization to a m×n grid is also simple. The only difference is that the strings have length m+n. Using the same reasoning as above, the number of paths through a m×n grid is:
Final note: If you want to access the forum of the problem, you have to solve it.
27 Comments
Funny – I searched for “paths through a square grid” in trying to solve the very same problem on the very same site.
Thank you for a clear explanation.
Hi Fish613,
I’m glad you find the explanation clear. Thanks for your comment.
You’re very welcome
I’m currently trying to make my own solution work, also involving the binomial, but my program fails to give the right answer, even though I’m sure it’s working properly
As long as you define the factorial function correctly, it should be very easy. In Haskell, for instance, you can define it as:
fac 0 = 1
fac n = n * fac (n-1)
Good luck!
How many routes is there on a 4 by 4 grid?
Boo2468: 70 ?
useful for Google Treasure Hunt 2008 at http://treasurehunt.appspot.com/ … Thanks !
Dr. Goulu: no problem! Good luck with Google’s challenge.
hey!
how many solutions would be in a 8X8?
=D
Amanda,
just replace n by 8 in the first formula and you get the desired result
Thank you very much for this helpful and clear description.
great work, but what if i want to include “go to left n positions”, what will happen to the formulas?, thx in advance….
also, what if we want from down to up path, we just change 2*n to 3*n…??
Mohammad: if you allow movements in all directions, then you have to be careful with loops (Note that RLRLRLRLRLRLRLRLRLRLRLRL maintains your position; you can thus prepend it to any other path.)
In that case, I suppose you could reformulate the problem to counting paths of size N that lead you to the bottom-right corner.
thank you for such a detailed answer.
I have solved this problem on the Project Euler site by computing the paths starting from the end and working my way backwards. For example, for a 2×2 grid:
0 1 1
1 2 3
1 3 6
What is shown is the vertices of the grid and in reverse order. So, the top left corner has a 0 because it takes 0 paths to get to this spot. There is one path along each of the sides, then every other vertex is the addition of the two adjacent and smaller vertices. You can then keep working up to your desired number. 20 in the case of Project Euler.
I’m not sure if I was clear but that solution worked for me. Actually, you really only need to calculate half of those numbers due to symmetry.
Wow!Im not much of a math person and I have no clue why Im even on this website well Hi peoples!!!!!!!!!!!!!!!!!
I feel soo stupid to me you guys are speaking another language!LoL. P.Syou guys are smart:D
Can you tell me how to identify these cases through a loop or any algorithm?
Could you help me? I am terrible at math and i need to find how many routes are in a 8×8 grid.
Harpreet: I didn’t understand your question.
Bandgeek13: the answer is in the post. You just have to use the same reasoning with your concrete values (8×8)
I am confused, I am trying to find out a simple way for a 4×4 grid and need to explain it (I am only 13). When I put 4 into the n spots it doesn’t come out with seventy, ???. Please could you explain it. Could you PLEASE reply quickly I need it before Friday the 26th (this Friday!!!) THANKS!
Oh, by the way I live in Australia so there is a slight difference in time so could you please reply by Thurs (your time). THANKS again!!!
Sorry to bother you again, I meant to say Thurs (your time) at the latest PLEASE. Thanks soooo so much!
Dear yaso97,
If the grid is 4×4, the length of any path from the top-left corner to the bottom-right corner is 8. For example, one path consists in moving 4 times to the right and then 4 times down (that is, RRRRDDDD). Another example is to move down, then 4 times to the right, and then 3 times down (that is: DRRRRDDD).
Note that all paths have the same number of Rs and Ds: for your particular example, that number is four. (That is why the length of any path is 8.)
Now, we want to count the total number of ways of getting from the top-left corner to the bottom-right corner. In other words, you want to count the total number of sequences of length 8 made of Rs and Ds, where the number of Ds is 4 and the number of Rs is 4. To do that, you just need to count the total number of ways of placing 4 Rs in a sequence of length 8, that is, you need to count how many ways there are of choosing 4 positions from 8 positions. (When you choose 4 positions for placing the Rs, you automatically determine the other 4 positions for placing the Ds.)
How many ways are there of choosing 4 positions from 8 positions? Assuming you know combinatorics, the answer is easily determined: 8!/(4!*4!).
And the result is larger than seventy (where did you get seventy from?).I hope this helps,
Joao
Sorry, but I haven’t learnt combinatorics yet and have no idea what that math sentence means could you please put it in simpler math?
Hi,
The factorial of n, denoted by n!, is the product of all numbers from 1 upto n:
n! = n*(n-1)*(n-2)*…*2*1
So, for example,
5! = 5*4*3*2*1 = 120
The expression I wrote above can be simplified as:
8!/(4!*4!) = ((8*7*6*5)*4!)/(4!*4!) = (8*7*6*5)/4! = etc…
(In fact, you were correct, it is 70. Sorry for my previous mistake.)
All the best,
Joao
4 Trackbacks/Pingbacks
[...] pour un damier de 56×32 cases (le nombre change pour chaque participant) et dans ce cas, la réponse est 232059241971866600926656. Ca suppose donc déjà de disposer d’une bonne calculatrice [...]
[...] gets solved just searching in Google for “grid path right down” from there you will get the equation that you must run on any language that has Big Integer implementations, since involves the [...]
[...] using combinatorics. João Ferreira has a good description of the problem and general [...]
[...] my efforts with launching the Austin Interactive Initiative (also known as Aii) to create a …A square grid path problem : Joao FerreiraLast November I have solved Problem 15 of Project Euler (a counting problem involving paths in [...]
Post a Comment