Solving the Chess Knight’s Tour using Excel VBA

The Knight’s tour is an ancient mathematical problem that dates back to the 9th Century AD. The problem consists of finding a path that allows the Knight chess piece to visit every single square on a chessboard once only.

Whilst there have been many different approaches to solving this problem, one of the earliest known methods was introduced in 1823 by H.C Von Warnsdorf. This post describes an implementation of his rule using Excel and VBA to solve the problem. A video showing the completed solution in action can be found below:

How this Works

To begin with, the application randomly picks a square from an 8×8 chessboard, and then moves the Knight (according to the rule) to a new square until all of the squares have been visited. The diagram below shows the legal moves that the Knight is allowed to make:

From the centre square it can visit any of the locations marked with an X, and can jump over visited squares to get to that location. To cover the whole board, the Knight needs to make 63 moves. The Knight’s path can be tracked by the sequence of numbers it leaves behind.

Implementing the Rule

Warnsdorf’s rule works by identifying all possible moves from a given square, and then selecting the square to move to that has the least amount of onward moves. Any visited squares are not included in the count of onward moves. If there is more than one square that matches the selection criteria, then the square chosen is picked at random from these matching contenders.

In the diagram, the Knight can move to any square with a number in it. The numbers represent the number of onward moves from that particular square. The next square to move to will be the one with the lowest number which in this case  happens to be 2. Since there are 2 squares with 2 onward moves, either of these squares can be chosen next.

About the Code

The Excel application itself consists of 3 main elements. The first element is the Knight Tour Class which handles most of the work:

The class consists of methods relating to move identification and  piece animation, as well as  properties which allow the board range and piece font to be specified. The code for the class is presented here in its entirety:

 
The second element is a main subroutine that runs the entire program using the methods and properties of the Knight tour class. It is fairly short because it does not have much work to do (the program’s complexity is handled by the class!). In a nutshell, all it does is create an instance of the Knight class, tells the instantiated object where the board is, picks a random square to start with, and then keeps moving the Knight to a valid square until no more moves can be found. The code is presented below:

 
The third element is the graphical display. The chessboard is represented using standard Excel cell formatting techniques.  However, the Knight chess piece itself is created using a third party TrueType font called Chess Alpha created by Eric Bentzen. The installation of this font occurs when the workbook is opened and it is uninstalled when the workbook is closed. The installation is handled by a separate class in the project. You can read more about the class in this post.

That covers the entire project in full. You can  download the solution in the video from here (however please take time to read the disclaimer about content found on this site).

Share :Facebooktwittergoogle_plusredditpinterestmail

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.