On Aug 17, 2006, at 8:51 AM, Ruby Quiz wrote:

> Now, when solving the Knight's Tour there is a common shortcut that  
> often leads
> to a solution much faster.  Luckily it works here too.  The idea is  
> that, you
> should visit the squares with the least choices first.  Those are  
> the places you
> are likely to run out of options, so getting them out of the way  
> while you still
> have plenty of open squares increases your chances of making it  
> around the
> board.  This is called the JC Warnsdorff heuristic, because JC  
> Warnsdorff made
> the suggestion all the way back in 1823.

So what I was calling the one-step look-ahead is properly called the  
JC Warnsdorff heuristic. I'm glad to learn that.

> The downside of the JC Warnsdorff heuristic is that is doesn't  
> always work.
> Depending on your starting position and which squares you visit  
> first, it can
> paint itself into a corner.  The problem is more common on certain  
> board sizes,
> but it does happen.  The upside is, it's so darn quick (because it  
> doesn't
> backtrack), you can do multiple searches and still be quicker than  
> the brute
> force approach.  If one attempt fails, just try again.  Most  
> solutions used this
> approach.

Re: ... because it doesn't backtrack ...

The heuristic can be used to improve a backtracking solver. The  
interesting question is whether backtracking is ever better than  
restarting. I think there are such situations. One might write a  
solver that tries backtracking a little first and then does a restart  
as Plan B. Of course, one would have to make a precise definition of  
what "a little" means ;)

Regards, Morton