Knight's Tour (TK94KV1)

Data Structures Project. University of Helsinki, Department of Computer Science

The knight's tour is a puzzle that has amused chess players throughout the ages. The goal of the knight is to traverse around the board, landing on each square but once, and finally return to the square it started from. If the board is thought of as a graph, this kind of closed path is called a Hamiltonian cycle. It can be proven that there is a closed knight's tour on all boards with an even number of squares and dimensions greater than four.

The Knight's Tour applet demonstrates a simple algorithm for finding a knight's tour. The idea is to always jump to the square with least exits, unless it makes some unvisited squares unreachable. This algorithm works surprisingly well: in the majority of cases the program chooses the right moves on first try, without having to back up once. If this fails, all possibilities are eventually tried in a depth-first manner.

The program is implemented as a Java applet that can be run with any browser that supports Java 1.1. The board is represented graphically, and can be resized by dragging the borders with the mouse to any dimensions between five and ten. The starting square can be chosen freely, and the actual search process can be viewed as an animation or skipped to just see the final tour.

Applet URL:
        http://www.helsinki.fi/~vahaaho/KnightsTour/tour.html
        local link
Documentation:
        http://www.helsinki.fi/~vahaaho/KnightsTour/doc/doc.html
        local link

Author:
        Markku Vähäaho
        tel: +358-40-5604416
        email: Markku.Vahaaho (at) helsinki.fi
        www: http://www.helsinki.fi/~vahaaho