Hola

Práctica 1: Representación y búsqueda
IAIC – Curso 2010-2011

Comportamiento Algoritmos Búsquedas No Informadas
Esta práctica la realiza cada alumno de forma individual. Se puede comentar entrecompañeros el modo de resolverla. No se permite reutilizar código de los compañeros. Se trata de analizar, para un problema concreto, qué comportamiento tienen los algoritmos de búsqueda 1º enprofundidad, 1º en anchura, profundidad limitada y coste uniforme. Se ha de usar la librería AIMA del libro de Norvig y Russell, 2ª edición, qué está en el campus virtual. Algunos algoritmos necesitanmodificaciones –p.e.: profundidad limitada. El problema Se trata de resolver un sudoku. Se ha escogido un problema de sobra conocido para contrastar las diferencias de este modo de resolverlo usando elparadigma de estados en relación con métodos clásicos. Un sudoku es un tablero de nueve casillas de lado. Se debe rellenar con dígitos del 1 al 9 sin que se repita ningún dígito en una misma fila, columnao bloque de 3x3 casillas de los 9 que componen el tablero, como se muestra en el ejemplo: 2 8 4 6 2 9 4 1 3 7 5 7 4 7 Tablero inicial 6 7 3 5 8 2 6 6 5 9 8 7 3 2 1 9 3 1 1 8 3 5 7 8 1 4 6 3 2 9 9 4 13 2 5 6 7 8 2 6 3 1 7 6 5 9 8 2 3 7 4 2 5 8 9 5 7 4 7 3 8 6 9 9 1 2 4 3 4 2 1 5 8 5 8 6 9 1 1 4 7 3 6 Tablero objetivo 4 1 9 6 5 8 7 3 2 8 3 6 2 1 7 9 4 5

Se parte de un tablero inicial(cualquiera,) con ciertos dígitos ya asignados a determinadas casillas. El problema consiste en rellenar correctamente el resto de las casillas del tablero (no se mueven los dígitos de casilla). Se asume que lostableros iniciales garantizan tener una única solución. La búsqueda debe ser aplicable a cualquier tablero inicial. El coste de un movimiento se asume 1.

Se pide:
1. Fijar una representaciónadecuada para el problema, utilizando el paradigma del espacio de estados. Se valora la simplicidad. 2. Fijar los datos de entrada necesarios a incorporar en un fichero de texto de cara a dar los datos...