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

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

Our puzzle-solving program will calculate all possible solutions for the Meteor puzzle. This means that we will have to exhaustively search for every possible tiling of the board using the pieces. One step in accomplishing this task is to determine all the permutations of a piece. A permutation is a possible way of placing a piece on the board. Knowing that every piece can be flipped upside down and can be rotated around the six sides of one of its hexagons, we arrive at a total of 12 (2 x 6) possible ways to put a piece on one position of the board. With 50 board positions, the total number of possible ways to put a single piece on the board equals 600 (2 x 6 x 50).

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.

Listing 1. The initial puzzle-solving algorithm
 `````` 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.

View Optimize your Java applications performance Discussion

Page:  1 2 3 4 5 6 7 8 9 10 11 Next Page: The Piece Class