Entradas etiquetadas con programación

Kaeru Jump, del japonés kaeru (蛙, rana), es un pequeño juego en flash de inteligencia (o también de probar, probar y probar). El objetivo del juego es que la rana protagonista llegue a cada una de las piedras del escenario. A cada salto, la piedra anterior se hunde en el agua. Los saltos son sólo en ángulos rectos y no se puede saltar hacia atrás.

El reto son diez niveles generados aleatoriamente, a cada cual más difícil. Os reto a ver cuánto tiempo tardáis en acabarlos todos, sin hacer trampas claro.

Solución

Si no consiguieseis acabar todos los niveles, no os desesperéis ni lancéis el teclado por la ventana. Existe un método para resolver este tipo de problemas. En programación se le llama backtracking. Aunque por el nombre parezca algo guapo, no es más que ir probando combinaciones hasta encontrar las que resuelvan el problema (en nuestro caso paramos al encontrar la primera que lo resuelva). Son muchas combinaciones, pero mientras las haga el ordenador a nosotros nos da igual, ¿no?

Para hacerlo funcionar, sólo tenéis que decir la posición inicial, la dirección a la que mira la rana y marcar los checkbox del mapa del nivel, si está marcado es que en el mapa hay una piedra en esa posición. ¡Si leéis desde el lector RSS es probable que no veáis nada!

El código

Os pongo la función para calcular la solución en javascript. Se puede comprimir más el código, pero así se entiende mejor. Para llamarla, necesitáis la fila y la columna inicial([cci lang="js"]f[/cci] y [cci lang="js"]c[/cci]), una matriz de booleanos para el [cci lang="js"]tablero[/cci] donde un [cci lang="js"]true[/cci] indica que hay una piedra en esa posición, un [cci lang="js"]Array[/cci] vacío para guardar el [cci lang="js"]camino[/cci] en la recursividad y un [cci lang="js"]string[/cci] [cci lang="js"]direccion[/cci] para la dirección inicial, que puede ser "arriba", "derecha", "abajo" o "izquierda". El resultado es un [cci lang="js"]Array[/cci] con dos posiciones: la primera indica si hay solución y la segunda indica el camino.

[cc lang = "javascript"] function resolver(f, c, tablero, restantes, camino, direccion) { if(restantes == 1) return new Array(true, camino); var resuelto = false; // Miro todas las direcciones desde la posición actual // Arriba if(direccion != "abajo") { var hay = false; for(fila = f - 1; !hay && fila >= 0; --fila) { if(tablero[fila][c]) { hay = true; tablero[f][c] = false; --restantes; camino.push("Arriba"); resultado = resolver(fila, c, tablero, restantes, camino, "arriba"); if(resultado[0]) return new Array(true, camino); else { ++restantes; tablero[f][c] = true; camino.pop(); } } } } // Derecha if(direccion != "izquierda") { var hay = false; for(columna= c + 1; !hay && columna < columnas; ++columna) { if(tablero[f][columna]) { hay = true; tablero[f][c] = false; --restantes; camino.push("Derecha"); resultado = resolver(f, columna, tablero, restantes, camino, "derecha"); if(resultado[0]) return new Array(true, camino); else { ++restantes; tablero[f][c] = true; camino.pop(); } } } } // Abajo if(direccion != "arriba") { var hay = false;; for(fila = f + 1; !hay && fila < filas; ++fila) { if(tablero[fila][c]) { hay = true; tablero[f][c] = false; --restantes; camino.push("Abajo"); resultado = resolver(fila, c, tablero, restantes, camino, "abajo"); if(resultado[0]) return new Array(true, camino); else { ++restantes; tablero[f][c] = true; camino.pop(); } } } } // Izquierda if(direccion != "derecha") { var hay = false;; for(columna= c - 1; !hay && columna >= 0; --columna) { if(tablero[f][columna]) { hay = true; tablero[f][c] = false; --restantes; camino.push("Izquierda"); resultado = resolver(f, columna, tablero, restantes, camino, "izquierda"); if(resultado[0]) return new Array(true, camino); else { ++restantes; tablero[f][c] = true; camino.pop(); } } } } return new Array(false); } [/cc]