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.

Tuesday, March 22, 2011

knight moves

The Knight is Chess's most enigmatic piece. Its weird L-shaped movement might prompt beginners (like me) to ask questions like:

  • What is the smallest number of moves required for a knight to move to a horizontally or vertically adjacent square of opposite colour? 
  • What is the smallest number of moves required for a knight to move to a diagonally adjacent square? 
  • What is the smallest number of moves required for a knight to move from one corner (say A1) to the diagonally opposite one (say H8)?

The diagram below shows the minimal number of moves a knight starting in the A1 corner takes to get to any other square.

Depending on where it is sitting on the chessboard, an unimpeded knight has a varying number of moves open to it (shown below). 

Not surprisingly, knights are at their freest in the middle of the board, and most constricted in the corners. To get a sense of how a chessboard looks to a knight, you can draw lines between the squares that knights can jump between. Squares that lie next to each other on the board are not adjacent as far as the knight is concerned: to the knight, A1 and A2 are not adjacent (accessible in one move), but A1 and B3 are. To the knight, the chessboard looks like a graph like the ones shown below.

For a standard board, the knight moves around on a graph with 64 vertices and 168 edges (it turns out that on an n x n board, the knight's graph has a number of edges equal to eight times the triangular number t_n). If a knight travels along this graph so that each vertex is touched once, it has performed a "knight's tour" - in general, a path like this is called Hamiltonian. If the knight finally ends on a vertex that can reach the vertex it started on, then it has completed a closed tour, or a Hamiltonian circuit, otherwise it has completed an open tour. 

These tours were found using Warnsdorff's algorithm (as it is described in Wikipedia). This is a greedyish algorithm in which the knight always chooses to move to a square that has the least number of open neighbouring squares (where 'neighbours' are in the sense of the knight's graph). This technique does not always yield a tour (but it succeeds surprisingly often), and makes no distinction between open and closed tours. Here's a few more tours:

Playing with this showed me an unlooked-for connection between origami and chess: Hamiltonian circuits give us knights tours and proper colourings of modular origami models (using Sonobe or Phizz).