Also interesting is Haskell version[0] and OCaml version[1]. [0] http://haskell.org/haskellwiki/The_Knights_Tour [1] http://www.reddit.com/r/programming/comments/7gk4m/solving_the_knights_tour_in_30_lines_of_haskell/c06lpv7
(from http://www.reddit.com/r/programming/comments/7glwj/solving_the_knights_tour_in_6_lines_of_j_using/c06lq7e ) 2008/12/1 Devon McCormick <[EMAIL PROTECTED]>: > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
