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