So, I got a little sidetracked tonight by a brief mention of the Knight’s Tour problem. I wasn’t interested in solving the problem — I was just curious how many possible 64-length moves a knight could make. Following is a reference image and the Mathematica code:

(* Let fn[x] be the number of possible move sequences of length (x-1), starting from square n. Also, let An be the set of immediate possible "next move" squares, starting from square n. Then fn[0] is the number of squares in An, and fn[x] for x>0 is the sum of fi[x-1], for each square i in An. *) f0[x_] := Piecewise[{{2, x == 0}, {2*f5[x - 1], x > 0}}]; f1[x_] := Piecewise[{{3, x == 0}, {f2[x - 1] + f7[x - 1] + f6[x - 1], x > 0}}]; f2[x_] := Piecewise[{{4, x == 0}, {f8[x - 1] + f5[x - 1] + f1[x - 1] + f6[x - 1], x > 0}}]; f3[x_] := Piecewise[{{4, x == 0}, {f4[x - 1] + f7[x - 1] + f5[x - 1] + f8[x - 1], x > 0}}]; f4[x_] := Piecewise[{{4, x == 0}, {2*f3[x - 1] + 2*f8[x - 1], x > 0}}]; f5[x_] := Piecewise[{{6, x == 0}, {f3[x - 1] + f8[x - 1] + f9[x - 1] + f6[x - 1] + f2[x - 1] + f0[x - 1], x > 0}}]; f6[x_] := Piecewise[{{6, x == 0}, {f2[x - 1] + f7[x - 1] + f8[x - 1] + f5[x - 1] + f1[x - 1] + f9[x - 1], x > 0}}]; f7[x_] := Piecewise[{{8, x == 0}, {2*f9[x - 1] + 2*f3[x - 1] + 2*f6[x - 1] + 2*f1[x - 1], x > 0}}]; f8[x_] := Piecewise[{{8, x == 0}, {f3[x - 1] + f5[x - 1] + 2*f8[x - 1] + f9[x - 1] + f6[x - 1] + f4[x - 1] + f2[x - 1], x > 0}}]; f9[x_] := Piecewise[{{8, x == 0}, {2*f5[x - 1] + 2*f6[x - 1] + 2*f7[x - 1] + 2*f8[x - 1], x > 0}}]; fall[x_] := 4*(f0[x] + f4[x] + f7[x] + f9[x] + 2*(f1[x] + f2[x] + f3[x] + f5[x] + f6[x] + f8[x]; (* This will run for a LONG time! *) fall[63]

Update: I woke up this morning and realized that Mathematica was re-computing all the function values multiple times, so the above code will run (virtually) forever. I didn’t know how to make it “save” each computed value for later, so I just did it manually. Here is the updated mathematica file. Anyway, it turns out that there are on the order of 4*10^51 possible moves (3926356053343005839641342729308535057127083875101072, to be exact) that can be made.

To give you an idea of how many moves that is, let’s imagine that the smallest microchip in the world (1.6875*10^-13 m^3) can simulate a move every 12 attoseconds (the shortest time interval ever measured). Now, imagine that you have enough of these microchips running in parallel to build a super computer the size of a minivan (180 in x 72 in x 60 in). Even with these impossibly fortuitous conditions, *every star in the universe* would be expected to die out (roughly 2*10^13 years) before the simulation was finished.

Update: Adjusted size of imaginary supercomputer. Sorry about that.

Update: Edited to make it clear that this is just a rough upper bound on the actual Knight’s Tour problem (which requires that squares are visited exactly once).