I use a 2×2 grid trying to explain a recursive solution to problem number 15.

Credit for the algorithm goes to Pim Spelier, who wrote a nice solution on Project Euler, which is downloadable as PDF once you have submitted the correct answer.

The idea is to assign a tuple to each grid point, starting with (0,0) at the upper left corner. First row (0,0), (0,1), (0,2). Second row (1,0), (1,1)…you get the idea. The bottom right corner is (2,2).

Now we turn the grid into Pascal’s triangle.

Looking at the grid this way, it is now more transparent how the grid actually is a Pascal’s triangle. Starting from the top left corner, only one possible route exists to each grid point marked with a “1”. A grid point marked with a “2” can be reached by taking two different routes. Guess how many routes lead to a grid point with a “3”.

The number of lattice paths through the grid is the sum of the paths to (2,1) and (1,2): 3 + 3 = 6.

You can see that for every tuple containing a 0 like (0,0) or (2.0) and so on, we must return 1.

Every other grid point number is the sum of the two numbers directly above it.

This leads to the following recursive algorithm.

The function is called 11 times.

Unfortunately this solution has a “minor” flaw, which is performance. Calculating the lattice path for a 20×20 grid on my iMac G5 takes over 10 minutes.

A better performing algorithm will be the topic of an upcoming blog post.