Re: Knight's tour

In article <d9upgd$lno$1@xxxxxxxxxxxxxxxxxx>, forayer@xxxxxxxxxxxxxx
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
.