Resolviendo el 8 puzzle

En esta práctica vamos a implementar un programa en Prolog para resolver el 8-puzzle usando tres algoritmos de planificación basados en búsqueda "ciega" o "no informada" (esto es, exploración de todas las posibilidades sin uso de información heurística).

El 8-puzzle es un problema muy sencillo en el que tenemos un tablero de 3 x 3 posiciones con 8 pequeñas fichas cuadradas numeradas del 1 al 8 además de una posición hueca. En cada transición, se puede mover hacia el hueco una cualquiera de las fichas adyacentes. El problema consiste en alcanzar una configuración final predeterminada, a partir de una configuración inicial "desordenada". Por ejemplo, podríamos tener la situación de esta figura:


En el estado inicial, los posibles movimientos son tres: mover la ficha 8 a la derecha, la 2 hacia abajo o la 6 hacia la izquierda. Por simplicidad, representaremos más bien el movimiento del hueco (en direcciones cardinales n, s, w, e), de modo que las acciones posibles en este estado inicial serían w (mover el hueco al oeste, intercambiando con el 8), n (mover el hueco al norte, intercambiando con el 2) o e (mover el hueco al este, intercambiando con el 6). Se desea obtener la secuencia de movimientos que nos permita llegar al estado final de la figura derecha, que supondremos que siempre es ese mismo estado meta predertimado. Para el estado inicial del ejemplo, se puede comprobar que un plan válido sería la secuencia de movimientos [w,n,n,e,s,e,s] (de hecho, ese es el plan más corto para llegar a la meta).

Programando el planificador en Prolog

Para representar un estado del puzle, usaremos una lista de 9 números, de modo que el 0 represente la posición del hueco. Por ejemplo, el estado inicial de arriba correspondería a la lista [4,1,3,7,2,5,8,0,6]. Igualmente, el estado meta será siempre la lista [1,2,3,4,5,6,7,8,0].

El predicado principal que debemos implementar será plan(Modo,S0,Plan) donde: Modo es un dato de entrada fijando el tipo de algoritmo que vamos a usar (podrá ser iter, anchura, profund), S0 es una lista de entrada conteniendo el estado inicial, y Plan es una lista de acciones conteniendo el plan final obtenido. Ese predicado hará llamadas a otros, dependiendo el tipo de algoritmo a programar.

Otro predicado esencial del que haremos uso es expandir(S0, Accion, S1) que nos debe devolver, para cualquier estado S0, todas las combinaciones de Accion válida y estado siguiente S1 al que nos lleva esa acción. Como ejemplo de funcionamiento, tendríamos:

?- expandir([4,1,3,7,2,5,8,0,6],A,S).
A = n,
S = [4, 1, 3, 7, 0, 5, 8, 2, 6] ;
A = e,
S = [4, 1, 3, 7, 2, 5, 8, 6, 0] ;
A = w,
S = [4, 1, 3, 7, 2, 5, 0, 8, 6] ;
false.

Para hacer pruebas, usaremos estos 3 posibles estados iniciales:

initial1([1,2,3,7,4,6,5,0,8]).
initial2([4,1,3,7,2,5,0,8,6]).
initial3([1,6,2,3,0,8,4,7,5]).

Algoritmos de anchura y de profundidad

Para los algoritmos anchura y profund usaremos un mismo predicado llamado buscar que tiene el siguiente aspecto buscar(Modo,Nodos,Vistados,Plan) cuyos argumentos son:

• Modo = será anchura o profund
• Nodos = es una lista de elementos de la forma "nodo(P,S)" donde P es el plan parcial obtenido hasta el momento, y S es un estado dado. Esta lista contiene los estados que todavía se van a explorar. Inicialmente, la lista tendrá el aspecto [nodo([],S0)] de modo que S0 es el estado inicial y el plan parcial por ahora es vacío.
• Visitados  = es una lista con todos los estados que hemos expandido hasta el momento. Inicialmente será vacía [].
• Plan = es el plan final, con la solución del problema

El modo de operar del predicado buscar es el siguiente:

• Tomamos el primer nodo n(P,S) de Nodos. Si el estado S es el meta, podemos parar y devolvemos el plan P
• Si el estado S no es el meta, pero ya existe en la lista de Visitados, entonces lo ignoramos y pasamos a contemplar el siguiente nodo en Nodos
• Si S no es meta ni ha sido visitado, entonces recopilamos en una lista de Expandidos todos los nodos que se pueden expandir a partir de S. Para ello, podemos usar
  
  findall(nodo([M | P],S1),expandir(S,M,S1),Expandidos)
  
  Si tenemos el algoritmo de profund, la lista de Expandidos se añadirá a la cabeza de la de Nodos, mientras que si tenemos el de anchura, los expandidos se añaden al final de los Nodos. Continuamos la búsqueda anotando el estado S como visitado y llamando de nuevo a buscar.
  

Algoritmo de profundización iterativa

El tercer algoritmo iter implementará la búsqueda por profundización iterativa. La idea es usar un algoritmo de backtracking con un límite de profundidad. Programaremos el predicado busca_limite(N,Max,S0,Plan0,Plan) que realizará una búsqueda por backtracking hasta un límite Max. El argumento N es la profundidad actual (comenzaremos en 0), mientras que S0 es el estado inicial. La lista Plan0 lleva el plan obtenido hasta ahora (de forma acumulada) y comienza siendo []. Por último, Plan devuelve el plan final obtenido. La idea es que, si N>Max, la búsqueda se detiene obligatoriamente.

Una vez que busca_limite esté funcionando, la búsqueda iter realizará llamadas sucesivas a busca_limite comenzando con Max=0 e incrementando el valor de Max de uno en uno hasta que aparezca algún plan.

Entrega y evaluación