Finding A Working Solution

In this section, we'll discuss an initial implementation of our puzzle-solving program. This will involve quite a few code fragments, so bear with us; once we have explained the basic algorithms involved, we will start optimizing. Source code for this initial implementation as well as the optimizations we'll discuss later in the article, is available in Resources.

The puzzle-solving algorithm

Not all of these "possibilities" would actually work, of course. For instance, some have a piece hanging over the edge of the board, which clearly does not lead to a solution. Recursively repeating this process for all pieces brings us to a first algorithm that will find every possible solution by trying every possible tiling of the board using the pieces. Listing 1 presents the code for this algorithm. We use a simple ArrayList object called pieceList to hold all the pieces. The board object represents the puzzle board, which we will discuss shortly.

public void solve() {
  if (!pieceList.isEmpty()) {
    // Take the first available piece
    Piece currentPiece = (Piece)pieceList.remove(0);

    for (int i = 0; i < Piece.NUMBEROFPERMUTATIONS; i++) {
      Piece permutation = currentPiece.nextPermutation();

      for (int j = 0; j < Board.NUMBEROFCELLS; j++) {
        if (board.placePiece(permutation, j)) {
          
          /* We have now put a piece on the board, so we have to
             continue this process with the next piece by 
             recursively calling the solve() method */
          
          solve();
          

          /* We're back from the recursion and we have to continue
             searching at this level, so we remove the piece we
             just added from the board */
          
          board.removePiece(permutation);
        }
        // Else the permutation doesn't fit on the board
      }
    }

    // We're done with this piece
    pieceList.add(0, currentPiece);
  }
  else {
    
    /* All pieces have been placed on the board so we
       have found a solution! */
    

    puzzleSolved();
  }
}

Now that we have our basic algorithm set up, we need to investigate two other important issues:

• How will we represent a piece of the puzzle?
• How will we implement the puzzle board?

In the algorithm shown in Listing 1, we used a Piece class and a Board class. Now let's take a look at the implementation of those two classes.