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.

Path diagram for 4×4 square grid

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.

Related Posts:

65 thoughts on “A square grid path problem

  1. 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. 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 :(

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

    • 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?

  4. Pingback: Recrutement et Casse-Tête « Dr. Goulu

  5. Pingback: Nektra Advanced Computing Blog :: Google Treasure Hunt puzzles are too easy?

  6. Pingback: Problem 15 | Project Euler

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

  8. 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.

  9. 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.

  10. 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)

  11. Pingback: the equation - StartTags.com

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

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

    • 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,

  14. 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?

  15. 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,

  16. Pingback: Recursive method infinitely looping - Java Forums

  17. Pingback: Recrutement et Casse-Tête | Pourquoi Comment Combien

  18. 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)

  19. 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! :)

  20. 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.

  21. 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.

  22. 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)?

  23. 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?

  24. 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?

  25. 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.

  26. Pingback: Number of unique way to travel in matrix « Java Task Force

  27. 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…

  28. 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)?

    • 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

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

  30. 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..

  31. 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 ?

  32. 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.

  33. 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.

  34. 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.

  35. 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. :) :)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>