Wednesday, March 30, 2011

closing time

I thought I would share some more knight's-tour fun: Euler's method of closing a knight's tour. I learned about Euler's method (which dates from 1759) while reading the chapter on chess-related mathematics in Ball and Coxeter's Mathematical Recreations and Essays. The section on knight-tours is included in some of the very old editions of this book that are available for free at Google Books (use this one, this other one seems to be missing the relevant page!).

It is tricky to come up with knight's tours that are closed (or re-entrant, as Euler called them), where the last square landed on is one move away from the square you started from. Warnsdorff's algorithm (described on Wikipedia) usually generates open tours and only occasionally (by luck) yields a closed tour. If a closed tour is your goal, instead of aiming for a closed path to begin with, you can create an open tour and then close it by applying a sequence of transformations to it.

Euler's method of changing the end-point of an open tour so that it is a neighbor of the starting point involves finding a square at which it is possible to chop-off the end of the tour and flip it such that the new final square is closer to the start.

Let's say we label our open tour $a_1, a_2, ..., a_{64}$, where each $a_i$ is a cell on the chess board, like A1, or G5, etc. The order that they are listed in is the order they are traversed by the tour. Each $a_i$ has a predecessor (except for $a_1$) and a successor (except for $a_{64}$)

Since this is an open tour, the "head" $a_1$ and the "tail" $a_{64}$ are not neighbors (the number of moves required to get from one to the other is greater than 1). To transform this open tour into a closed tour, we will alter the end of the tour so that the tail is closer to the head. We may have to do this several times before we get to the point where the tail and head are actually neighbors.

Start by choosing a neighbor of the tail (a cell that is one move away from $a_{64}$ but that is not its predecessor in the tour). Let's call the neighbor $a_k$. Our $a_k$ should be chosen such that the successor of the neighbor ($a_{k+1}$) is fewer moves away from the head ($a_1$) than the current tail. Make this choice such that the distance between $a_1$ and $a_{k+1}$ is the smallest you can, and if there is a tie, make this choice randomly.

We now keep the same partial-path $a_1 ... a_k$, but then instead of moving to $a_{k+1}$ as in the original tour, we jump from $a_k$ to $a_{64}$ (which we can do - they are neighbors), and then follow the path that used to lead from $a_{k+1}$ to $a_{64}$ in the reverse direction. So, our new tour becomes: $a_1, a_2, ..., a_k, a_{64}, a_{63}, ... a_{k+1}$. Our new tail should be closer to our head than the previous tail was. Repeating this process will eventually transform the open tour into a closed tour.

Here's a picture of what is going on in this technique:

The diagrams below show example of an application of the algorithm that takes two steps (some that I have run have taken over 40 steps!). An open tour A1 to F5 is first transformed to an open tour A1 to B5 and finally to a closed tour A1 to C2.

Euler developed further tools to help create knight's tours, including methods for absorbing missed cells into a partially completed tour and for constructing symmetrical tours that form partially magic squares.

A couple of other places to read about knight's tours and Euler's techniques are Martin Gardner's essay "Knights of the Square Table" (from Mathematical Magic Show), and in Ed Sandifer's article, How Euler Did It: Knight's Tour.

Among the many things that struck me while looking at this is the fact that I would never have been able to approach this without a computer (nor would I have had a strong inclination to try). The computer not only  finds and displays tours (something I have never actually done with a real chessboard), it also provides an algorithmic way of looking at things that helped me see what was going on. For knight's tours, the algorithmic lens provided by computers and programming can allow us to vaguely perceive things that Euler could see clearly with the naked eye.