free web hosting | free website | Business Hosting | Free Website Submission | shopping cart | php hosting

Knight's Tour


What is the Knight's Tour Problem?

The Knight's Tour Problem is to find a tour on an M-by-N chessboard that visits all the squares exactly once, using only knight's moves. There are two variations of the Knight's Tour Problem. The first variation is to find a path rooted at some square and visit all the squares only once. The second variation requires finding a cycle that covers all the squares on the chessboard exactly once. The second variation is an interesting problem because it is often considered as a subset of the famous Hamiltonian Cycle problem, which belongs to the class of NP-Complete problems. I will focus on the second variation here.

The Knight's Tour problem thus reduces from finding a solution to a Hamiltonian Cycle. If you regard squares as nodes and moves as edges, then finding a solution to a KT problem is actually reduced to find a solution to an equivalent HC problem. In fact, the most potent solutions on the Web solves KT this way. There is one problem with this approach though, is that finding Hamiltonian Cycles necessarily forces the use of backtracking, and simple backtracking algorithms without heuristics often leads to algorithm run-time in exponential time of the input size. So in order to reduce the cost, one must use heuristics to help make better "guesses" for each move so that the number of backtrackings can be reduced. With proper conditions, one can show that the Knight's Tour problem can be solved in polynomial time.

On this page I provide an algorithm for solving a rather restricted version of the Knight's Tour Problem. The most obvious restrictions being the chessboard must be a square, and that the board size must be of length 4n+2, where n>=1. With these restrictions, my algorithm runs in a fast polynomial O(n^2) time. Yet the most distinctive feature of my algorithm is that it doesn't use any backtracking at all. That is, any moves that I make will be final. In fact, this is probably an example where the approximation algorithm is "perfect". I call the heuristics used in my algorithm the "Eight Walks" or "Basket Weaving" heuristics.

My algorithm is actually part of a hand-in of my CS341 assignment. You can read all about the documentation for this algorithm here.

Matlab

Matlab is a very good mathematical tool developed by MathWorks. You can basically do all your matrix algebra and graph plotting in a breeze. You can also build Matlab programs by writing in Matlab's native language. Functions and script written in Matlab has the extension .m. I still haven't got to figure out the most advanced features Matlab provides, but from what I have seen I am pretty impressed.

For the Knight's Tour program you will need Matlab to run its code.

Some files:

Here you will find the necessary .m files to run my algorithm. The program's main file is knighttour.m. You can find out more about it in the documentation.
I also provided some sample run results in form of .mat and .tif. The .mat files are stored Matlab matrix files. The .tif are images files converted from Matlab graph plottings.


Last update: 03-17-00
Contact me for questions or comments regarding this page.