Thought Process

This problem was really hard, but also very fun. I started by first trying to make a function which generates the desired arrangements for n = 7 and n = 34.

A key observation to make is that the Largest Fibonacci number must be to the right of the king, as its neighbour can only have a Fibonacci sum if it is the next smallest Fibonacci which means it can only have 1 neighbour.

Knowing this I made something similar to my Sudoku Solver, which essentially checks the last value of a path, and checks all of it's potential neighbours, and backtracks if at some point no neighbour can be found. I recommend you read the link above and the code below, because that in itself is not an easy challenge.

Once I did this I was stuck for quite a while until I noticed an intriguing pattern

Case n = 21:

[21, 13, 8, 5, 16, 18, 3, 10, 11, 2, 19, 15, 6, 7, 14, 20, 1, 12, 9, 4, 17] <- sequence from right to left

[34, 21, 13, 21, 34, 21, 13, 21, 13, 21, 34, 21, 13, 21, 34, 21, 13, 21, 13, 21] <- Sum of next 2 terms (34 = 21 + 13, 21 = 13 + 8, etc)

Essentially we have a pattern where when n is a Fibonacci the sum of 2 consecutive terms must be either n (denote F(n)) or the Fibonacci before and after it (denote F(n+1), F(n-1)), with this it is still a bit tricky to get the final answer but within grasp, so I will leave it to you.

A hint is to consider is F(n+1) mod F(n) = F(n-1) mod F(n)

If you are still stuck feel free to see my Github, where I wrote some notes when I was solving it