Enumerating the Knight’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-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).

8 thoughts on “Enumerating the Knight’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.

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

  5. You won’t believe how long I was searching for such a result. I’m writing a PHD on “mathematical model of knight’s tour aided by computering” but I need to know 2 things. Is that the number of all possible tours (complete and incomplete) taking into an account all starting squares? Is this number exact mathematically? Thanks a lot for your effort. How can I thank you?

  6. I wrote this many years ago, and unfortunately don’t have time to go back and check the math right now. Yes the number is exact, but I’m also not sure what you mean by “complete” and “incomplete.” As mentioned before, this is a rough upper bound on the number of tours, since it makes no attempt to discard tours that visit a square more than once. The Mathematica file is there for you to download and look over though (it’s human-readable, so you shouldn’t need Mathematica to manually verify if I made a mistake in the functions).

  7. By an incomplete tour I mean “< 64 moves". I'm counting the probability of complete 64 move tour. P(64) = all complete tours / all move sequences . All complete tours is counted by a group of researchers. All move sequences is surely less that what you counted and more than 2^70 as I counted using bit-strings and binary trees. But the program I wrote never ended up with a successful tour. This means that the lower bound I counted is far less than the exact number. It's incredibly difficult to get the exact value of all moves sequences but I need it to estimate the average running time of an ordinary computer and to build up a statistical model. That's the reason no one ever took this topic in his work. But anyway, thanks for all. I'm going to include your link in my PHD work.

Leave a Reply

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