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.

Figure 5. Generating islands

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:

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.

Figure 6. The cells of a piece

Running the updated program