# A square grid path problem

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{\times}2$ grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a $20{\times}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 an $n{\times}n$ grid. Our argument is based on three observations:

1. all the paths have size $2{\times}n$ (the reason is obvious: you have to go right $n$ positions and down another $n$ positions);
2. 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;
3. 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{\times}n$, consisting of $n$ Rs and n Ds, are there?

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 of ways in which we can choose $n$ positions from $2{\times}n$ available positions. The answer, using the traditional notation for the binomial coefficient, is:

${2n \choose n} = \frac{(2n)!}{n! \times n!}~~~~.$

Instantiating n with 20, we get the answer to the initial problem of the $20{\times}20$ grid.

## Generalization to $m{\times}n$ grids

The generalization to an $m{\times}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 an ${m{\times}n}$ grid is:

${m+n \choose n} = \frac{(m+n)!}{m!\times n!}~~~~.$

Final note: If you want to access the forum of the problem, you have to solve it.

## 65 thoughts on “A square grid path problem”

1. fish613 on said:

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.

2. jff on said:

Hi Fish613,

3. fish613 on said:

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 4. jff on said:

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!

5. Boo2468 on said:

How many routes is there on a 4 by 4 grid?

• Edward on said:

The solution above does not included if you are occupying the squares but instead are going around them. If you are occupying the squares and are looking for all possible paths, you are to find that the total number of paths are 144. 72 by starting horizontally and 72 by starting vertically… if you are not allowed to use the same location twice and are attempting to go from square 1 to square 16 (furthest from square 1). (allowing for left, right, up and down directions)

I ask, under this possibility, what is the equation to prove I am right?

6. jff on said:

Boo2468: 70 ?

7. Dr. Goulu on said:

useful for Google Treasure Hunt 2008 at http://treasurehunt.appspot.com/ … Thanks ! 8. jff on said:

Dr. Goulu: no problem! Good luck with Google’s challenge.

9. amanda on said:

hey!
how many solutions would be in a 8X8?
=D

10. jff on said:

Amanda,

just replace n by 8 in the first formula and you get the desired result 11. Pingback: Problem 15 | Project Euler

12. 1234 on said:

Thank you very much for this helpful and clear description.

13. Mohammad Hourani on said:

great work, but what if i want to include “go to left n positions”, what will happen to the formulas?, thx in advance….

14. Mohammad Hourani on said:

also, what if we want from down to up path, we just change 2*n to 3*n…??

15. jff on said:

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.

16. Madan kumar on said:

thank you for such a detailed answer.

17. Fulcanelli on said:

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.

18. torie4590 on said:

Wow!Im not much of a math person and I have no clue why Im even on this website well Hi peoples!!!!!!!!!!!!!!!!!

19. torie4590 on said:

I feel soo stupid to me you guys are speaking another language!LoL. P.Syou guys are smart:D

20. Harpreet Singh on said:

Can you tell me how to identify these cases through a loop or any algorithm?

21. bandgeek13 on said:

Could you help me? I am terrible at math and i need to find how many routes are in a 8×8 grid.

22. jff on said:

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)

23. Pingback: the equation - StartTags.com

24. yaso97 on said:

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!

25. yaso97 on said:

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!!!

26. yaso97 on said:

Sorry to bother you again, I meant to say Thurs (your time) at the latest PLEASE. Thanks soooo so much!

• jff on said:

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

27. yaso97 on said:

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?

28. jff on said:

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

29. beniskwl1998 on said:

i still dont get it im only 13 could u explain it more clearly?

30. Indigo on said:

I think that’s a very interesting solution, and I’d be curious as to how you would solve my Airplane Crash scenario.

The idea of the airplane crash scenario is that a plane crashes on an island, which is represented by a 12×12 grid, 40 people survive and using the airplane as a home base for shelter and storage of what they find in the wild, they begin scavenging out to find supplies that may have scattered from the airplane or are naturally occuring and could be used to sustain them until help arrives.

The goal is to make the searching more efficient, two people searching the same square find the same amount as one person searching the square. It is ok to cross paths, for practical purposes, but the search will yeild better results if squares are only visited once.

Also, because although theres 40 people, each person can only move 12 squares a day and needs to be back at the camp or they die of exposure.

