--- "Evan A. Zacks" <[EMAIL PROTECTED]> wrote: > Japhy wrote a peg game solver awhile back: > > http://www.perlmonks.org/index.pl?node_id=121626
Yes, that's very good, and uses minimal code. However, it's not immediately extensible to any size in it's present form. It's also somewhat brute force, though there are some speedups. For example, only starting with the 1st 5 pegs works well. There's only 1 redundant peg in that list (numbered from 0, pegs 1 & 2 are equivalent). 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. But N=8 finds a solution in a few minutes. Stopping at the first solution, it doesn't run out of memory. I'm working on balancing time and memory so that larger N will still find a solution in a reasonable time, but not run out of memory. I'll have to check out the book mentioned in the other post for some tips. Thanks, QM ===== ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Quantum Mechanics: The dreams stuff is made of __________________________________________________ Do you Yahoo!? Yahoo! Web Hosting - establish your business online http://webhosting.yahoo.com
