HSE-96: practica-03.txt
 Búsqueda con heurística.
===============================================================================

*******************************************************************************
* ENUNCIADO:
*******************************************************************************

 Para el 8-puzzle se usa un cajón cuadrado en el que hay situados 8 bloques
   cuadrados.  El cuadrado restante está sin rellenar. Cada bloque tiene un
   número. Un bloque adyacente al hueco puede deslizarse hacia él. El 
   juego consiste en transformar la posición inicial en la posición final
   mediante el deslizamiento de los bloques.

 Se usarán los ficheros 8-puzzle.lsp y busqueda-heuristica.lsp.

*******************************************************************************
* APARTADOS:
*******************************************************************************

 (1) En el fichero 8-puzzle.lsp se encuentra definida la función 8-PUZZLE de
     forma que
	   (8-PUZZLE :ESTADO-INICIAL '<INICIAL>
		     :ESTADO-FINAL '<FINAL>
		     :POR '<METODO>
		     :HEURISTICA '<FUNCION>)
     resuelve el problema del 8-puzzle, con estado inicial <INICIAL>, estado
     final <FINAL>, utilizando el procedimiento de búsqueda heurística 
     <METODO> con función de heurística <FUNCION>. En esta función, los
     estados inicial y final se proporcionan como listas. 
     Resolver el problema del 8-puzzle utilizando dicha función con 
       * Estado inicial:
	   ((4 8 1) (3 H 2) (7 6 5)) 
       * Estado final:
           ((1 2 3) (8 H 4) (7 6 5))
       * Métodos:
	   escalada y primero-el-mejor
       * Heurística:
	   heuristica-2

 (2) Resolver el problema del 8-puzzle utilizando la función descrita en el
     apartado anterior con
       * Estado inicial:
	   ((1 2 3) (4 H 5) (8 7 6)) 
       * Estado final:
           ((1 2 3) (8 H 4) (7 6 5))
       * Métodos:
	   escalada, primero-el-mejor y busqueda-optimal
       * Heurística:
	   heuristica-1 y heuristica-2
     y rellenar las siguientes tablas:
	 
         +---------------------------------------------+
         |               heuristica-1                  |
         +----------+----------+------------+----------+
         |          | escalada | primero el | busqueda |
         |          |          |   mejor    | optimal  |
         +----------+----------+------------+----------+
         | Solucion |          |            |          |
         | Tiempo   |          |            |          |
         | Espacio  |          |            |          |
         +----------+----------+------------+----------+

         +---------------------------------------------+
         |               heuristica-2                  |
         +----------+----------+------------+----------+
         |          | escalada | primero el | busqueda |
         |          |          |   mejor    | optimal  |
         +----------+----------+------------+----------+
         | Solucion |          |            |          |
         | Tiempo   |          |            |          |
         | Espacio  |          |            |          |
         +----------+----------+------------+----------+

     donde en el apartado "Solucion" hay que indicar si se encuentra la
     solución o no.

 (3) Implementar la función SUCESORA-EN-SECUENCIA que calcule el sucesor de
     una casilla del 8-puzzle según se indica a continuación:
         >(SUCESORA-EN-SECUENCIA '(0 0))
	 (0 1)
         >(SUCESORA-EN-SECUENCIA '(0 1))
	 (0 2)
         >(SUCESORA-EN-SECUENCIA '(0 2))
	 (1 2)
         >(SUCESORA-EN-SECUENCIA '(1 2))
	 (2 2)
         >(SUCESORA-EN-SECUENCIA '(2 2))
	 (2 1)
         >(SUCESORA-EN-SECUENCIA '(2 1))
	 (2 0)
         >(SUCESORA-EN-SECUENCIA '(2 0))
	 (1 0)
         >(SUCESORA-EN-SECUENCIA '(1 0))
	 (0 0)
     Para el resto de las casillas del 8-puzzle (en este caso únicamente la
     casilla (1 1)) y para cualquier otra entrada, el resultado ha de ser igual
     a la entrada.

 (4) Implementar la función VALOR-EN-SECUENCIA tal que a partir de un estado
     del 8-puzzle y una posición en dicha matriz devuelva:
      * 0 si en la posición indicada está el hueco.
      * 1 si la posición indicada es la central ['(1 1)] y hay alguna pieza
        en dicha posición (distinta del hueco).
      * 2 si la posición indicada no es la central y la pieza que ocupa la
        posición SUCESORA-EN-SECUENCIA de la posición dada no es la
        sucesora inmediata de la pieza que ocupa la posición dada.
      * 0 en cualquier otro caso.
     Nota: Se considera que las piezas están ordenadas de manera creciente
     del 1 al 8 y que la inmediata sucesora del 8 es el 1.
     Ejemplos:

      +------------+------------+--------------+--------------+-----------+
      |            |            |              |  ficha en    |           |
      |            |  ficha en  | sucesora-en- | sucesora-en- | valor-en- |
      | posición | posición |  secuencia   |  secuencia   | secuencia |
      +------------+------------+--------------+--------------+-----------+
      |   (i j)    |     'h     |              |              |     0     |
      +------------+------------+--------------+--------------+-----------+
      |   (1 1)    |  no es 'h  |              |              |     1     |
      +------------+------------+--------------+--------------+-----------+
      |   (0 2)    |     1      |    (1 2)     |      2       |     0     | 
      +------------+------------+--------------+--------------+-----------+
      |   (0 2)    |     1      |    (1 2)     |      3       |     2     | 
      +------------+------------+--------------+--------------+-----------+
      |   (2 1)    |     8      |    (2 0)     |      1       |     0     | 
      +------------+------------+--------------+--------------+-----------+
      |   (2 1)    |     8      |    (2 0)     |      5       |     2     | 
      +------------+------------+--------------+--------------+-----------+
      |   (2 1)    |     8      |    (2 0)     |      'h      |     0     | 
      +------------+------------+--------------+--------------+-----------+

 (5) Implementar la función CUENTA-DE-SECUENCIA que a todo ESTADO del
     8-puzzle le asocie la suma del VALOR-EN-SECUENCIA de todas las casillas de
     dicho ESTADO.

 (6) Implementar la función HEURISTICA-3 tal que:
       (HEURISTICA-3 ESTADO) = (HEURISTICA-2 ESTADO) +
			       3 * (CUENTA-DE-SECUENCIA ESTADO)

 (7) Resolver el problema del 8-puzzle utilizando la función descrita en el
     apartado anterior con
       * Estado inicial:
	   ((2 1 6) (4 H 8) (7 5 3)) 
       * Estado final:
           ((1 2 3) (8 H 4) (7 6 5))
       * Métodos:
	   primero-el-mejor
       * Heurística:
	   heuristica-1, heuristica-2 y heuristica-3
     y rellenar la siguiente tabla:
	 
         +---------+--------------+--------------+--------------+
         |         | heuristica-1 | heuristica-2 | heuristica-3 |
         +---------+--------------+--------------+--------------+
         | Coste   |              |              |              |
         | Tiempo  |              |              |              |
         | Espacio |              |              |              |
         +---------+--------------+--------------+--------------+

 (8) Una vez finalizados todos los apartados anteriores, envía por correo
     electrónico a tu profesor los ficheros 
       "practica-03.txt"   (con Subject: Practica 3 (practica-03.txt))
       "8-puzzle.lsp"      (con Subject: Practica 3 (8-puzzle.lsp)
     Recuerda, las direcciones son:
        fmartin@cs.us.es si tu profesor es F. J. Martín.
        jalonso@cs.us.es si tu profesor es J. A. Alonso.