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-move tours could be made. 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.

Hi, im not sure if this site is still active or not but im just a little confused on one part.

If you’re claiming that you found out that there are 4*10^51 possible moves useing an 8×8 board, then how is it that it would take 2*10^13 years to make all of the moves?

Maybe I’m just confused on the wording or the math of it, but if someone could explain, I’d be thankful 🙂

Hmm… I see what you mean. I did this really late at night and a long time ago, so I’m not surprised that there is an error with the example calculation. We can still easily arrive at the 2*10^13 years number, but I’ll have to change the size of the giant supercomputer. I’ll update the values shortly.

We can verify the calculation in the following manner:

The minivan has a volume of 450 cubic feet.

This is enough space for [450 cubic feet / (1.7*10^-13 m^3) = 7.6*10^13] microchips.

That means we can do an average of [7.6*10^13/(12 attoseconds) = 6.3*10^30] simulations/second

Multiply by 2*10^13 years to obtain the original 4*10^51 simulations.

This algorithm gives just a rough upper bound on the number of knight tours, right? It counts the number of knight walks (in which vertices may appear more than once).