Improving The Algorithm

Take a look back at Listing 1 and think about how we might be able optimize our initial puzzle-solving algorithm. A good way to optimize an algorithm is to visualize it. Visualisation allows us to get a better understanding of the process being implemented and its possible downsides. The next sections discuss two inefficiencies we can discern. We leave the actual visualisation code for our puzzle-solving program to the interested reader.

Island detection pruning

The algorithm in Listing 1 fits pieces (or more precisely, the piece cells of a piece) onto every position of the board. Figure 4 shows a possible board situation at the beginning of the process. The current permutation of the blue piece has been placed on the first available board position and the current permutation of the yellow piece has moved to its second possible board position. Our algorithm then continues with the third piece, and so on. However, if we look carefully at Figure 4, it's clear that there will be no possible solutions for the puzzle with the blue and yellow pieces in these positions. The reason is those two pieces have formed an island of three neighbouring empty cells. Because all the puzzle pieces consist of five cells, there is no way to fill this island. All the effort that our algorithm exerts trying to fit the remaining eight pieces on the board is useless. What we need to do is cut off our algorithm if we detect an island on the board that cannot be filled.

Figure 4. An island on the board

Text books call this process of interrupting a recursive search algorithm pruning. Adding a pruning function to our Solver class is easy. Before every recursive call to the solve() method, we check for islands on the board. If we find an island consisting of a number of empty cells that is not a multiple of five, we do not make the recursive call. Instead, the algorithm continues at the current level of recursion. Listings 7 and 8 show the necessary code adjustments:

Listing 7. A puzzle-solving algorithm with pruning

public class Solver { public void solve() { ... if (!prune()) solve(); ... } private boolean prune() { /* We'll use the processed field of board cells to avoid infinite loops */ board.resetProcessed(); for (int i = 0; i < Board.NUMBEROFCELLS; i++) { if (board.getBoardCell(i).getIslandSize()%Piece.NUMBEROFCELLS != 0) { // We have found an unsolvable island return true; } } return false; } }

Listing 8. The getIslandSize() method

public class BoardCell { public int getIslandSize() { if (!isProcessed() && isEmpty()) { setProcessed(true); // Avoid infinite recursion int numberOfCellsInIsland = 1; // this cell for (int i = 0; i < Cell.NUMBEROFSIDES; i++) { BoardCell neighbour=(BoardCell)getNeighbour(i); if (neighbour != null) { numberOfCellsInIsland += neighbour.getIslandSize(); } } return numberOfCellsInIsland; } else { return 0; } } }