I'm only including this example because it was so outrageous! A government agency was investigating
various hardware platforms for (what I guess was) HPC cryptographic applications. Obviously, they were
not sharing any of their actual code, but instead specified a number of number crunching challenges for
large scale multiprocessors. I took up the challenge of Solitaire with a 16-way E6000 and more than 8GB
o o o \* \* \* o o o 5 6 7 5 6 7
o o o \* \* \* o o o 2 3 4 2 3 4
o o o o o o o \* \* \* \* \* \* \* o o o o o o o 0 1 7 4 0 1 0 2 5
o o o o o o o \* \* \* o \* \* \* o o o \* o o o 6 3 1 x 1 3 6
o o o o o o o \* \* \* \* \* \* \* o o o o o o o 5 2 0 1 0 4 7
o o o \* \* \* o o o 4 3 2
o o o \* \* \* o o o 7 6 5
Fig.1 Fig.2 Fig.3 Fig.4 Fig.5
In Figs.1-3 a "o" represents a hole, and a "\*" a marble in a hole. Thus, Fig.1 shows the empty board,
Fig.2 the staring position (32 marbles), and Fig.3 the target end position. My solution was to encode
each board position as 33 bits, with 0 for a hole and 1 for a marble. Threads in a worker pool took known
board positions from a work pile and found all possible news moves, which were then added to the
work pile. Exploiting rotational and reflectional symmetry, each new board position becomes up to eight
possible board positions.
By coding the 33 bits as shown in Figs.4-5 I was able to make rotation a simple byte swap. Reflection is
harder, but only needs to be done once (since the remaining three reflections and be achieved by rotating
the first reflection). The really extravagant part was adding an 8GB char array to record board positions
that had already been seen (and which, therefore didn't require to be explored again).
The result was a solution in just 2 seconds, with all possible board positions being found within 30
seconds. Sun hardware and my expertise in multithreading has moved on a lot in the intervening years.
I'm now itching to try the exercise again on an T5220!