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