On Thu, Mar 13, 2003 at 01:22:26PM -0800, Quantum Mechanic wrote: > I came at it from another direction, starting out > caching the board state (equivalent to @state) for > each board seen. [In most cases, there are several > "paths" to a given board state.] > > I also used some other speedups, like precomputing the > jump neighbors for each hole, and computing all > rotations/reflections of each board and caching all of > them (there are 5 equivalents for each board state, > besides itself). > > The problem space soon blows up rather large for > larger board sizes. For instance, I've seen it run out > of memory on a large machine (caching boards) for N=7 > (7 pegs on a side, 28 holes total), having cached > about 1M boards.
Since the rotations/reflections are equivalent, you could save a lot of memory by only caching a canonical instance of each board state. For example, number the holes with powers of 2, and only cache the rotation/reflection with the lowest sum of occupied holes. Of course, checking the cache would also require finding the canonical state, so you would be saving memory by adding runtime. Ronald
