Warnsdorff: choose a successor with the fewest further moves. i.e. choose a son with the fewest grandsons.
http://www.slac.stanford.edu/cgi-wrap/getdoc/slac-pub-0261.pdf Ira Pohl in January 1967 suggested that in case of ties, choose a son with the fewest great-grandsons. In principle, the tie breaking procedure can be carried through to arbitrary levels of grandsons. Pohl claimed that (and I have not verified it yet) with one level of tie-breaking the Knight's Tour always succeeds. Your idea (ktourw2) of keeping a stack of possibilities sorted by the number of grandsons, is good. If the initialization of the stack is modified to all possible starting positions (i.e. all positions), sorted by the number of successors, then it would have the advantage of always finding a solution if there is one. This proves the point you made several days ago re the advantage of sorting the stack. Since the straightforward Warnsdorff works most of the time, and is very fast, perhaps the following is a good alternative: ktourw=: ktourwfast :: ktourw2a That is, use the fast implementation unless it fails, whence use a slower one (but still fast) that always works. ----- Original Message ----- From: John Randall <[EMAIL PROTECTED]> Date: Monday, November 24, 2008 15:18 Subject: Re: [Jprogramming] Project Euler Problem 216 To: Programming forum <[email protected]> > Roger Hui wrote: > > > Discussions of efficiency on this problem must > > involve Warnsdorff's algorithm, invented in 1823. > > ktourw 8 takes 0.003 seconds and ktourw 74 > > takes roughly the same time as ktourx 8. > > > > The heuristic is that on each step, choose a > > successor having the fewest further moves. > > I don't know yet whether I've made a mistake > > in the implementation or whether the heuristic > > sometimes fails: > > My implementation follows. It is not as fast as ktourw, > but it agrees > with it, and gives plausible results for all arguments, > including 11. > > ktourw2=:3 : 0 > m=.kmoves y > p=.*:y > stack=.<0 > while. #stack do. > s=.>{: stack > if. (#s)=p-1 do. (,~y)$/:s,(i.p)-.s return. end. > ms=.m-.&.> < s > t=.({:s){::ms > stack=.(}:stack), (<s),&.> t \: #&> t { ms > end. > ) > > To ensure it was doing the right thing, I reduced the graph each > time. > Obviously this is quite expensive. > > Best wishes, > > John ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
