Subj : Re: Knight's tour
To   : comp.programming
From : Gerry Quinn
Date : Wed Jun 29 2005 11:35 am

In article <d9tb2i$7m3$1@domitilla.aioe.org>, forayer@dontspamme.pls 
says...
> Hi there,
> 	Is there any particular pattern in which to short-list the
> possible squares in the Knight's Tour problem such that it is solved 
> with few back-tracking?

You're looking for a heuristic.

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.

- Gerry Quinn

.