Knight’s Tour
Trying to come up with a chessgame on a 3d board (maybe more on this later), my attention was sidetracked by the knight’s tour problem.
A knight’s tour is a complete tour of the chessboard using a chess knight, where every square is only visited once. This is part of a complete class of mathematical problems.
I wrote an algorithm to solve the standard problem (8×8). I implemented the algorithm in flash which might not be the fastest platform but it can easily be placed on the web. It uses a depth first search algorithm and a normal form for storing solutions which takes less than 24 bytes per solution. This will probably prove to be necessary because there are millions of unique solutions and they will be stored on my webserver.
Problem space is vast, so I devised a way to automatically distribute the problem over different computers.
I worked this into a windows screensaver with which you can contribute to the computation. Download the installer here. It will use your internet connection to receive a part of the problem space and send results back to the server every 10 seconds.
Output is minimal, to keep cpu overhead to a minimum so there’s no visual fireworks.
The fun part for me was building the algorithm and the distributed approach. And playing around with math in general. Since there are said to be billions of solutions, there is no real usefulness to my little project… (though I enjoyed myself!)
Click here for an online version.
Update (2005-05-08):
After 2,000,000,000 steps and over 5 million solutions I cancelled the computation. Since I will not find all solutions anytime soon and I proved my point to myself, I have taken down the online screensaver. Links in this post will not work as expected.
Thanks for contributing your cpu-time!
Tags:
