El rompecabezas de 8 piezas (I)

Escriba un programa de acuerdo a la estructura de los programas planteados en AIMA, que resuelva el rompecabezas de 8 piezas.
Es imprescindible que utilice las estructuras de datos y formatos de programas propuestos. Puede adaptarlos desde el modo idiomático imperativo que figura en el AIMA, a un modo orientado a objetos, si así lo desea, pero debe conservar las formas originales.

1. El programa funcionará como primero en amplitud o en profundidad solamente cambiando la función de encolamiento usada. En todo caso deberá identificar claramente la función general de búsqueda, y las funciones específicas de primero amplitud, primero en profundidad, primero el mejor.


2. Modifique el programa para que implemente la búsqueda por profundización interativa.


3. Implemente la búsqueda A* como un caso particular de la búsqueda general. Debe tener la función heurística intercambiable. Se debe poder usar al menos las siguientes heurísticas:
   
   
   
   • h₁: Cantidad de números fuera de su lugar.
   
   
   • h₂: distancia de Manhattan.
   
   
   
   


4. Escriba un programa que genere en forma aleatoria K estados iniciales para el rompecabezas y los escriba en un archivo en disco. El formato del archivo será de un estado por cada renglón. Por ejemplo, el estado meta se codificaría como:
   

   
      12345678X
   

   
   donde la X representa el espacio en blanco. Note que el orden de codificación no es por filas o por renglones.
   


5. Corra las variantes de su programa de búsqueda contra los estados iniciales generados aleatoriamente (K no menor a 200), y cuente la cantidad de nodos expandidos antes de hallar la solución, y la cantidad de pasos de la misma. Debe usar profundización iterativa, A* con h₁ y A* con h₂. Promedie la cantidad de nodos expandidos para cada longitud de solución dada. Los estados iniciales usados deben entregarse como parte del trabajo práctico para su verificación; se debe usar el mismo conjunto de estados iniciales en las tres búsquedas.