A Star 8 Puzzle

Project Objectives

In this project we will implement a model of the 8-Puzzle and use the A* algorithm to find solutions from input board configurations

8-Puzzle

The 8-Puzzle is a sliding puzzle game. It consists of a 3X3 board containing 8 interlocking tiles, numbered from 1 to 8, and one empty space. The board can be manipulated by sliding tiles into the empty space. The goal of the puzzle is to manipulate the board into a goal configuration. The goal configuration looks like this:

1 2 3
4 5 6
7 8 0

where each number represents its tile and zero represents the empty space. Board manipulations can be thought of as exchanging the empty space, zero, for one of its neighbor tiles: up, down, left, right. For example, if we perform up from:

1 2 3
4 5 6
7 8 0

it produces the board configuration:

1 2 3
4 5 0
7 8 6

As a first step, we will create a model of the 8-Puzzle, called EightPuzzle. We will model the 8-Puzzle as a 3X3 array and allow clients to perform up, down, left, and right operations on the tiles. Here is the EightPuzzle API:

void EightPuzzle()
void EightPuzzle(int[][] puzzle)
boolean isSolved()
void U()
void D()
void L()
void R()
Hashtable< EightPuzzle,String>
getNeighbors()
int h()
String toString()

void EightPuzzle() should construct a new puzzle object in the goal configuration

void EightPuzzle(puzzle) should construct a new puzzle object, starting from the configuration specified by the input puzzle matrix.

boolean isSolved() returns true if the puzzle array is in the goal configuration and false otherwise.

void U() shifts the 0 tile up. If the 0 tile is already in the top row, do nothing.

void D() shifts the 0 tile down. If the 0 tile is already in the bottom row, do nothing.

void L() shifts the 0 tile left. If the 0 tile is already in the left column, do nothing.

void R() shifts the 0 tile right. If the 0 tile is already in the right column, do nothing.

Hashtable< EightPuzzle,String> getNeighbors() returns a hashtable that maps each of the boards that can be created by performing an up, down, left, and right operation with the strings U, D, L, and R, respectively.

int h() returns the heuristic value calculated from the current board. Use the Manhattan Distance heuristic.

String toString() returns a String representation of the board array.

A* (A Star)

Implement A* to search through EightPuzzle space. It should take as input an EightPuzzle object and search until it finds an EightPuzzle that isSolved() returns true. The search should return a String that describes the sequence of moves that will transform the input board into the goal board. For example, given an input:

1 0 3
4 2 5
7 8 6

A* should return, DRD. Implement the A* search as a static method in a class named AStar. Here is the AStar API:

public static String search(EightPuzzle start)

The first part is a working implementation of the EightPuzzle API. The following test:

public class EightPuzzleTest {
public static void main(String[] args) {
int[][] puz = new int[3][3];
puz[0][0] = 1;
puz[0][1] = 0;
puz[0][2] = 2;
puz[1][0] = 7;
puz[1][1] = 5;
puz[1][2] = 4;
puz[2][0] = 8;
puz[2][1] = 6;
puz[2][2] = 3;
EightPuzzle p = new EightPuzzle(puz);
p.L();
p.D();
p.R();
System.out.println(p);
}
}

should print:

7 1 2
5 0 4
8 6 3

The second part is an implementation of the AStar API. The following test:

public class AStarTest {
public static void main(String[] args) {
int[][] puz = new int[3][3];
puz[0][0] = 1;
puz[0][1] = 0;
puz[0][2] = 2;
puz[1][0] = 7;
puz[1][1] = 5;
puz[1][2] = 4;
puz[2][0] = 8;
puz[2][1] = 6;
puz[2][2] = 3;
EightPuzzle p = new EightPuzzle(puz);
System.out.println(AStar.search(p));
}
}

should print out DRDLLURURDD.