The Knight's Tour

Clicking any square starts a new tour

The Knight's Tour - some background.

What it is:

The "Knight's Tour" is a solution to an old chess problem: how can you move the Knight, starting from any square on a chessboard, to every other square, landing on each square only once?

My solution uses a famous algorithm by Warnsdorff.

Generations of Computer Science students have worked on this problem.

What is special about this particular implementation?

It is graphical.

Traditionally, it is implemented as a console application, where you run it from the command line and give it the row and column number of a particular square to start from.

To test it, you have to run it 64 times, making sure you change the row and column numbers each time to a new starting square. That is very tedious and error prone.

Now that it is graphical you can just click your way through it, going from left to right in the first row and then down to the next one. Less tedious, easier to avoid skipping a square.

Even so, it took me a while to spot that if you start in row 6 and column 5, then it doesn't make it around.  I then added some error-flagging logic to be sure any other problem would be easier to spot. It now seems clear that the tour will end successfully when it is started from any one of the other 63 squares.

I can't help wondering how many other students have devised a solution that has a similar subtle error that they never noticed because it only happens on one or two squares buried somewhere in the middle of the board...

How it came to be.

It started life as a console application for a project in my Computer Science class "Data Structures in C" years ago.

A couple of years later, I wanted to put it up on my web site, so it could run in a browser. I replaced the prompts and print statements with some cgi logic, so it would do that. At that time, web hosts would still allow you to upload c executables.

In the latest upgrade, I went back to the console version and ported it to C#. I then made further modifications, so it would run from a code behind file in ASP.NET.

The design of the logic is based on the logic of a graphical calculator, where the four buttons (for doing addition, subtraction, multiplication and division) have been replaced with sixty-four buttons (one for each tour started at a particular square).

Valid XHTML 1.0 Transitional Valid CSS!

MCP icon