Friday, December 23, 2016

life lessons from a knight's tour

Please check out these interactive puzzles: kixote (knight's tour) puzzles, and hidato (king's tour) puzzles.

Both are based on the idea of a solitary chess piece roaming around an otherwise empty board. A "tour" is completed if the piece touches every square exactly once.

Solving these puzzles involves revealing the hidden steps in the correct order to complete the tour. For example, in the kixote puzzle below, the first step in the tour is highlighted.

We need to find the second step in this tour. Based on how knights move, there are two options: the cell to the right of 19, and the cell to the left of 57. Looking at where the third step is (third cell down in the last column), we realise that the cell next to 19 must be number 2. Clicking on that, we unlock the next few steps in the tour:

Now at step 4, we need to find step 5, and to do that, we look at where step 6 is... and continue in that way until all the steps are revealed.

If you try this a few times, you may notice that although each tour is different, they tend to follow a familiar pattern of cycling around the edge of the board in their early stages, sometimes hopping around in the corners before moving along:

The tours look like this because of the technique used to generate them: the puzzle generator is not randomly selecting which square to move to, if it did this, it might take a long time to come up with a proper tour for you to solve. Instead of randomly selecting each move, the generator is using a heuristic to pick squares that will most likely lead to a completed tour.

To a knight, an empty chessboard looks something like this:
knight's graph

Two cells are connected if the knight can jump from one to the other. Some cells are better connected than others. The image below shows the number of connected neighbours for each cell:

The rule used by the tour generator is to always select a reachable cell that has the fewest free neighbours. This leads us towards the edges and into the corners, leaving the wide-open and accessible centre for the end. Obviously, this is not the only strategy that will work: every knight's tour is reversible, so each path which starts on the edges and corners could be flipped to produce a tour that starts at the centre. But the "start with the least open cells" is a strategy that works well, frequently producing complete tours.

Maybe there is some lesson here for many tasks: when faced with a list of things to be completed, start with the less attractive options first, and save the best until last.