speeding up help.. probably deepcopy()...

[Bengt Richter]

On Sun, 08 Dec 2002 17:02:23 +0000, eugene kim <eugene1977 at hotmail.com> wrote:

>http://gotofreegames.com/IQGame/free_peg_game.htm
>
>i am trying to make a program to solve the game in above page.
>It works fine.. but it's still finding solutions with 45 mins run time.
>lol
>
>and i have newbie question ..
>is always pass by reference in python?
>(in java, it's always pass by value..afaik)
>It seems like scoping rules changed with new python.
>
>
>thank you
>--
>I store 14balls information and pass it as I move one ball until there's no 
>possible move
[...snip code ...]
Since the pegboard has 15 holes that can either be occupied
or not, that is 2**15 states possible for the board (including
before choosing the first empty, and an impossible all-empty solution,
and probably a number of other impossible states).

The point is that an integer (15 bits) can represent the board status very compactly,
and transformations could be done with bit mask operations. And if you wanted to
store masks applicable from any given (of 15) position, you could store that in
an indexed list. You could even do the same for info relevant to any board state,
since there are only 32768 of them, which is not a long list. A particular game
would be a sequence of peg/destination selections at 4+4 bits per jump, which is only
2**(4+4)==256 possible jumps (maybe there is a useful table for info about jumps?),
and I suppose 15 max jumps for a game? That would be 30 hex characters (or one long
integer, but if so use 1-15 for positions so you don't lose leading zeroes in a
variable width number) to represent any game log if so.

Perhaps this will give you some ideas for speedups etc.

Regards,
Bengt Richter