Solución problema 8 puzzle mediante búsqueda de anchura y búsqueda de profundidad en java

Introducción

El 8 puzzle es un juego en la que se dispone de una caja que contiene 8 fichas puestas en disposición aleatoria en una matriz de 3x3, donde cada una de estas contiene un número de la siguiente lista {1,2,3,4,5,6,7,8}. Con la descripción inicial nos podemos dar cuenta de que el tablero de 3x3 contiene solamente 8 fichas y un espacio vacío. 

La finalidad del juego es lograr que las fichas se encuentren en una disposición ordenada ascendentemente. Ej:

123

456

78X    <--- donde X es la ficha vacía 

Parte I - Representación de problemas en el espacio de estados.

Sobre los estados

Un espacio de estados es el conjunto total de estados posibles que un problema tiene.
Un estado representa un conjunto de propiedades que existen en un problema y que son únicos en cantidad/valor para todo el espacio de estados.

El espacio de estados para este problema se encuentra representado por el conjunto de todas las posibles ubicaciones de cada una de las fichas. A continuación se pretende graficar esto mediante una simple comparación de 2 estados distintos de 8 puzzle.

Caso1:        Caso2:

1 2 3            1  2  3

4 5 6            4  5  6

7 8 X            7 X  8

Caso1 es un estado distinto de Caso2 porque se ha movido 8 hacia la derecha y se ha dejado el espacio vacÌo en el espacio de al medio para la tercera fila.

Cada estado del problema es representado en un nodo de la estructura de datos.

Sobre las operaciones

Cada problema que es representado con estados (para ser utilizado con un algoritmo inteligente) debe poseer un método de transición entre un estado y otro. Estos métodos de transición son llamados operaciones.

Para nuestro problema se han definido 4 tipos de operaciones. Las cuales son las de movimiento de una ficha hacia arriba, abajo, izquierda y derecha; donde la ficha que se mueve a una cierta posición intercambia de lugar con la ficha que se encontraba anteriormente en dicho lugar. Nuestras operaciones tienen sólo 1 restricción, la cual no permite que la ficha siendo movida pueda salir del tablero.

Debido a que la existencia de 1 ficha en cierta posición impide a cualquier otra ocupar esa misma posición para ese mismo estado, se dice que estos son eventos excluyentes. Por lo tanto, el espacio de estados para este problema es de 9!/2 (181.440 posibles estados!!), ya que contamos el espacio en blanco cómo una ficha dentro del tablero ya que ocupa un espacio e impide a las otras de ocuparlo para ese mismo estado. Además de lo anterior, hay que considerar que 9! contempla que todas las fichas pueden estar al menos una vez en cierta posición sin repetirse ninguna para ese mismo estado, y que según sea el estado inicial, hay ocasiones en que no es posible llegar a una solución. Debido a lo anterior, se dice que los posibles estados son de 9!/2. 

Cada operación realizada en la resolución del problema es representada como un arco que une al estado previo m·s el resultante (una vez realizada la operación sobre el previo).

En nuestro caso hemos representado el espacio vacío como un 0 y es este el que movemos a lo largo del tablero, ya que simplifica la cantidad de operaciones para la resolución del problema

Parte II - Implementación de los Algoritmos de búsqueda en el espacio de estados.

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

