The difference between ktour and kt, is that ktour
always picks the lowest numbered successor
whereas kt always picks the highest numbered one.
The effect of kt (and the same result as kt) can be
achieved as follows:
ktourx=: 3 : 0
if. 1>:y do. i.,~y return. end.
m=. |.&.> kmoves y
p=. *:y
stack=. ,&.>y (<:/[EMAIL PROTECTED] #&, * +/ ]) i.>.-:y
while. #stack do.
s=. >{:stack
if. a: e. (((i.p)-.s){m)-.&.><s do.
if. (#s)=p-1 do. (,~y)$/:s,(i.p)-.s return. end.
stack=. }:stack continue.
end.
stack=. (}:stack),(<s),&.>s-.~({:s){::m
end.
)
Only the initializations of m and stack were changed.
ktourx is faster than kt by another factor of 2,
due to its not having to sort the stack on each iteration.
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:
1:@ktourw :: 0:"0 i.10 10
0 1 0 0 0 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 0
1 1 1 1 1 1 1 1 0 1
0 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 0 1 1 0
1 1 1 1 1 0 1 0 1 0
1 1 1 1 1 1 1 1 0 1
The failures for y e. 0 2 3 4 are understandable.
The others are not.
ktourw 11
|index error: ktourw
| s=.s, (]{~[:(i.<./)(<s)[EMAIL PROTECTED]&>~m{~])s-.~({:s){::m
----- Original Message -----
From: John Randall <[EMAIL PROTECTED]>
Date: Sunday, November 23, 2008 5:39
Subject: Re: [Jprogramming] Project Euler Problem 216
To: Programming forum <[email protected]>
> Roger Hui wrote:
> > http://www.jsoftware.com/jwiki/Essays/Knight's_Tour
> >
> > ktour 8 now much faster, from 470 seconds to 12 seconds.
> > Main loop from 17,739,768 iterations to 302,701 iterations.
>
> Even faster:
>
> kt=: 3 : 0
> if. 1>:y do. i.,~y return. end.
> m=. kmoves y
> p=. *:y
> stack=. ,&.>|.y (<:/[EMAIL PROTECTED] #&, * +/ ]) i.>.-:y
> while. #stack do.
> stack=./:~ stack NB. line added
> s=. >{:stack
> if. a: e. (((i.p)-.s){m)-.&.><s do.
> if. (#s)=p-1 do. (,~y)$/:s,(i.p)-.s return. end.
> stack=. }:stack continue.
> end.
> stack=. (}:stack),(<s),&.> s-.~({:s){::m
> end.
> )
>
> time 'ktour 8'
> 12.7458
> time 'kt 8'
> 1.53991
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
