← Complete problem index

PROJECT EULER · #0554

Centaurs on a Chess Board

Statement only · UnsolvedOriginal problem ↗

On a chess board, a centaur moves like a king or a knight. The diagram below shows the valid moves of a centaur (represented by an inverted king) on an 8×8 board.

0554-centaurs.png

It can be shown that at most n2 non-attacking centaurs can be placed on a board of size 2n×2n.
Let C(n) be the number of ways to place n2 centaurs on a 2n×2n board so that no centaur attacks another directly.
For example C(1)=4, C(2)=25, C(10)=1477721.

Let Fi be the ith Fibonacci number defined as F1=F2=1 and Fi=Fi1+Fi2 for i>2.

Find (i=290C(Fi))mod(108+7).

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.