Hace poco buscaba algún problema para ponerle a mis alumnos de paradigmas de programación (en programación funcional en LISP) que requiriese del uso de la recursividad, y me acordé del juego Sokoban.
Las reglas son muy simples, pero es verdaderamente adictivo. El juego consiste en colocar una serie de cajas en sus casillas de destino, empujándolas con tu personaje. Sólo podemos empujar una caja poniéndonos detrás de ella, por lo que si una caja queda empotrada en una esquina es imposible moverla.
Se puede jugar en multitud de sitios online, entre otros aquí.
El juego engancha, cuando empiezas no puedes dejar de jugar. El caso es que hace muchos años (allá por el 2001, cuando trabajaba en Newknow) me quedé atrapado en un nivel que no era capaz de solucionar, así que decidí implementar un programa en Java que calculase la solución por mí (no me llevó más de un par de horas, aunque es bastante ineficiente y para profundidades mayores de 50 tarda bastante).
La solución tiene unas 200 líneas, y hace uso intensivo de la recursividad y la técnica backtracking.
He conseguido recuperar aquella clase Java que escribí en su día, el puzle a solucionar está a fuego en el código y es el siguiente, aunque podéis cambiarlo por cualquiera que se os ocurra.
La solución que da es la siguiente (leer de abajo a arriba):
Abajo: [3 , 4]
Abajo: [3 , 3]
Abajo: [3 , 2]
Abajo: [3 , 1]
Derecha: [2 , 1]
Arriba: [2 , 2]
Arriba: [2 , 3]
Arriba: [2 , 4]
Arriba: [2 , 5]
Abajo: [2 , 4]
Abajo: [2 , 3]
Izquierda: [3 , 3]
Arriba: [3 , 4]
Arriba: [3 , 5]
Arriba: [3 , 6]
Derecha: [2 , 6]
Abajo: [2 , 5]
Izquierda: [3 , 5]
Abajo: [3 , 4]
Izquierda: [4 , 4]
Arriba: [4 , 5]
Arriba: [4 , 6]
Derecha: [3 , 6]
Derecha: [2 , 6]
Izquierda: [3 , 6]
Izquierda: [4 , 6]
Abajo: [4 , 5]
Abajo: [4 , 4]
Derecha: [3 , 4]
Abajo: [3 , 3]
Derecha: [2 , 3]
Abajo: [2 , 2]
Derecha: [1 , 2]
Y aquí está el código del buscador de soluciones:
/*
* Cajas.java
*
* Created on 30 de abril de 2001, 13:02
*/
public class Cajas extends Object {
public char[][] lab = {
{'#','#','#','#','#','#'},
{'#','#',' ',' ','#','#'},
{'#',' ','H',' ','#','#'},
{'#','#','H',' ','#','#'},
{'#','#',' ','H',' ','#'},
{'#','o','H',' ',' ','#'},
{'#','o','o','X','o','#'},
{'#','#','#','#','#','#'}};
public int initX = 1;
public int initY = 2;
public static int DIRECTION_UP = 1;
public static int DIRECTION_RIGHT = 2;
public static int DIRECTION_DOWN = 3;
public static int DIRECTION_LEFT = 4;
public int MAX_DEPTH = 100;
public static final char WALL = '#';
public static final char TARGET = 'o';
public static final char FREE = ' ';
public static final char BOXOVERFREE = 'H';
public static final char BOXOVERTARGET = 'X';
public static final char STEPOVERFREE = '.';
public static final char STEPOVERTARGET = ',';
public static void main(String args[]) {
new Cajas().go();
}
/** Creates new Cajas */
public Cajas() {
}
public void go() {
System.out.println("Iniciando ejecución...");
for(int i=1; i<MAX_DEPTH; i++) {
State state = new State(initX, initY, lab);
if(!state.step(1, i)) {
System.out.println("No hay soluciones con " + i + " movimientos");
}
else {
System.out.println("Encontrada solución con " + i + " movimientos");
break;
}
}
}
private class State {
public int x;
public int y;
public char[][] matrix;
public State(int x, int y, char[][] matrix) {
this.x = x;
this.y = y;
this.matrix = matrix;
}
public boolean step(int depth, int maxDepth) {
// print();
try {
// System.in.read();
} catch(Exception e) {
}
if(depth > maxDepth) {
return false;
}
if(isDone()) {
System.out.println("Hecho: [" + x + " , " + y + "]");
return true;
}
State newState = alterState(DIRECTION_UP);
if(newState != null && newState.step(depth+1, maxDepth)) {
System.out.println("Arriba: [" + x + " , " + y + "]");
return true;
}
newState = alterState(DIRECTION_RIGHT);
if(newState != null && newState.step(depth+1, maxDepth)) {
System.out.println("Derecha: [" + x + " , " + y + "]");
return true;
}
newState = alterState(DIRECTION_DOWN);
if(newState != null && newState.step(depth+1, maxDepth)) {
System.out.println("Abajo: [" + x + " , " + y + "]");
return true;
}
newState = alterState(DIRECTION_LEFT);
if(newState != null && newState.step(depth+1, maxDepth)) {
System.out.println("Izquierda: [" + x + " , " + y + "]");
return true;
}
return false;
}
public State alterState(int direction) {
int toGoX=0,nextToGoX=0,toGoY=0,nextToGoY=0;
if(direction == DIRECTION_UP) {
toGoX = x;
nextToGoX = x;
toGoY = y-1;
nextToGoY = y-2;
}
else if(direction == DIRECTION_RIGHT) {
toGoX = x+1;
nextToGoX = x+2;
toGoY = y;
nextToGoY = y;
}
else if(direction == DIRECTION_DOWN) {
toGoX = x;
nextToGoX = x;
toGoY = y+1;
nextToGoY = y+2;
}
else if(direction == DIRECTION_LEFT) {
toGoX = x-1;
nextToGoX = x-2;
toGoY = y;
nextToGoY = y;
}
State newState = null;
char mToGo = matrix[toGoY][toGoX];
// Moverse a sitio libre
if(mToGo == FREE || mToGo == TARGET) {
newState = getCopy();
if(newState.matrix[y][x] == FREE)
newState.matrix[y][x] = STEPOVERFREE;
else if(newState.matrix[y][x] == TARGET)
newState.matrix[y][x] = STEPOVERTARGET;
newState.x = toGoX;
newState.y = toGoY;
return newState;
}
if( nextToGoY < 0 || nextToGoY >= matrix.length
|| nextToGoX < 0 || nextToGoX >= matrix[0].length)
return null;
char mNextToGo = matrix[nextToGoY][nextToGoX];
// Empujar caja que estaba sobre blanco, sobre blanco
if(mToGo == BOXOVERFREE && (mNextToGo == FREE || mNextToGo == STEPOVERFREE)) {
newState = getCopyClearStepped();
newState.x = toGoX;
newState.y = toGoY;
newState.matrix[toGoY][toGoX] = FREE;
newState.matrix[nextToGoY][nextToGoX] = BOXOVERFREE;
}
// Empujar caja que estaba sobre blanco, sobre objetivo
else if(mToGo == BOXOVERFREE && (mNextToGo == TARGET || mNextToGo == STEPOVERTARGET)) {
newState = getCopyClearStepped();
newState.x = toGoX;
newState.y = toGoY;
newState.matrix[toGoY][toGoX] = FREE;
newState.matrix[nextToGoY][nextToGoX] = BOXOVERTARGET;
}
// Empujar caja que estaba sobre objetivo, sobre blanco
else if(mToGo == BOXOVERTARGET && (mNextToGo == FREE || mNextToGo == STEPOVERFREE)) {
newState = getCopyClearStepped();
newState.x = toGoX;
newState.y = toGoY;
newState.matrix[toGoY][toGoX] = TARGET;
newState.matrix[nextToGoY][nextToGoX] = BOXOVERFREE;
}
// Empujar caja que estaba sobre objetivo, sobre objetivo
else if(mToGo == BOXOVERTARGET && (mNextToGo == TARGET || mNextToGo == STEPOVERTARGET)) {
newState = getCopyClearStepped();
newState.x = toGoX;
newState.y = toGoY;
newState.matrix[toGoY][toGoX] = TARGET;
newState.matrix[nextToGoY][nextToGoX] = BOXOVERTARGET;
}
return newState;
}
public State getCopy() {
int height = matrix.length;
int width = matrix[0].length;
char[][] newMatrix = new char[height][];
for(int i = 0; i < height; i++) {
newMatrix[i] = new char[width];
for(int j = 0; j < width; j++)
newMatrix[i][j] = matrix[i][j];
}
return new State(x,y,newMatrix);
}
public State getCopyClearStepped() {
int height = matrix.length;
int width = matrix[0].length;
char[][] newMatrix = new char[height][];
for(int i = 0; i < height; i++) {
newMatrix[i] = new char[width];
for(int j = 0; j < width; j++) {
char c = matrix[i][j];
if (c == STEPOVERFREE)
newMatrix[i][j] = FREE;
else if (c == STEPOVERTARGET)
newMatrix[i][j] = TARGET;
else
newMatrix[i][j] = c;
}
}
return new State(x,y,newMatrix);
}
public boolean isDone() {
int height = matrix.length;
int width = matrix[0].length;
for(int i = 0; i < height; i++)
for(int j = 0; j < width; j++)
if(matrix[i][j] == BOXOVERFREE)
return false;
return true;
}
public void print() {
int height = matrix.length;
int width = matrix[0].length;
for(int i = 0; i < height; i++) {
for(int j = 0; j < width; j++) {
if(i == y && j == x)
System.out.print("$");
else
System.out.print(matrix[i][j]);
}
System.out.println("");
}
}
}
}
Entradas
No hay comentarios:
Publicar un comentario