Sudoku con IA

Inteligencia Artificial

Entrega Laboratorio L2a.
Experimentos y conclusiones con CSP para el puzzle Sudoku mediante POO
5º de Ingeniería en Sistemas de Información de la FRM - UTN.



A. INTRODUCCION Y EXPLICACIÓN DE IMPLEMENTACIONES.
Se realizará el trabajo en base a problemas de satisfacción de restricciones y su aplicación en el
problema de resolución de Sudoku. Para resolver estetipo de problemas nos enfocaremos en 3 tipos de
estrategias: Backtracking, backtracking cronológico (forward checking o comprobación hacia adelante) y
AC-3.
Todas estas estrategias tienen porciones en común en su formulación. Todas comienzan y trabajan
con una lista de valores por instanciar. Para lo cual, en su algoritmo deben seleccionar una variable y
seleccionar un valor para luegoinstanciar a la variable con dicho valor. Seguidamente, cada estrategia
realiza una evaluación distinta. Para todos los casos, se obtiene el conocimiento de si la evaluación
muestra consistencia o inconsistencia (puede ser en base a una variable con sus restricciones hasta en base
al grafo total resultante con dominio reducido). Si el resultado es inconsistencia, se procede a sacar otro
valor para lavariable en cuestión, o si no quedan valores para dicha variable, se hace vuelta a atrás y se
continúa con otra variable. Si no quedan vas variable, hay fallo. Por otro lado, si hay consistencia, se
guarda la instancia y se procede con otra variable, si no hay más variables, finaliza el algoritmo con éxito.
La evaluación mencionada es el punto de variación más importante en las estrategias. Enbacktracking se comprueba la consistencia de la variable seleccionada instanciada con el valor
seleccionado. Para esto se verifica si viola alguna restricción con sus vecinos del grafo. En AC-3 al
seleccionar una variable con un valor se obtiene una instancia del grafo. Luego, se evalúa la consistencia
completa del grafo, verificando que todos y cada uno de sus arcos sean consistentes. Enesta porción de la
estrategia se eliminan valores posibles para variables de manera que todos los arcos sean consistentes. Si
luego de hacer esto no todos los arcos son consistentes, hay fallo y se procede a probar con otro valor. Si
es consistente, se guarda la instancia del grafo con el dominio reducido obtenido y se continúa con el
algoritmo. En cronológico es similar a AC-3 solo que no evalúatodos los arcos del grafo, sino solo
aquellos que son formados desde cada uno de sus vecinos hasta la variable seleccionada. Por ejemplo, en
el juego del sudoku, si se selecciona el valor “3”para instanciar una celda, se elimina el valor “3” como
opción en todas las celdas de la fila y columna en donde está posicionada.
Para llevar a cabo Backtracking y Forward Checking la estructura deprogramación se basa en la
recursividad. Backtracking recibe una lista de celdas sin asignar. Primero verifica si la lista está vacía y si
el resultado del tablero es correcto devuelve verdadero (en este caso hay éxito y termina), sino extrae una
celda y hace una lista con los valores posibles a asignar. Luego, prueba con uno de estos, si es factible (no
viola ninguna restricción) con este, realizarecursividad con la misma función para lista de celdas
restantes, sino prueba con otro valor. Si ningún valor es factible, da falso y falla. Forward Checking es
similar, lo que varía es que el análisis de factibilidad lo hace según si es esta variable con su valor
seleccionado es arco consistente con sus vecinos.
En AC-3, particularmente en el problema de Sudoku, se debe contar con una listade celdas, luego
seleccionar una celda de dicha lista y un valor posible para la celda (según alguna heurística). Luego
verifica arco por arco (del grafo completo actual) para ver su consistencia, eliminando los valores para
todas las celdas que no hacen posible la consistencia entera. De ser consistente la salida, se guardan las
celdas con sus valores que permiten la consistencia, y así se...