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