The other element is the plane crash site is randomly determined. They may crash in the middle, giving them full range of the map, they may crash on an edge or in a corner that keeps them from ever being able to search every square. In cases like these we still want to find the maximum number of routes availible and of course the most efficient routes prioritized.

Also, some of the people will die from lack of supplies, so although they start with 40 people, each day the survivors total may drop at a random rate.

Survivors can only move N, S, E and W. They cannot move diagonally.

A program illustrating this should have 4 factors in mind that can be input manually.

1. Grid size – A 12×12 would be default, but the option to change the grid size should be available.

2. Survivor Count – The system always starts with 40, but it should allow a field to select a different number as conditions change.

3. Crash Site – The crash site coordinates should be entered in manually

4. Most efficient, unique routes should be itemized first and when selected (radio button) should highlight their corresponding path on the map. Duplicate routes should not be shown at all. (ie: NESW and ENWS are the same route just in reverse)

31. Lost on said:

Hi.. i noticed that all this involves using square numbers like 4×4 and 6×6. But what if the squares are 4×5?

Thanks! this would really help me from failing maths! 32. pooja on said:

I had studied the same problem as part of discrete mathematics course in college. It’s similarly solved in the book by Grimaldi. This is more often called as Catalan number. You’ve given a simple explanation. Thanks.

33. paul on said:

Hi Joao, Elegant solution… . Do you have mathematica code? I would like to take a look at it. Thanks!

• João Ferreira on said:

Hi Paul, thanks for reading. No, I don’t have any Mathematica code. Sorry.

34. Fred on said:

I saw the same problem in statistic class, though I’m interested in the total number of paths available including going “up” and “left”. For a 2×2 square with paths going from top left to lower right would have another 6 paths going like this (D means down, U means up, R means right, L means left) DRURDD, DDRURD, DDRUURDD, and RDLDRR, RRDLDR, RRDLLDRR. Of these paths there are four 6 units paths and two 8 units paths. I’m not sure if there’s a way to compute this, thinking of writing a minimum distance algorithm for this problem.

35. AbdulFattah Popoola on said:

Great tutorial! Very clear and straight to the point. Thanks man!!

36. Saurabh on said:

Could you please help me in solving the following problem. We have a 4 X 4 square grid. The allowed moves are Up or Right. How many distinct paths are possible from (0,0) to (4,4) always excluding the points
(1,2) and (3,3)?

37. Barry on said:

We have college professors and students trying to solve this problem and I’m trying to help my 6th grader solve it for a 2 (horizontal) x 3 (vertical) grid. Any help?

• Barry on said:

Sorry 4 (horizontal) x 3 (vertical) grid.

• João Ferreira on said:

Hi Barry, replace m and n by 4 and 3 in the last formula.

38. Ashley on said:

I have a similar problem I need to calculate the number of routes in an 10×4 from the top left to the bottom left cell and passing through every cell. Any ideas?

39. Jonathan on said:

João, thank you for the formula, it helped with the same problem!

I would like to understand it before I move on though. I am doing this projects as much to learn math as programming.

My solution at it’s base was similar, a factorial of the possibilities once I noticed the pattern of diminishing possibilities. I got the wrong answer because I was using the triangle number, n * (n + 1) / 2, of the X axis assuming 20 possibilities for the first placement of R, 19 for the second etc until you have no more Rs to place. Reverse triangle number.

Was my error in the assumption I didn’t need to worry about the size of the Y axis because their positions were fixed once x was decided? Just trying to understand your formula.

40. Zangar on said:

Hello! Interesting article! I need help though, what if the condition that you can’t go through certain point on the grid, all other ways are opened. How to find algebraically the amount of paths in that case? I know already the geometrical way…

41. colin on said:

Thanks João, you’ve made the problem very easy to understand. How could I extend this to routes through a n.n.n cube (or even a m.n.p box)?

• colin on said:

To be clear, I’m looking for the number of paths from one corner of the cube to the diagonal corner (without backtracking).

This is what I have so far…

For a n x n x n cube, the total length will be 3n. As with the square, we can move Left/Right and Up/Down; but in this 3-dimensional problem, we can also move Back/Forth. So we need a string of n Rs, n Ds, and n Bs. For example, for a 3x3x3 cube we could have DDDRRRBBB, or BRDBRDBRD, among others.

