The FillUp Algorithm
A second downside of our initial algorithm is that it intrinsically generates a lot of islands. This happens because we take one permutation of a piece and move that over the board before switching to the next permutation of the piece. For instance, in Figure 5 we have moved the current permutation of the blue piece to its third possible board position. As you can see, this generates an island at the top of the board. While the islanddetection pruning we added in the previous section will generate drastic performance improvements because of the large number of islands we're generating, it would be even better if we could update our algorithm to minimize the number of islands it generates in the first place.
To reduce the number of islands we generate, it would be best if our algorithm concentrated on filling empty board positions. So instead of just focusing on trying every possible way of tiling the board, we'll try to fill the board lefttoright, toptobottom. This new puzzlesolving algorithm is shown in Listing 9:
Listing 9. The fillup puzzlesolving algorithm

Our new approach tries to fit any available piece on the first empty board cell. Just trying all possible permutations of all available pieces is not enough. We should also try to cover the empty board cell with any piece cell in the piece. In the initial algorithm, we silently assumed that we were manipulating the piece using its first cell. Now we have to try every cell in the piece, as illustrated in Figure 6. The current permutation of the pink piece does not fit on the board when we try to put the piece cell with index 0 on board position 5 (circled in Figure 6). However, it does fit when we use the second piece cell.
Figure 6. The cells of a piece
Running the updated program
When we ran our initial program, it failed to find any solutions in a reasonable amount of time. Let's try again with our improved algorithm and islanddetection pruning. The code for this version of the program can be found in the packagemeteor.algorithm
. When we launch it using java meteor.algorithm.Solver
,
we almost immediately see solutions popping up. Our test computer
calculates all 2,098 possible solutions in 157 seconds. So we've made a
gigantic performance improvement: from several hours per solution to
less than onetenth of a second. That's roughly 400,000 times as fast!
As an aside, the initial algorithm combined with island detection
pruning completes in 6,363 seconds. So the pruning optimization causes
a 10,000fold speedup, while the fillup algorithm generates an extra
40fold speedup. It clearly pays off to spend some time studying your
algorithms and attempting to optimize them. View Optimize your Java applications performance Discussion
Page: 1 2 3 4 5 6 7 8 9 10 11 Next Page: Caching Intermediate Results