There's a thread on the Knight's Tour on Slashdot:
http://developers.slashdot.org/article.pl?sid=08/11/30/1722203 .
The original poster was proud of his 60-line Python solution but it looks
like someone later posted a 60-line C++ solution.
On Wed, Nov 26, 2008 at 12:54 PM, Roger Hui <[EMAIL PROTECTED]> wrote:
> 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
>
--
Devon McCormick, CFA
^me^ at acm.
org is my
preferred e-mail
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
