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. ----- Original Message ----- From: Roger Hui <[EMAIL PROTECTED]> Date: Friday, November 21, 2008 8:55 Subject: Re: [Jprogramming] Project Euler Problem 216 To: Programming forum <[email protected]> > > This is efficient. I think the problems may come on > scaling up. The > > example given requires about 200,000 iterations through the > main loop with > > a maximum stack size of 120. In my experience these are > the main > > parameters affecting things. Please note that my > ignorance is probably > > the major factor in writing efficient programs. For > Project Euler #216 I > > will shortly have a separate query about preventing integers > from being > > promoted. > > http://www.jsoftware.com/jwiki/Essays/Knight's_Tour > > The Knight's Tour is probably an example of the situation > you described. ktour uses depth first search and looks > very much like the queens_dfs verb discussed yesterday. > ktour 7 goes through 137459 iterations with a maximum > stack size of 87, taking a little over 3 seconds. ktour 8 > takes about 470 seconds. > > The problem with ktour is not "scaling up". The problem is > that the search trimming is too simple-minded (trim if no > next move). ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
