# Optimizations to 8-puzzle

I am a CS student about to enter my junior year. I am attempting to get better and better at programming and thought that this would be a good place to toss my code out there to see if some of you could give me some tips on how to make it better.

If you've got tips as to different websites I could go to for this sort of thing, please don't hesitate to tell me.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/*************************************************************************
* Compilation: javac EightPuzzle.java Execution: java EightPuzzle Dependencies:
* MinPQ.java
*
* AI solution to N-by-N slider puzzle using heuristic function which is depth
* in tree plus number of tiles out of position.
*
* Note: integer 0 corresponds to blank cell
*
* Goal state is of the following form and is hardwired into the dist() and
* manhattan() methods.
*
* 1 2 3 4 5 6 7 8
*
*************************************************************************/

public class EightPuzzle implements Comparable<EightPuzzle> {

private final static int N = 3;
private final static String[] names = { "   ", "  1", "  2", "  3", "  4",
"  5", "  6", "  7", "  8" };
private static int totalEnqueued;
private final static int[][] solved = { { 1, 2, 3 }, { 4, 5, 6 },
{ 7, 8, 0 } };
private int moves;
private int[][] tiles;
private EightPuzzle parent;
private int priority;
private int distance;
int zeroLocX = 0;
int zeroLocY = 0;

// allocate separate memory for new tiles array
EightPuzzle(int[][] tiles) {
this.tiles = new int[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
this.tiles[i][j] = tiles[i][j];

}

EightPuzzle(int[][] tiles, EightPuzzle parent, int moves) {
this.tiles = new int[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
this.tiles[i][j] = tiles[i][j];
this.parent = parent;
this.moves = moves;
priority();
}

// priority
/**
* @return
*/
public int priority() {
int manhatDist = 0;
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++) {
switch (tiles[x][y]) {

case 1:
manhatDist += posDiff(x, y, 0, 0);
break;
case 2:
manhatDist += posDiff(x, y, 0, 1);
break;
case 3:
manhatDist += posDiff(x, y, 0, 2);
break;
case 4:
manhatDist += posDiff(x, y, 1, 0);
break;
case 5:
manhatDist += posDiff(x, y, 1, 1);
break;
case 6:
manhatDist += posDiff(x, y, 1, 2);
break;
case 7:
manhatDist += posDiff(x, y, 2, 0);
break;
case 8:
manhatDist += posDiff(x, y, 2, 1);
break;
case 0:
manhatDist += posDiff(x, y, 2, 2);
break;
default:
break;
}

}
this.priority = manhatDist + moves;
return priority;
}

private int posDiff(int xPos, int yPos, int xGoal, int yGoal) {
int diff = Math.abs(xPos - xGoal);
diff += Math.abs(yPos - yGoal);

return diff;
}

// which board position is closer to the goal board position
/**
*/
@Override
public int compareTo(EightPuzzle b) {
if (b.distance() == distance()) {
for (int i = 0; i < N; i++) {
if (!(Arrays.equals(b.getBoard()[i], this.getBoard()[i]))) { //if any elements are different, we know the arrays are not equal
if (b.priority() > priority()) //but we still need to know whether to return a -1 or 1
return -1;
return 1;
}
}
return 0; //if we make it here they are equal
} else if (b.priority() > priority()) //if the distances are different
return -1;
else
return 1;
}

/**
* @return
*/
public int[][] getBoard() {
return tiles;
}

// does board position equal goal position?
/**
* @return
*/
public boolean isSolved() {
for (int i = 0; i < N; i++) {
if (!(Arrays.equals(tiles[i], solved[i]))) {
return false;
}

}
return true;
}

//for NxN expansion...not quite complete yet.
public int[][] findGoalState() {
int[][] solved = new int[N][N];
int nums = 1;

for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
solved[i][j] = nums;
nums++;
if (nums == (N * N)) {
solved[N - 1][N - 1] = 0;
break;
}
}
return solved;
}

// return sum of Manhattan distances of tiles to their proper position
private int distance() {
this.distance = priority() - moves;
return this.distance;
}

private int getZeroXLoc() {
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
if (tiles[x][y] == 0) {
zeroLocX = x; //finding our zero so we can begin moving tiles
zeroLocY = y;
}
return zeroLocX;
}

private int getZeroYLoc() {
getZeroXLoc();
return zeroLocY;
}

private void assignZeroLoc() {
getZeroYLoc();
}

// return the neighboring board positions
/**
* @return
*/
public EightPuzzle[] neighbors() {
ArrayList<EightPuzzle> tempneighbors = new ArrayList<EightPuzzle>();

assignZeroLoc(); //determines both x and y loc's of the zero

for (int i = -1; i < 2; i++) { //creating all surrounding x coordinates
int p = zeroLocX + i; //current array being looked at
if (p < 0 || p > N - 1)
continue; //meaning these squares are out of bounds
for (int j = -1; j < 2; j++) {
int q = zeroLocY + j; //current index in current array
if (q < 0 || q > N - 1 || (p == zeroLocX && q == zeroLocY) || //if we are out of bounds or at the same square
((Math.abs(zeroLocX - p) + Math.abs(zeroLocY - q))) > 1) //or if delta x + delta y is greater than 1, aka at a diagonal space
continue; //skip this iteration

int[][] temptiles = new int[N][N];

for (int m = 0; m < N; m++)
temptiles[m] = Arrays.copyOf(tiles[m], N); //copy the original board

int tempQ = temptiles[p][q]; //store the value of the value to swap
temptiles[p][q] = 0; //place the 0 in a valid location
temptiles[zeroLocX][zeroLocY] = tempQ; //place the stored value to swap where the 0 was
EightPuzzle neighbor = new EightPuzzle(temptiles, this,
this.moves + 1); //create a new 8 puzzle
totalEnqueued++;

}

}

EightPuzzle[] neighbors = new EightPuzzle[tempneighbors.size()];

return tempneighbors.toArray(neighbors);
}

// print parents in reverse order
/**
*
*/
public void showPath() {
if (parent != null)
parent.showPath();
System.out.println("Move #" + moves + " Priority = " + priority);
System.out.println(toString());
}

// print details of puzzle
/**
*
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
String s = "";
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
s += names[tiles[i][j]] + " ";
s += "\n";
}
return s;
}

/**
* @return
*/
public boolean isSolvable() {
int[] row = new int[(N * N) - 1];
int rowIndex = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (tiles[i][j] != 0) {
row[rowIndex] = tiles[i][j];
rowIndex++;
}
}
}

