A Hamiltonian path is a path on a graph that steps through its vertices exactly once. On a grid, this means stepping through every cell exactly once.
On a square grid, a Chess King can move to a horizontally, vertically, or diagonally adjacent cell in one step.
Count the number of Hamiltonian paths using Chess King's moves through a square grid of 3 rows and N columns (denoted
X below), starting at the left side of the entire grid (denoted
S below) and ending at the right side (denoted
<------N------> X X X ... X X X S X X X ... X X X E X X X ... X X X
In other words, count all paths from
E that passes through every
X exactly once using only King's movements.
Standard code-golf rules apply. The shortest code in bytes wins. Kudos if you can solve this with short code in a way other than brute-forcing all possible paths.
Generated using this APL code (equivalent Python 3 + Numpy) which I created by finding 15 possible states of the rightmost column and deriving a 15-by-15 transition matrix (figures up to
N=3 are crosschecked with a pure brute-force Python).
N -> Answer 0 -> 1 1 -> 2 2 -> 28 3 -> 154 4 -> 1206 5 -> 8364 6 -> 60614 7 -> 432636 8 -> 3104484 9 -> 22235310 10 -> 159360540
Thanks to @mypronounismonicareinstate and @ChristianSievers for confirming the test cases in the sandbox.