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.

Reader of books, watcher of films, player of games.
British father of three, now living in Belgium and making a living from building interfaces.
View all posts by Paul