Solitaire is a game for one player. The goal is to reduce a set of pins so that only one pin is left. The starting set of pins looks like that:
1 1 1
1 1 1
1 1 1 1 1 1 1
1 1 1 0 1 1 1
1 1 1 1 1 1 1
1 1 1
1 1 1
A move in this game is to jump with one pin over another pin. The pin over which is jumped is removed. eg:
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 ----> 1 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
The game is won if there is only one pin left, exactly in the middle of the board.
The question in the project was how many solutions exist for this game. This problem is of exponential complexity and it takes very long to solve it with the full set of pins. To get some results we were given sets with 13,14,15,16,17 and 18 pins.
My serial solution to this problem introduces the use of permutations in the search to speed up the calculation and is a lot of faster than a simple approach.
The parallel solution is based on PVM which is a library for message passing in a heterogenous network of computers.
The program is designed to run efficiently with up to 100 workstations. If you want to use more workstations some heavy extensions to the used scheme should be programmed otherwise the solution won't be very efficient.
If you are interested: download the sources.
To compile you need to have PVM, which you can get here .