Finding A Working Solution
In this section, we'll discuss an initial implementation of our puzzlesolving 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 puzzlesolving algorithm
Our puzzlesolving 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.

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