Subj : Re: Knight's tour
To   : comp.programming
From : forayer
Date : Thu Jun 30 2005 01:03 am

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

.