Project Euler 15: Find the number of routes from the top left corner to the bottom right corner in a rectangular grid.
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?
This question has been posed as: “Starting at the top left corner, how many ways through town are possible using only one-way streets and ending at the bottom right corner of a n x n grid?”
Another analogy might be: “Place a single rook on the top left corner of an empty chess board and count the number of tours to the bottom right corner moving only left and down.” This would assume an 8 × 8 grid.
Determining the number of routes for a square grid (n × n) is the central binomial coefficient or the center number in the 2nth row of Pascal's triangle.
The formula in general for any rectangular grid (n × m) using the notation for the binomial coefficient is:
Any combination using nDowns(D) and mRights(R) would be a valid move.
In the example provided in the problem description there would be (2 + 2)! or 24 possible moves, but many would be indistinguishable, and we would have to divide by (2! × 2!) to eliminate them. So, (2 + 2)! / (2! × 2!) = 24 / 4 = 6. Namely, RRDD, RDRD, RDDR, DRRD, DRDR and DDRR. By indistinguishable we mean DDR1R2 is the same move as DDR2R1.
Project Euler 15 SolutionRuns < 0.001 seconds in Python 2.7.
from Euler import factorial as fact, binomial n, m = 20, 20 # method 1, n == m, square grid, central number in row 2*n of Pascal's triangle if n == m: print "Project Euler 15 Solution (square grid) =", binomial(2*n, n) # method 2, n != m or n == m, rectangular grid print "Project Euler 15 Solution (rectangular grid) =", fact(n+m) / (fact(n)*fact(m))Use this link to get the Project Euler 15 Solution Python 2.7 source.
AnswerSlowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
- Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A000984: Central binomial coefficients: C(2*n,n) = (2*n)!/(n!)^2.
- If we added the condition “which do not pass below the diagonal” to our problem statement, we would use a Catalan number. It is calculated as 2n! / n! / (n+1)!