The Fill-Up 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 island-detection 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 left-to-right, top-to-bottom. This new puzzle-solving algorithm is shown in Listing 9:Listing 9. The fill-up puzzle-solving 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.
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 island-detection pruning. The code for this version of the program
can be found in the package
meteor.algorithm. When we launch it using
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 one-tenth 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,000-fold speedup, while the fill-up algorithm generates an extra
40-fold speedup. It clearly pays off to spend some time studying your
algorithms and attempting to optimize them.