I am trying to make a breadth-first search to solve a square-shifting puzzle (the one where you move squares into an empty space until it's solved). My breadth-first algorithm uses a queue. Unfortunately, it only seems to be working for the UP and DOWN cases, and not the LEFT or RIGHT cases:
if (up)
{
int[][] current = copy(v.state);
current[x][y] = current[x - 1][y];
current[x - 1][y] = 0;
State w = new State(current);
w.distance = v.distance + 1;
w.path = v;
System.out.println(q.insert(w));
}
if (down)
{
int[][] current = copy(v.state);
current[x][y] = current[x + 1][y];
current[x + 1][y] = 0;
State w = new State(current);
w.distance = v.distance + 1;
w.path = v;
System.out.println(q.insert(w));
}
if (left)
{
int[][] current = copy(v.state);
current[x][y] = current[x][y - 1];
current[x][y - 1] = 0;
State w = new State(current);
w.distance = v.distance + 1;
w.path = v;
System.out.println(q.insert(w));
}
if (right)
{
int[][] current = copy(v.state);
current[x][y] = current[x][y + 1];
current[x][y + 1] = 0;
State w = new State(current);
w.distance = v.distance + 1;
w.path = v;
System.out.println(q.insert(w));
}
I think it's a problem with my queue, the implementation of which is below. Is there something wrong with my queue, or is it another problem? Does the Java API have a queue class I could use?
public class ArrayQueue {
State[] items;
int maxSize;
int front;
int rear;
int numItems;
public ArrayQueue(int max)
{
items = new State[max];
maxSize = max;
front = 0;
rear = -1;
numItems = 0;
}
public boolean insert(State item)
{
if (isFull()) return false;
rear = (rear + 1) % items.length;
items[rear] = item;
return true;
}
public State remove()
{
if (isEmpty()) return null;
State removed = items[front];
front = (front + 1) % items.length;
return removed;
}
public boolean isFull()
{
if ((front + 1) % maxSize == rear)
return true;
else
return false;
}
public boolean isEmpty()
{
if ((rear + 1) % maxSize == front)
return true;
else
return false;
}
}
Here is the copy method:
public static int[][] copy(int[][] input) //This method is necessary because we are trying to clone a multi-dimensional array.
{ //Just using clone() will copy the outer arrays but they will be arrays of references to the original inner arrays.
int[][] output = new int[input.length][];
for (int i = 0; i < input.length; i++)
output[i] = input[i].clone();
return output;
}
The JDK provides a Queue
interface and a number of implementations, which can be found in the "All Known Implementing Classes" section of the Queue
documentation.
For your purposes, a LinkedList
should probably be good enough.