Also known as: Project Euler problem 15
Also known as: A week to understand, a minute to implement.
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.