Developer Forums | About Us | Site Map


Useful Lists

Web Host
site hosted by netplex

Online Manuals

Optimize your Java applications performance
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 */

          /* 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 */
        // 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! */


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

First published by IBM developerWorks

Copyright 2004-2021 All rights reserved.
Article copyright and all rights retained by the author.