Search

Useful Lists

Web Host
Partners

Online Manuals

By Erwin Vervaet & Maarten De Cock - 2003-12-15 Page:  1 2 3 4 5 6 7 8 9 10 11

## 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
 `````` public void solve() { if (!pieceList.isEmpty()) { // We'll try to find a piece that fits on this board cell int emptyBoardCellIdx = board.getFirstEmptyBoardCellIndex(); // Try all available pieces for (int h = 0; h < pieceList.size(); h++) { Piece currentPiece = (Piece)pieceList.remove(h); for (int i = 0; i < Piece.NUMBEROFPERMUTATIONS; i++) { Piece permutation = currentPiece.nextPermutation(); /* Instead of always using the first cell to manipulate the piece, we now try to fit any cell of the piece on the first empty board cell */ for (int j = 0; j < Piece.NUMBEROFCELLS; j++) { if (board.placePiece(permutation, j, emptyBoardCellIdx)) { if (!prune()) solve(); board.removePiece(permutation); } } } /* Put the piece back into the list at the position where we took it to maintain the order of the list */ pieceList.add(h, currentPiece); } } else { puzzleSolved(); } } ``````

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 `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 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.

View Optimize your Java applications performance Discussion

Page:  1 2 3 4 5 6 7 8 9 10 11 Next Page: Caching Intermediate Results