Jonathan E. Paton [mailto:[EMAIL PROTECTED] wrote:
>What about a meet-in-the-middle algorithm, with one graph > created by running forwards, and one by running backwards. > You would require to calculate ALL board positions to a > given depth in each direction. Yes, good thought. Unfortunately, the number of board states becomes very large with increasing N. It is just manageable at N=7, but I'm also interested in pushing this as far as I can. Perhaps I'll put some adaptive logic in so that small boards are solved quickly, while large boards can still be solved without running out of space. Ronald J Kimball [mailto:[EMAIL PROTECTED] wrote: > Since the rotations/reflections are equivalent, you could save a lot of > memory by only caching a canonical instance of each board state. Yes, I'm planning to do this next. It should help a little, trading space for time. Steffen Mueller [mailto:[EMAIL PROTECTED] wrote: > I think you could either use your hard disk for caching (I know it's > slower, but CPU&time may not be the limiting factor) or think about > using a more compact representation of the board - What about a bit > string? Or a C-style array? There are modules for that. Oh, and > pack/unpack are friends. :) Yes, I've already converted to a bit string for board keys. Perhaps more interesting: I started using a tied hash for the board keys. When it runs out of memory, I start the program over, and it reports the correct number of hash keys, and uses less memory (for a while). So I think my problem is a memory leak somewhere. There is one main recursive routine, which creates a number of "my" variables. I suspect that I'm somehow keeping a reference to a variable that I shouldn't be, and that's causing my memory problem. [I looked for memory leak posts on the boards, and the general consensus is that most of them have been plugged. I can't presume to have found one with such a simple program, especially not using any modules.] Cheers, QM ===== ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Quantum Mechanics: The dreams stuff is made of __________________________________________________ Do you Yahoo!? Yahoo! Web Hosting - establish your business online http://webhosting.yahoo.com
