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

Get a FREE Twist Tie Animal!

So, here’s the beef, folks.  Check out the following actual traffic data for this blog:

chart

dogPretty pathetic, huh?  We here at Josiahland.com sure think so.  And, so we’ve decided that it’s time for something new and exciting with the site.  But, what that something is, we want YOU to decide. For each qualifying submission, we’re GIVING AWAY one of our awesome custom Twist Tie Animals (See example to the right).  Let me tell you folks, these things will TOTALLY make your life WAY BETTER IN EVERY WAY.

To qualify, a comment must be posted on this post before next Sunday (August 23rd).  If you’d like a specific animal, please include that information.

IMPORTANT:

If you would like to receive the actual twist-tie animal via mail (as opposed to a link to a digital photo), please provide me with the following information:

  1. Your mailing address.
  2. A comment suggesting something new and exciting to add to or change about Josiahland.com.  This must be something that is actually possible for a time-pressed college student like myself to implement.