Warnsdorff'a algorithm is useful for more than the knight's tour.
It is applicable for Hamilton path problems in general.
The following is an application of Warnsdorff's algorithm
to the n queens problem, using John's idea of stacking
all sons sorted by the number of grandsons, favoring a son
with the fewest grandsons. It always finds a solution if there
is one.
Results for n=20:
iterations seconds
queens_dfs simple DFS 199635 5.73
qdfs1 Warnsdorff 111 0.00439
] t=: queens_dfs 20
0 2 4 1 3 12 14 11 17 19 16 8 15 18 7 9 6 13 5 10
qcheck t
1
] t1=: qdfs1 20
0 4 8 12 2 17 10 14 3 19 7 13 6 18 15 5 9 16 1 11
qcheck t1
1
queens_dfs=: 3 : 0
if. 1>:y do. i.y return. end.
stack=. ,&.> i.->.-:y
while. #stack do.
s=. >{:stack
if. y=#s do. return. end.
stack=. (}:stack),(<s),&.>(i.-y)-.s+((-i.)#s)*/_1 0 1
end.
)
qdfs1=: 3 : 0
if. 1>:y do. i.y return. end.
ind=. i.-y
stack=. ,&.> i.->.-:y
while. #stack do.
s=. >{:stack
if. y=#s do. return. end.
d=. ((-i.)1+#s)*/_1 0 1
c=. s,"1 0 ind-.s+}.d
stack=. (}:stack),<"1 c\:[EMAIL PROTECTED]"1 2 d+"2 1 c
end.
)
qcheck=: 3 : 0
assert. 1=#$y
assert. (i.#y)-:/:~y
assert. (=i.#y) +.(-/~y) (= +: (=-)) -/~i.#y
1
)
----- Original Message -----
From: Roger Hui <[EMAIL PROTECTED]>
Date: Tuesday, November 25, 2008 7:50
Subject: Re: [Jprogramming] Project Euler Problem 216
To: Programming forum <[email protected]>
> 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
