Enumerating the Kight’s Tour

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.

3 thoughts on “Enumerating the Kight’s Tour

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

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>