On Aug 16, 2006, at 9:49 AM, James Edward Gray II wrote:

> Oddly, it has some super weird behavior on my box.  It will do any  
> size grid less than or equal to 17 in the blink of my eye.  When I  
> pass 18 or higher it seems to hang forever.  It's not eating  
> memory, but it does max out a CPU.  It's very odd.
>
> James Edward Gray II

I think it might be because the garbage collector is working extra  
hard. I have observed similar behavior with an improved version of my  
Pen and Paper program. Whereas the original version was brought down  
on its knees by a 7x7 grid, the new one can do a 9x9 in 0.1 sec or an  
11x11 in about 10 sec, but strangely had not completed a 10x10 when I  
killed it after running for 20 minutes. I have determined, in the  
10x10 case, that my algorithm produces a huge amount of garbage and  
that the GC is running constantly.

The improvement in my program comes from incorporating Darren Kirby's  
look-ahead technique into the search algorithm. As he asserted, it  
really speeds things up. I'm at a loss as to why Kirby's technique  
doesn't work on a 10x10 grid. It has something to do with my  
requirement for a cyclic solution -- if I remove this requirement,  
the program finds a 10x10 solution in 0.1 sec, a 20x20 in 0.2 sec, a  
39x30 in 0.4 sec, and a 50x50 in 0.6 sec (close to O(n log n) behavior).

Regards, Morton