class Node{
public Node(int[][] state){
this.state = state;
this.children = new ArrayList<Node>();
}
//get and set for state and children

public int[][] getState(){
return state;
}

public void setState(int[][] state){
this.state = state;
}

public void prependChild(Node node){
this.children.add(0, node);
}

public void appendChild(Node node){
this.children.add(node);
}

public ArrayList<Node> getChildren(){
return this.children;
}

public void setChildren(ArrayList<Node> children){
this.children = children;
}

public String to_string(){
String result = "";
for(int[] y : state){
for(int x : y){
result += x + " ";
}
result += "\n";
}
return result;
}

private int[][] state;
private ArrayList<Node> children;

}
class Solver{
public Solver(int[][] init_state, int[][] goal_state){
in = new Scanner(System.in);
Node a = new Node(init_state);
this.root = a;
this.goal_state = goal_state;
this.open_list = new ArrayList<Node>();
this.closed_list = new ArrayList<Node>();
this.states_nuevos = 0;
}

/*


BREADTH START


*/

public void solve_breadth(){
int total =0;
boolean done = false;
Node node;
this.root.setChildren(new ArrayList<Node>());
this.open_list = new ArrayList<Node>();
this.closed_list = new ArrayList<Node>();
this.open_list.add(this.root);

while(!this.open_list.isEmpty() && !done){
node = this.open_list.remove(0);
System.out.println("TOTAL DE:"+states_nuevos + " STATES NUEVOS" );
states_nuevos=0;
System.out.println("======================================");
System.out.println("USING:\n" + node.to_string());
System.out.println("======================================");

this.closed_list.add(node);
//we need to see if node is inside closed list to ignore it
if (Arrays.deepEquals( node.getState(), this.goal_state) ){
done = true;
}
else{
expand_node_breadth(node);
}
total++;
System.out.println(total);

}
System.out.println("Total moves: " + total);
}

public void expand_node_breadth(Node node){
int[] empty_index = new int[2];
ArrayList<Node> node_children = new ArrayList<Node>();
Node child;

int[][] state = node.getState();

for(int empty_row=0; empty_row < state.length; empty_row++){
for(int empty_column=0;empty_column < state[empty_row].length; empty_column++){
if(state[empty_row][empty_column] == 0){
empty_index[0] = empty_row;
empty_index[1] = empty_column;
}
}
}
int row = empty_index[0];
int column = empty_index[1];
//System.out.println("x is " +empty_index[1] +"\ny is " + empty_index[0]);
int actual_up_value, actual_down_value, actual_left_value, actual_right_value;

if(row!=0){
child = new Node(clone_state(state));
actual_up_value = child.getState()[row-1][column];
child.getState()[row][column] = actual_up_value;
child.getState()[row-1][column] = 0;
node_children.add(child);
}

if(row!=2){
child = new Node(clone_state(state));
actual_down_value = child.getState()[row+1][column];
child.getState()[row][column] = actual_down_value;
child.getState()[row+1][column] = 0;
node_children.add(child);
}

if(column!=0){
child = new Node(clone_state(state));
actual_left_value = child.getState()[row][column-1];
child.getState()[row][column] = actual_left_value;
child.getState()[row][column-1] = 0;
node_children.add(child);
}

if(column!=2){
child = new Node(clone_state(state));
actual_right_value = child.getState()[row][column+1];
child.getState()[row][column] = actual_right_value;
child.getState()[row][column+1] = 0;
node_children.add(child);
}

ArrayList<Node> printable_children = new ArrayList<Node>();
//#node_children has each node expansion of the node parameter
//#node_children has priorities. The first element has lower priority than the last one
for (Node achild : node_children){
if(!closed_has_child(achild)){
this.open_list.add(achild);
this.states_nuevos++;
printable_children.add(achild);
}
}
int printable_children_size = printable_children.size();
int contador_lineas=0;
String[] lineas = {"","",""};
for (Node achild : printable_children){
lineas[0] += " " + Arrays.toString(achild.getState()[0]);
lineas[1] += " " + Arrays.toString(achild.getState()[1]);
lineas[2] += " " + Arrays.toString(achild.getState()[2]);
contador_lineas++;
}

System.out.println("STATES NUEVOS");
for (String linea : lineas){
System.out.println(linea);
}

}

/*


BREADTH END


*/





/*


DEPTH START



*/

public void solve_depth(){
int total =0;
boolean done = false;
Node node;
this.root.setChildren(new ArrayList<Node>());
this.open_list = new ArrayList<Node>();
this.closed_list = new ArrayList<Node>();
this.open_list.add(this.root);

while(!this.open_list.isEmpty() && !done){
node = this.open_list.remove(0);
System.out.println("TOTAL DE:"+states_nuevos + " STATES NUEVOS" );
states_nuevos=0;
System.out.println("======================================");
System.out.println("USING:\n" + node.to_string());
System.out.println("======================================");

this.closed_list.add(node);
//we need to see if node is inside closed list to ignore it
if (Arrays.deepEquals( node.getState(), this.goal_state) ){
done = true;
}
else{
expand_node_depth(node);
}
total++;
System.out.println(total);

}
System.out.println("Total moves: " + total);

}

public void expand_node_depth(Node node){
int[] empty_index = new int[2];
ArrayList<Node> node_children = new ArrayList<Node>();
Node child;

int[][] state = node.getState();

for(int empty_row=0; empty_row < state.length; empty_row++){
for(int empty_column=0;empty_column < state[empty_row].length; empty_column++){
if(state[empty_row][empty_column] == 0){
empty_index[0] = empty_row;
empty_index[1] = empty_column;
}
}
}
int row = empty_index[0];
int column = empty_index[1];
//System.out.println("x is " +empty_index[1] +"\ny is " + empty_index[0]);
int actual_up_value, actual_down_value, actual_left_value, actual_right_value;

if(row!=0){
child = new Node(clone_state(state));
actual_up_value = child.getState()[row-1][column];
child.getState()[row][column] = actual_up_value;
child.getState()[row-1][column] = 0;
node_children.add(0,child);
}

if(row!=2){
child = new Node(clone_state(state));
actual_down_value = child.getState()[row+1][column];
child.getState()[row][column] = actual_down_value;
child.getState()[row+1][column] = 0;
node_children.add(0,child);
}

if(column!=0){
child = new Node(clone_state(state));
actual_left_value = child.getState()[row][column-1];
child.getState()[row][column] = actual_left_value;
child.getState()[row][column-1] = 0;
node_children.add(0,child);
}

if(column!=2){
child = new Node(clone_state(state));
actual_right_value = child.getState()[row][column+1];
child.getState()[row][column] = actual_right_value;
child.getState()[row][column+1] = 0;
node_children.add(0,child);
}

ArrayList<Node> printable_children = new ArrayList<Node>();
//#node_children has each node expansion of the node parameter
//#node_children has priorities. The first element has lower priority than the last one
for (Node achild : node_children){
if(!closed_has_child(achild)){
this.open_list.add(0, achild);
this.states_nuevos++;
printable_children.add(0,achild);
}
}
int printable_children_size = printable_children.size();
int contador_lineas=0;
String[] lineas = {"","",""};
for (Node achild : printable_children){
lineas[0] += " " + Arrays.toString(achild.getState()[0]);
lineas[1] += " " + Arrays.toString(achild.getState()[1]);
lineas[2] += " " + Arrays.toString(achild.getState()[2]);
contador_lineas++;
}

System.out.println("STATES NUEVOS");
for (String linea : lineas){
System.out.println(linea);
}

}

/*



DEPTH END


*/

public boolean closed_has_child(Node child){
for(Node closed : this.closed_list){
if(Arrays.deepEquals(closed.getState(), child.getState()) ){
return true;
}
}

return false;
}

public int[][] clone_state(int[][] state){
int [][] clone = new int[state.length][];
for(int i = 0; i < state.length; i++)
{clone[i] = state[i].clone();}

return clone;
}

private Node root;
private int[][] goal_state;
private ArrayList<Node> open_list;
private ArrayList<Node> closed_list;
private Scanner in;
private int states_nuevos;

}

public class SolverStarter{
public static void main(String args[]){
Scanner in = new Scanner(System.in);
int[][] initstate = {{2,8,3},{1,6,4},{7,0,5}};
int[][] goal = {{1,2,3},{4,5,6},{7,8,0}}; //never change
Solver solver = new Solver(initstate, goal);
System.out.print("Do you want to use depth first search or breadth first search?[depth/breadth]: ");
String response = in.nextLine();
if (response.equals("depth")){
System.out.println("\n === Starting depth first search === \n");
solver.solve_depth();
}
else if (response.equals("breadth")){
System.out.println("\n === Starting breadth first search === \n");
solver.solve_breadth();
}else{
System.out.println("Response not valid, exiting now");
}
}

}

Parte III - Experimentación con los algoritmos implementados.

No se pudo completar la ejecución de los ejemplos dados y no se pudo determinar un costo de ejecución, ya que cada movimiento tiene un costo de 1 en base a nuestra solución sin heurística.

Integrantes:
Jose Saez
Rodrigo Lagos
Cesar Adriazola
Ivan Barrera

Link al tema del grupo:
(Proyecto) Trabajo Pr·ctico de B˙squeda en el espacio de estados .