Ayuda con Java

Buenas, nesecito ayuda con la creacion de una aplicacion que me ayude a resolver un juego parecido al de Eight puzzle o fifteen puzzle, lo unico diferente es que son ochos fichas movibles y una estatica, que es la del centro, en la cual no pude haber ningun numero, pero la ficha que esta arriba de esta, si puede intercambiarse con la que esta abajo, oseas ayuda a intercambiar, pero de la derecha a la izquierda o viceversa no se puede. Y hay un espacio en blanco sin numero que puede moverse

La solucion es:

1 0 7
2 -1 6
3 4 5

Llevo algo de codigo, necesito hacerlo con recursividad:
public class Solucionador {


// Matriz del estado meta
private static int[] ESTADO_META = {1,0,7,2-1,6,3,4,5};

// Matriz de adyacencia que indica si una celda vacia se pueden intercambiar con otras.
private static final int[][] RELACIONES = {{0,1,0,1,0,0,0,0,0},
{1,0,1,0,0,0,0,1,0},
{0,1,0,0,0,1,0,0,0},
{1,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,1},
{0,0,0,1,0,0,0,1,0},
{0,1,0,0,0,0,1,0,1},
{0,0,0,0,0,1,0,1,0}};

// Tamano de la matriz cuadrada
private static final int TAMANO = 3;

// Vector que contiene las 9 celdas del celdas. La celda 4 es el puente.
private int[] celdas;

private int celdaVacia;

public static void main(String[] args) {
int[] valores = {2,1,7,0,-1,6,3,4,5};
Solucionador s = new Solucionador(valores);
s.solucionar();
System.out.println(s);
}

public Solucionador(int[] valores) {
celdas = new int[TAMANO * TAMANO];
if (valores.length == 9) {
for (int c = 0; c < valores.length; ++c) {
if (valores[c] == 0) {
celdaVacia = c;
}
celdas[c] = valores[c];
}
}
else {
System.err.println("Debe tener 8 valores!");
}
}

private void cambiar(int c1, int c2) {
if (celdaValida(c1) && celdaValida(c2)) {
int temp = celdas[c1];
celdas[c1] = celdas[c2];
celdas[c2] = temp;
}
}

private boolean celdaValida(int celda) {
return celda >= 0 && celda < celdas.length;
}

public boolean solucionar() {
return solucionar(celdaVacia, celdaVacia, 0);
}

private boolean solucionar(int celdaVacia, int celdaVaciaAnterior, int celdaCandidato) {
boolean exito = solucionado();
if (!exito) {
if (celdaValida(celdaCandidato)) {
if (RELACIONES[celdaVacia][celdaCandidato] == 1 && celdaVaciaAnterior != celdaCandidato) {
cambiar(celdaVacia, celdaCandidato);
mostrar();
exito = solucionar(celdaCandidato, celdaVacia, 0);
if (!exito) {
cambiar(celdaVacia, celdaCandidato);
System.out.println("Bactracking...");
mostrar();
exito = solucionar(celdaVacia, celdaVaciaAnterior, celdaCandidato + 1);
}
}
else {
exito = solucionar(celdaVacia, celdaVaciaAnterior, celdaCandidato + 1);
}
}
}
return exito;
}


private void mostrar() {
System.out.println("\033[2H \033[J");
System.out.println(this);
try {
Thread.sleep(2000);
} catch ( Exception e ) {};
}

private boolean solucionado() {
boolean iguales = true;
for (int i = 0; iguales && i < ESTADO_META.length; ++i) {
iguales = ESTADO_META == celdas;
}
return iguales;
}

public String toString() {
String celdas = "";
for (int c = 0; c < this.celdas.length; ++c) {
celdas += String.format(" %2s",this.celdas[c]);
if ((c + 1) % TAMANO == 0) {
celdas += "\n";
}
}
return celdas;
}

}


Al final debe encontrar la solucion gracias al BackTracking o MarchaAtras...