Subj : Re: Knight's tour
To   : comp.programming
From : Gerry Quinn
Date : Thu Jun 30 2005 10:18 am

In article <d9upgd$lno$1@domitilla.aioe.org>, forayer@dontspamme.pls 
says...
> 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

Seems good.  Of course for knights 'following the edges' and 'going to 
the node with the fewest exits' tend to be synonymous.
> 
> > 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

Interesting site.  I see I'm following in the footsteps of Mani and de 
Moivre in regard to general methodologies ;-)

- Gerry Quinn

.