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).

Yep. “I was just curious how many possible 64-move tours could be made.”