2011-11-03

# grid tours

Problem:

Here is a 4x10 board with a "tour" which visits every square exactly once.

The question is: How many "tours" (paths that visit every single square exactly once) are there in a 4x10^12 grid under the condition the tour must start in the top left square and finish in the bottom left square. (Credit to the guys at projecteuler.net for thinking up another great problem)

If we let T(n) be the formula for the number of tours in a 4xn grid, we need to find T(10^12). One approach is to find a recurrence relation. A trick is to realize there are only two possible ending columns. Try follow my working if you can, sorry It's messy :)

Final code: