Problem 237
Tours on a 4 x n playing board

Let T(n) be the number of tours over a 4 ×n playing board such that:

  • The tour starts in the top left corner.
  • The tour consists of moves that are up, down, left, or right one square.
  • The tour visits each square exactly once.
  • The tour ends in the bottom left corner.

The diagram shows one tour over a 4 × 10 board:

T(10) is 2329. What is T(1012) modulo 108?

These problems are part of Project Euler and are licensed under CC BY-NC-SA 2.0 UK