int inversions = 0;
for (int x = 0; x < row.length; x++) {
for (int y = x; y < row.length; y++)
if (row[x] > row[y])
inversions++;
}
return inversions % 2 == 0;
}

/***********************************************************************
* Test routine.
**********************************************************************/
public static void main(String[] args) {

// 6 moves
int[][] easy0 = { { 1, 2, 3 }, { 7, 0, 5 }, { 8, 4, 6 } }; //<1 second
int[][] hard0 = { { 0, 8, 7 }, { 2, 5, 1 }, { 3, 6, 4 } }; //5.5 minutes
int[][] hard1 = { { 4, 5, 0 }, { 6, 8, 7 }, { 1, 2, 3 } }; //5.5 minutes
int[][] medium0 = { { 2, 3, 1 }, { 7, 0, 8 }, { 6, 5, 4 } }; //1 second
int[][] medium1 = { { 1, 2, 3 }, { 8, 0, 4 }, { 7, 6, 5 } }; //1 second
int[][] medium2 = { { 1, 2, 3 }, { 7, 0, 4 }, { 8, 6, 5 } }; //2 seconds
int[][] twentytwo = { {4, 8, 2},
{3, 6, 5},
{1, 7, 0} };

System.out
.println("Please enter the 3x3 grid in the format \n\"XXX \n XXX  \n XXX\" where X is a number between 0 and 8");
Scanner scan = new Scanner(System.in);
int userEntered = 0;
int[][] userIn = new int[N][N];
try {
while (userEntered < 3) {
String line = scan.nextLine().trim();

for (int i = 0; i < N; i++) {
userIn[userEntered][i] = Integer.parseInt(Character
.toString((line.charAt(i))));

}
userEntered++;
}
} catch (Exception e) {
System.out
.println("Please restart the program and enter the gridin the correct format");
System.exit(0);
}

EightPuzzle x = new EightPuzzle(userIn);
System.out.println(x);

MinPQ<EightPuzzle> pq = new MinPQ<EightPuzzle>();
pq.insert(x);

int nodes = 0;
ArrayList<EightPuzzle> seen = new ArrayList<EightPuzzle>();
//      Stopwatch sw = new Stopwatch();
while (!pq.isEmpty()) {
x = pq.delMin(); //get the minimum key
if (nodes == 0) {
if (!x.isSolvable()) {
System.out                      .println("This is an unsolvable puzzle, please enter a solvable one");
System.exit(0);
}
}
nodes++;

//TODO:make this faster, maybe a binary search tree instead of arraylist
for (int i = 0; i < seen.size(); i++) { //make sure we aren't back tracking.
if (x.compareTo(seen.get(i)) == 0) {
x = pq.delMin();
}
}

if (x.isSolved()) {
//              System.out.println(sw.elapsedTime());
break;
}

EightPuzzle[] neighbors = x.neighbors(); //find and add all neighbors
for (int i = 0; i < neighbors.length; i++)
if (!(x.compareTo(neighbors[i]) == 0)
&& neighbors[i].isSolvable())
pq.insert(neighbors[i]);

}
System.out.println("Total nodes enqueued = " + totalEnqueued);
System.out.println("Nodes expanded = " + nodes);
x.showPath();
}

}