So, first we have to place n Rs in a possible 3n positions = (3n/n) = (3n)!/(n! x (2n)!)

Then in the remaining 2n positions, we have to place n Ds = (2n/n) = (2n)!/(n! x n!)

We can then put n Bs in the remaining n positions.

The complete answer is (3n/n) x (2n/n) = (3n)!/(n! x (2n)!) x (2n)!/(n! x n!) = (3n)!/(n! x n! x n!)

For a 1x1x1 cube, n=1, so there are (3×1)!/(1! x 1! x 1!) = 3 paths

For a 2x2x2 cube, n=2, so there are (3×2)!/(2! x 2! x 2!) = 90 paths

For a 3x3x3 cube, n=3, so there are (3×3)!/(3! x 3! x 3!) = 1680 paths.

Generalizaton to m x n x p box.

The total path length will be m+n+p.

So, possible ways to place the m Rs in m+n+p positions = ((m+n+p)/m) = (m+n+p)!/(m! x (n+p)!)

Possible ways to place n Ds in the remaining n+p positions = ((n+p)/n) = (n+p)!/(n! x p!)

And the p Bs fill the remaining p positions.

So the complete answer is = ((m+n+p)/m) x ((n+p)/n) = (m+n+p)!/(m! x (n+p)!) x (n+p)!/(n! x p!) = (m+n+p)!/(m! x n! x p!)

For a 1x2x3 box, m=1,n=2,p=3, so there are (1+2+3)!/(1! x 2! x 3!) = 60 paths

For a 3x4x5 box, m=3,n=4,p=5, so there are (3+4+5)!/(3! x 4! x 5!) = 27720 paths

42. Happy Face on said:

this is a really fun but challenging puzzle that we are learning about in math. do you know how to solve one of these puzzles with a hole in the middle i.e. a 3×4 hole in any part of the puzzle ? its really important because i need the answer asap please if possible!

43. Edward on said:

now what would happen if you took say a 3×2 rectangle out of a 7×4 rectangle?

44. Enelin on said:

Very nice and easy explanation but I can’t seem to find the correct way to insert the answer in ProjectEuler (for 20×20 grid). 40!/(20!*20!) equals about 1,38*10^11 so it’s not possible the fit the whole number into the answer slot.. I have tried C(40,20) etc but nothing seems to work..

45. Enelin on said:

Okay, already figured it out 46. Jhony on said:

What if a part of the rectriangle is cut from the upper right portion of the triangle..
Will there be any specific formula, except a summation one ?

47. Pedro on said:

Excellent explanation. Congratulations and thanks.

48. Jonathan on said:

I recently had to solve this on my own for work, and it took all of five minutes to see, and a bit under an hour to explain to others. This was a nice short sweet way, and I wish I’d been able to articulate it.

49. Domi on said:

Hi!

Thank you for a great explanation! Thanks for making it so easy to understand. 50. aditya4997 on said:

Hi João,

Thanks for very nice explanation. I am computer science major, so i was doing it with dynamic programming which make running time O(m * n) but with your explanation we can solve this problem with constant time. Your explanation is elegant.

51. Jean-Paul on said:

The combinatorial stuff was also my first though. However, there’s a much simpler way of thinking about it (Fulcanelli’s got the right idea) … rotate the square clockwise by 45 degrees so you get a diamond.
For the top half, each corner point can thus be reached by two possible paths above it, i.e. the sum of the two possible paths reaching it from above e.g. for the third row of corners it will be respectively 1, 3 (=1+2), 3 =(2+1), 1 etc. (If you don’t rotate the square, just think of the number of paths to reach a diagonal line’s corners.) You will recognize the numbers of the triangle of pascal.
Once you reach the widest point of the diamond (i.e. the 20th row of Pascal i.e. 1, 20, etc.), you will have an equal number of possible leading down to the bottom corner and each of the possible paths above can be combined with each of the possible paths below it.
So the total number of paths is the sum of the (21) squares of the values on that 20th row (of the diamond or Pascal’s triangle). Much simpler to visualize it than to explain. And very easy & quick to calculate.

52. Rahul Jain on said:

A lot of thanks to you. I was stuck on this formula for many days. Couldn’t find any source to understand the proof. This helped me a lot. Really thankful to you.  53. PeterJB on said:

Your solution is both simple and elegant. Thank you.