Brainvita puzzle
Brainvita is a popular board game for kids sold in India. It may be known
under different names in the west. The game works like chinese checkers and
the goal is to be left with as few marbles on the board as possible.
The best possible ending is to end with only one marble and with the last
marble at the middle of the board.
This is my attempt to solve the puzzle in the python programming language.
Initially, a 800 MHz CPU + 256 MB RAM were insufficient to solve the problem.
The problem turned out to be due to inefficient storage representation and
unnecessary deep copies.
Once I profiled the program and compressed the board into a single 64 bit
number (need 33 bits to represent the board), it was easy. The above program
took about 30 mins and half a million searches before it found the solution.
Caveats: though the above program correctly searches the solution, uncompressing the
64 bit integer above on 32 bit processors doesn't work correctly and I had
to "hand correct" the problem.
Enjoy the solution to the problem!
Aug, 2001
Arun Sharma <arun@sharma-home.net>
