Re: Knight's tour

Gerry Quinn wrote: 
You're looking for a heuristic.

"Warnsdorf heuristic" seems to be a good enough solution. I found a PDF explaining the technique http://www.cs.ucsc.edu/~pohl/Papers/Pohl_Stockmeyer_full.pdf

For n x n boards, where n is odd and greater than 3, you can get a solution by starting at one corner and going round and round clockwise, staying as near to the edge as you can.

Unfortunately there doesn't seem to be other solutions that are so easy.

However, the concept of two-fold or four-fold symmetry, combined with a predilection for taking outside squares early, seems like a good idea. You could also try to have some connectivity heuristic for the cells left inside. Obviously you can't have two with only one connected usable square, and you probably don't want any. It would be nice if those with two linked up in chains.

Those are the sorts of things I would look at.

Thank you Gerry Quinn for helping me out.
Anyone reading this thread and interested in the knight's tour problem, might find this link a good read: http://homepages.stayfree.co.uk/gpj/ktn.htm

cheers,
forayer
.