• MinPQ cannot be resolved to a type – tb- Dec 17 '12 at 14:05

In the Constructor, you manually copy an array:

for(int j = 0; j < N; j++)
{
this.tiles[i][j] = tiles[i][j];
}


Which can be replaced with:

System.arraycopy(tiles[i], 0, this.tiles[i], 0, N);


And the entire switch in your priority() method can be replaced by:

manhatDist += posDiff(x, y, (tiles[x][y] == 0 ? 2 : (int) (tiles[x][y] / 3.5)), (tiles[x][y] + 2) % 3);


To test this code, I used:

for(int i = 0; i < 9; i++)
{
System.out.println(i + "\t"  + (i == 0 ? 2 : (int) (i / 3.5)) + "\t" + (i + 2) % 3);
}


Which produces:

0    2    2
1    0    0
2    0    1
3    0    2
4    1    0
5    1    1
6    1    2
7    2    0
8    2    1


Which is what you're already doing manually.

Additionally, your constructor with more parameters exactly duplicates code from the smaller one, so you could replace (your newly changed!):

this.tiles = new int[N][N];
for(int i = 0; i < N; i++)
{
System.arraycopy(tiles[i], 0, this.tiles[i], 0, N);
}


With:

this(new int[N][N]);


So the smaller constructor does that part, then continues with the additional options.

• Great, thanks for the suggestions. I implemented them both and it looks like they are working well. – theSilentOne Dec 16 '12 at 2:39
• Does anyone have a suggestion as to how the neighbors() method could be improved? I was playing with recursive ideas and/or a BFS but couldn't quite put my finger on it as well as I could with this iterative solution. – theSilentOne Dec 16 '12 at 2:40
• My original change to your switch was wrong, I didn't notice the third parameter should change. I have updated my post to include the new code as well as the output. – MrLore Dec 16 '12 at 12:20