From: Morton Goldberg <m_goldberg@...>
Date: 2006-08-19T04:26:37+09:00
Subject: Re: [SUMMARY] Pen and Paper (#90)

On Aug 17, 2006, at 10:23 AM, Morton Goldberg wrote:
> 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 ;)

I have implemented such a program, one which applies the Warnsdorff  
rule starting from a random position and which allows backtracking to  
be turned on or off. I find the results convincing --  backtracking  
does have value even when the Warnsdorff rule is used, especially  
when a cyclic solution is wanted.

17x17 grid -- cyclic solution required -- average of 5 runs for each  
case

no backtracking:   10.2562504 sec
with backtracking:  1.1582514 sec

I appologize if I'm being a bore on this subject, but I hope at least  
a few people will be interested in this result.

Regards, Morton