(13 votes, average: 5.00 out of 5)

## Project Euler 15: Find the number of routes from the top left corner to the bottom right corner in a rectangular grid.

#### Problem Description

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?

#### Analysis

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.

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

The formula in general for any rectangular grid (n × m) using the notation for the binomial coefficient is:

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

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 Solution

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