Running The Program

Now that we have finished our first puzzle-solving program, we can run it to find all possible solutions for the Meteor puzzle. The source code described in the previous sections is found in the meteor.initial package of the source download. This package contains a Solver class that has a solve() method and a main() method to start the program. The constructor of the Solver class initializes all puzzle pieces and adds them to pieceList. We can launch the program using java meteor.initial.Solver.

The program starts searching for solutions, but as you will notice, it doesn't seem to find any. Actually, it does find all possible solutions, but you will have to be very patient. It takes several hours to find just one solution. Our test computer, an Athlon XP 1500+ with 512MB of RAM running RedHat Linux 7.2 and Java 1.4.0, finds the first solution after about eight hours. Finding all of them would take several months, if not years.

Clearly, we have a performance problem. A first candidate for optimization is the puzzle-solving algorithm. We're currently using a naive, brute-force approach to find all possible solutions. We should try to fine tune this algorithm. A second thing we can do is to cache temporary data. For instance, instead of recalculating the permutations of a piece every time, we could cache those permutations. Finally, we can try to apply some low-level optimization techniques, like avoiding unnecessary method calls. In the next sections, we'll study these optimization techniques.