JAVA N on N puzzle game - heuristic method resolver

Java heuristic N puzzle solver.

Assignment introduction

In this Java assignment we will solve N on N Puzzle games using heuristic algorithems. First we will shuffle the board x number of times. Then the program will use heuristic methods to find the path to the solution.
In this exaple application there are two implimentations:

Search in width: This method will always find the best solution.
Greedy search: This method uses less system ressources then the 'width search' and often gets a good solution.

The system evaluates each board position calculating the Manhattan distance between two boards.

Assignment downloads

Executable jar file:	Launch the application
Source code:	puzzle.zip
Discussion:	Click here to post/read comments on this assignment

Solution info

How the program works

When you launch the application you will see the following window:

The left board shows the goal, the right board is the starting point.
Shuffle the board 'x' times.
Here you can run through the different steps from startpoint until solution.
Use these buttons to see the next or previous step.
Start the algorithm that will find the solution

Please note:

The first tab 'width' will always search for the shortest solution, but it takes a lot of memory. Therefore it may cause 'OutOfMemoryException' if the puzzle it tries to solve is too hard.

The code explained

Two packages: 'gui' and 'logic' with the following classes:

StartUp.java

logic

ManhattanComparator.java
ProblemSolver_GreedySearch.java
ProblemSolver_Width.java
ProblemSolver.java
PuzzleNumber.java
PuzzleState.java

Startup.java

This class contains the presentation layer for this application.

PuzzleState.java

An instance of this class represents a puzzle containing the numbers on a defined position. Each puzzle state has a reference to its parent. Important methods:

move(int direction) Move a number in the puzzle into the specified direction.
List getSuccessors() Get all PuzzleState objects that can be a result after you make a move in any direction.
PuzzleState clone() Get an exact copy of the given PuzzleState.
equals(Object object) Check if the given PuzzleState is equal to another PuzzleState. By implementing this method we can check if any collection contains a PuzzleState object that is the same. (Also see ManhattanComparator.java)
shuffle(int numberOfMoves) Shuffle the current puzzle state x number of times.
int getManhattanDistance(PuzzleState otherPuzzleState) Calculate the Manhattan distance between two PuzzleState s.

ManhattanComparator.java

This is an implemenation of java.util.Comparator. We will use this comparator to put PuzzleStates in 'ordered' Collections (like TreeSet). The objects in the collection will be ordered based on the comparator its implementation.

ProblemSolver.java

This is an abstract class. Each heuristic method implementation should inherit from this class. If you plan to implement a new heuristic method in this application you will have to inherit from this class.

ProblemSolver_Width.java

This ProblemSolver will search for the 'best' solution using a search algorithm that searches in the 'width'.

ProblemSolver_GreedySearch.java

This ProblemSolver will search for the 'a' solution (not necessairily the 'best' solution like the ProblemSolver_Width) It uses a search algorithm that is called the 'greedy search'.

FAQ

How do I change the target to search for?

Change the method implementation of setATarget(PuzzleState puzzle) method in the gui.Startup class

How do I change the number of rows/columns of the puzzle?

Change the static values of PuzzleState.NMBR_OF_ROWS and PuzzleState.NMBR_OF_COLUMNS

How do I add a new heuristic method implementation?

Inherit from the abstract class ProblemSolver.java and implement the getSolution method. Also add a line in the StartUp.java class to add a 'tab' to the tabbed pane that will trigger your ProblemSolver implementation.

Java school assignments