Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

Also known as: Project Euler problem 15

Also known as: A week to understand, a minute to implement.

The problem:

Starting in the top left corner of a 2 x 2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20 x 20 grid?

To start with the simple observation first: Any route through an m x m grid can be expressed as a sequence of Rs and Ds where R is right and D is down (the without backtracking condition ensures that you can’t go left or up – this simplifies things somewhat).

The second observation is that each route must be exactly 2m steps long (m steps to the right and m steps down).

So the problem that needs to be solved is: How many ways can you combine m Rs and m Ds?

It turns out that this is a combination problem which Wikipedia handily defines as a way of selecting several things out of a larger group, where order does not matter. The larger group, in this case, is all 2m steps and the several things you want to select are the k possible combinations of R (or D). The Ds (or Rs) don’t matter because you know that they have to populate the m remaining slots in the path.

A k-combination of a set S is a subset of k distinct elements of S. If the set has n elements the number of k-combinations can be expressed as n! / k!(n - k)! as long as k<=n.

Implementing this was a doddle and, for bonus points, my solution should work for any rectangular grid.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s