practica sodoku (final)

INSTITUTO TECNOLÓGICO DE CD. CUAUHTÉMOCINTELIGENCIA ARTIFICIAL I

EJERCICIO PRÁCTICO

Práctica: Resolución de Sudokus-X con técnicas de búsqueda y Satisfacción de restricciones.

* Introducción.....................................................................................................................................................1 1 El juego del Sudoku..................................................................................................................................2

1.1 Características del juego...........................................................................................................................2.................... 2 Características del Sudoku como un problema a resolver mediante técnicas de búsqueda y satisfacción de restricciones........................................................................................................................................3

2.1 Representación estándar del tablero.........................................................................................................32.2 Planteamiento como un problema de propagación de restricciones.........................................................42.3 Planteamiento como un problema de búsqueda sin información.............................................................52.4 Planteamiento como un problema de búsqueda heurística.......................................................................52.5 Utilización de otras técnicas de búsqueda y heurísticas...........................................................................6

3 Trabajo a realizar.............................................................................................................................................63.1 Requisitos del programa...........................................................................................................................63.2 Requisitos de la documentación...............................................................................................................73.3 Entrega del material de la práctica............................................................................................................7

4 Evaluación.......................................................................................................................................................75 Más información..............................................................................................................................................8

IntroducciónEsta práctica consistirá en la implementación de un programa que utilice de forma conjunta algunas de las técnicas de búsqueda y satisfacción de restricciones, explicadas en teoría, poniéndolas en práctica para la resolución de Sudokus-X (una variante del Sudoku que se explicará más abajo). La evaluación de los programas entregados por los alumnos se basará en una competición cuyas reglas se explican más adelante. Por esta razón, este guión debe interpretarse como una serie de consideraciones básicas para resolver Sudokus (válidas también para Sudokus-X) y se anima a los alumnos a tratar de mejorar las técnicas descritas a continuación para obtener una buena clasificación en la competición (la nota de la práctica dependerá de la posición obtenida en la clasificación).

Entrega de la práctica

Fecha

Modo Presencial.

CATEDRÁTICO: ING. REYNA ESMERALDA GARCÍA GUADERRAMA 1


EJERCICIO PRÁCTICO

1 El juego del SudokuUn Sudoku es una plantilla que consiste en una retícula cuadrada de 81 casillas dividida en 9 cuadrados menores de 9 casillas (3 filas x 3 columnas cada uno) a los que llamaremos recuadros. La partida empieza con una plantilla inicial donde algunas de las casillas llevan ya inscrita una cifra del 1 al 9 (Ver siguiente figura).

Las reglas de este juego son muy simples: hay que ir ocupando las casillas vacías con los dígitos del 1 a 9, de modo que ninguno aparezca repetido en una misma fila, en una misma columna ni en un mismo recuadro.

Estas son las reglas del “Sudoku Clásico”. En esta práctica se considerará una variante del Sudoku, denominado Sudoku-X. Esta variante consiste en añadir la restricción adicional de que los dígitos de las diagonales principales también deben ser distintos.

En general, la solución de un Sudoku-X es única, pero pueden existir Sudokus-X con más de una solución; en cualquier caso, el programa entregado se considerará válido si encuentra una de las posibles soluciones a un Sudoku-X (en caso de que tenga varias).

Es importante tener en cuenta que ninguna regla aritmética ayudará a resolverlo: las celdas o casillas podrían estar ocupadas por nueve símbolos cualesquiera (no numéricos). No se trata, por tanto, de un juego aritmético, sino combinatorio, y para resolverlo basta y sobra con aplicar "reglas lógicas" sistemáticamente y, para un humano, una gran tenacidad.

1.1 Características del juegoPara resolver Sudokus (o Sudokus-X, en adelante se usarán ambos términos indistintamente) a mano con relativa pericia hay que descubrir las mañas o trucos por uno mismo. Un jugador sin ninguna experiencia puede dedicar como mucho 20 minutos en resolver su primer sudoku (de nivel fácil), pero una vez descubiertas las técnicas básicas pueden resolverse sudokus fáciles o difíciles en muy poco tiempo.

Para quienes no sepan cómo empezar, dos principios elementales:

· Buscar las casillas vacías que tengan mayores condicionantes (o restricciones), es decir, aquéllas que pertenecen a una fila, columna, recuadro o diagonal que estén "bastante llenos". Con un poco de suerte, las restricciones acumuladas (del tipo "la casilla no puede tener un 1, un 3 o un 7, porque ya hay un 1, un 3 y un 7 en la misma columna") pueden determinar unívocamente su valor.

· Buscar en qué lugar puede estar una determinada cifra dada en una columna, fila o recuadro dados (por ejemplo, "¿dónde debe estar el 3 en la columna 4?")

Pueden encontrarse guías más detalladas para resolver Sudokus en http://www.microsiervos.com/archivo/puzzles-y-rubik/resolver-sudokus-1.html, un blog (en castellano) sobre consejos acerca de cómo resolver Sudokus a mano, o bien en http://platea.pntic.mec.es/~ablanco/gi/tecnicasudoku.htm, una recopilación, obtenida del blog, de técnicas y estrategias para resolver Sudokus de cualquier nivel de dificultad.



EJERCICIO PRÁCTICO

Hay escritos varios programas que tratan de seguir de cerca los métodos que utilizamos los humanos. Estos programas que siguen razonamientos humanos son útiles para graduar la dificultad de las plantillas propuestas y, en función de los principios de razonamiento aplicados para completar la plantilla, califican a un sudoku como fácil, medianamente difícil, difícil y diabólico

2 Características del Sudoku como un problema a resolver mediante técnicas de búsqueda y satisfacción de restriccionesNo cuesta demasiado implementar un programa para resolver sudokus utilizando métodos retroactivos (backtracking) que simulen la técnica humana de "ensayo y error" (técnica, por otro lado, desaconsejable para resolver Sudokus). Un algoritmo simple puede comenzar por asignar una cifra de 1 a 9 a la primera casilla vacía, continuar recursivamente mientras no se encuentren contradicciones y, cada vez que una asignación de casilla vacía viole las leyes del Sudoku, probar con una nueva cifra. Este método explora todas las posibilidades sistemáticamente y por tanto es completo, aunque muy ineficiente, especialmente la solución de sudokus "difíciles" con este método puede ser intratable.

La eficiencia puede mejorarse utilizando técnicas de satisfacción y propagación de restricciones de manera que, cada vez que se coloque una cifra, el programa actualizará una tabla de posibilidades restantes para cada casilla vacía y no considerará nuevas cifras que no aparezcan en las posibilidades. A continuación se describirá, en primer lugar, cómo plantear la resolución de un Sudoku como un problema de satisfacción de restricciones simple y, en segundo lugar, cómo emplear técnicas de búsqueda heurística para mejorar aun más el rendimiento del algoritmo.

2.1 Representación estándar del tableroUna plantilla de Sudoku puede representarse como una matriz de 9 filas x 9 columnas en la que cada celda contiene los posibles valores con los que puede ser asignada (en una plantilla inicial habrá algunas casillas con un único valor). La siguiente figura muestra una plantilla inicial de Sudoku "justo antes de empezar a ser procesada":



EJERCICIO PRÁCTICO

Hay una notación estándar para Sudoku que denomina las filas con letras (A..I) y las columnas con números (1..9). Cada celda o casilla estará representada entonces por una combinación de letra y número (A1, por ejemplo), además, es usual denominar unidad a una columna, fila o recuadro y pares de una celda al resto de celdas que la "acompañan" en una unidad.

A1 A2 A3| A4 A5 A6| A7 A8 A9

B1 B2 B3| B4 B5 B6| B7 B8 B9

C1 C2 C3| C4 C5 C6| C7 C8 C9

---------+---------+---------

D1 D2 D3| D4 D5 D6| D7 D8 D9

E1 E2 E3| E4 E5 E6| E7 E8 E9

F1 F2 F3| F4 F5 F6| F7 F8 F9

---------+---------+---------

G1 G2 G3| G4 G5 G6| G7 G8 G9

H1 H2 H3| H4 H5 H6| H7 H8 H9

I1 I2 I3| I4 I5 I6| I7 I8 I9

Por ejemplo, {A1, A2, A3, B1, B2, B3, C1, C2, C3} forman un recuadro (que es una unidad) y, {B1, C1, D1, E1, F1, G1, H1, I1} son los pares de A1 en la columna 1.

2.2 Planteamiento como un problema de propagación de restriccionesA modo de guía, a continuación se presenta un planteamiento para resolver sudokus clásicos (no Sudokus-X) basado en una técnica de propagación de restricciones que es "relativamente" simple de implementar y que resuelve gran cantidad de sudokus clásicos de nivel "fácil" (parte de la práctica consiste en ampliarlo par el caso de Sudokus-X).

El objetivo en este caso consiste en obtener un sudoku donde cada celda de la matriz tenga un único dígito. Para ello podemos considerar dos procedimientos básicos:

· Cada vez que se detecte una celda Xi con un sólo dígito, d, debe eliminarse d como posibilidad para todos los valores de los pares de la celda (e.d. los "compañeros" de la celda en una columna, fila o recuadro). Si durante la eliminación de d en los pares de Xi nos encontramos una nueva celda Yj con un único valor, d2, habrá que eliminar éste para los pares de Yj más los pares que quedan por comprobar de Xj, y así sucesivamente. Este es un proceso recursivo básico de propagación de restricciones : establecer una restricción en una celda puede ocasionar el estableciento de restricciones adicionales en otras celdas relacionadas.

· Existe otra restricción que es conveniente considerar, a parte de la eliminación de valores en pares. Esta consiste en la asignación de un único valor a una celda. Pongamos por caso que, durante el proceso de eliminación, se detecta que se ha eliminado el valor 6 de la celda A1 y que, además, se están explorando los pares de A1 en la columna número 1. Imaginemos que de todos los pares de A1 en ésta columna, sólo C1 tiene como posible valor 6: entonces podemos asignar 6 como único valor de C1 y continuar con la propagación de restricciones.

· Estos procedimientos deberán comprobar además que no se producen errores por tratar de asignar un valor que no es consistente con las regas del Sudoku o por tratar de eliminar un valor de una celda que ya tenga un único valor asignado.



EJERCICIO PRÁCTICO

Finalmente, siguiendo estas recomendaciones podremos implementar un proceso muy simple, no retroactivo, de propagación de restricciones para solucionar un buen conjunto de Sudokus "fáciles" (pero, ojo, no cualquier Sudoku). En resumen, el proceso "dispararía" la propagación de restricciones arriba descrita sólo para las celdas de la plantilla inicial que tengan asignado un único valor. En la URL http://mathschallenge.net/project/sudoku.txt pueden encontrarse sudokus clásicos de este nivel para comprobarlo.

En la URL http://www.sudocue.net/sudoku-x-12-7193.sdm pueden encontrarse Sudokus-X (sin clasificar) para validar estas técnicas adaptadas a Sudokus-X.

Hay que tener en cuenta que este proceso basado en simple propagación de restricciones sin búsqueda es rápido pero no es completo, es decir, existen sudokus que tienen solución y que no pueden ser resueltos sólo mediante la combinación de los procesos de asignación y eliminación arriba descritos. Podemos encontrar otras técnicas para satisfacer y propagar restricciones que complementan y mejoran las descritas, pero que no pueden garantizar la completitud, aunque sí resolver una gran cantidad de Sudokus (estas estrategias pueden consultarse en http://www.krazydad.com/blog/2005/09/29/an-index-of-sudoku- strategies/).

No obstante hay técnicas que si garantizan la completitud de un algoritmo para la solución de cualquier sudoku y que incorporan técnicas de búsqueda, permitiendo construir programas para resolver Sudokus más eficientes.

2.3 Planteamiento como un problema de búsqueda sin informaciónUna primera aproximación a la resolución de cualquier sudoku consiste en la integración de un proceso de satisfacción de restricciones como el descrito en el apartado anterior con una estrategia de búsqueda. El algoritmo de búsqueda podría seguir los siguientes pasos:

· Primero, dado un sudoku, asegurarse de que no se ha encontrado la solución o de que se han violado las reglas del sudoku

· Segundo, si no se da ninguno de estos casos escoger una celda no asignada aún con un único valor y considerar todos los posibles valores de la celda

· Para cada valor, probar con asignarlo a la celda, propagar restricciones (como se ha descrito antes) y volver al primer paso.

Este algoritmo puede implementarse como una estrategia retroactiva o bien como una búsqueda primero en profundidad en la que se mantenga un grafo de búsqueda con ramas de búsqueda independientes, (es decir, un espacio de búsqueda en el que el nodo inicial será la plantilla inicial del sudoku y el resto de nodos se generan por cada uno de los posibles valores de la celda escogida).

Una correcta implementación de este algoritmo resolverá cualquier sudoku porque, en el peor de los casos, realizará una exploración exhaustiva de todas las posibilidades para cada una de las celdas del sudoku.

2.4 Planteamiento como un problema de búsqueda heurísticaEl algoritmo esbozado en el apartado anterior no hace uso de ningún tipo de información sobre el estado del sudoku durante el proceso de búsqueda, lo que puede dar lugar a un proceso de resolución muy lento para Sudokus difíciles. Podemos hacer uso en cada etapa de la búsqueda de información heurística a la hora de escoger la "mejor" celda no asignada aún con un único valor. La heurística más inmediata consiste en dar prioridad a las celdas con un menor número de posibilidades, "es de esperar" que de esta forma se llegue antes a la solución. Aunque existen otras técnicas propias de CSP que también pueden emplearse.

Finalmente, siguiendo estas recomendaciones podremos implementar un proceso de búsqueda informado que, junto a la propagación de restricciones, podrá solucionar un buen conjunto de Sudokus "difíciles".


http://www.sudocue.net/sudoku-x-12-7193.sdm


EJERCICIO PRÁCTICO

En la URL http://magictour.free.fr/top95 pueden encontrarse sudokus clásicos de este nivel para comprobar las técnicas implementadas (

En la URL http://www.sudocue.net/sudoku-x-12-7193.sdm pueden encontrarse Sudokus-X (sin clasificar) para comprobar

2.5 Utilización de otras técnicas de búsqueda y heurísticas

Las técnicas para resolver Sudokus que se han descrito en este guión de prácticas no son únicas, ni tampoco tienen por qué ser las más adecuadas. Al contrario, deben interpretarse como una guía básica para la elaboración de la práctica y, por tanto, animamos a los alumnos a que traten de introducir bien heurísticas o bien estrategias para la propagación y satisfacción de restricciones, que intenten mejorar las aquí esbozadas.

En la última sección de este guión aparecen enlaces de los que se puede extraer información interesante para tratar de mejorar estas técnicas. Además, si alguien se considera "experto/a en Sudokus" puede tratar de plasmar las técnicas que utiliza como heurísticas en el proceso de búsqueda.

3 Trabajo a realizarLa práctica consistirá en la implementación de un programa que utilice a la vez técnicas de búsqueda heurística y satisfacción de restricciones para resolver un Sudoku. Habrá que entregar también una documentación de la práctica, como se indica a continuación.

IMPORTANTE:

Tanto el trabajo a realizar como el material a entregar para la evaluación de la práctica tienen que respetar escrupulosamente las instrucciones que siguen a continuación, en caso contrario no se calificará la práctica.

3.1 Requisitos del programaEl programa deberá estar implementado en _______________, se nombrará sudoku y recibirá como argumento una cadena de caracteres que representan una plantilla inicial de Sudoku. El programa mostrará como resultado, por la salida estándar, una cadena de caracteres que represente el Sudoku solución (si no ha encontrado solución, el resultado será la cadena vacía).

Cada carácter de la cadena de entrada o salida que representa un Sudoku podrá ser:· Un dígito del 1 al 9, para representar que una celda tiene ya asignado un dígito en la plantilla inicial· Un punto '.', o un cero '0', o un guión, '-', para representar una celda vacía· Los caracteres "blanco", "fin de línea" u otros especiales son ignorados.

Por ejemplo, el Sudoku ilustrado en la primera sección de este guión se corresponderá con la siguiente cadena:

97.3.4.65.2.25.6.8............58.29....2.4.3....87.51............6.2.8.3.84.1.9.27

La siguiente cadena también debe considerarse válida para representar la misma plantilla inicial de Sudoku:

970304065

020506080

000000000

005802900

002040300

008705100

000000000




EJERCICIO PRÁCTICO

060208030

840109027

La utilización de varios posibles caracteres para representar celdas en blanco se debe a que no hay un estándar aceptado ampliamente para representar Sudokus mediante cadenas de caracteres; de hecho, en la URL http://mathschallenge.net/project/sudoku.txt (Sudokus Clásicos fáciles) se utiliza el '0' para la casilla vacía y en http://magictour.free.fr/top95 (Sudokus Clásicos difíciles), se utiliza el '.' .

En cualquier caso, el procesado de la cadena de caracteres de entrada no es una tarea compleja.

3.2 Requisitos de la documentaciónLa documentación del programa consistirá en un documento pdf con una extensión no mayor de 2 páginas, con los siguientes apartados:

· Algoritmo utilizado: donde se describirá a grandes rasgos, en un lenguaje claro, el algoritmo utilizado para implementar la solución. Deberá especificarse en el algoritmo:

· Técnicas de satisfacción de restricciones utilizadas: donde se indicarán las técnicas y heurísticas utilizadas para la satisfacción y propagación de restricciones. Si se han utilizado técnicas adicionales a las mostradas en el guión de prácticas, indicarlas además de adjuntar referencias sobre las fuentes consultadas.

· Técnicas de búsqueda y heurísticas utilizadas: donde se indicarán las técnicas de búsqueda y heurísticas utilizadas. Si se han utilizado técnicas adicionales a las mostradas en el guión de prácticas, indicarlas además de adjuntar referencias sobre las fuentes consultadas.

· Experimentos adicionales: en caso de realizar aportaciones o experimentos adicionales, indicarlo expresamente y adjuntar referencias sobre las fuentes consultadas.

3.3 Entrega del material de la práctica

La práctica se entregará como un programa comprimido (formato zip) con el siguiente contenido:

· El programa fuente, denominado obligatoriamente "sudoku".

· Un archivo con la documentación de la práctica.

El nombre del fichero .zip se corresponderá con la plantilla

<Apellido1>_<Apellido2>_<Nombre>.zip

y se entregará en un CD al catedrático .

4 EvaluaciónEl proceso de evaluación se basará en un sistema de competición con las siguientes reglas:

· El programa entregado será ejecutado para comprobar su funcionamiento con varios sudokus-X.

· La calificación final de la práctica dependerá de la posición en una clasificación de los programas entregados que se construirá atendiendo al tiempo invertido por cada programa en resolver 80 sudokus-X. El tiempo se calculará sumando los tiempos individuales en resolver cada sudoku, ejecutando el programa 80 veces recibiendo como entrada en cada iteración una cadena conteniendo un sudoku-X distinto. Las prácticas que resuelvan 80 sudokus-X en menos de 2 minutos, tendrán una calificación entre 7 y 9, atendiendo a la posición que tengan en la clasificación.

· Si durante la comprobación se sobrepasaran los 2 minutos de tiempo, se considerará entonces la cantidad de sudokus resueltos en ese tiempo para decidir la calificación entre 5 y 7.

· Si no se resuelve ningún sudoku la práctica se considerará suspensa.



EJERCICIO PRÁCTICO

· La calificación de 10 se reservará a las prácticas excepcionales, debidamente documentadas.

5 Más informaciónhttp://es.wikipedia.org/wiki/Sudoku Definición de Sudoku en Wikipedia

http://www.microsiervos.com/archivo/puzzles-y-rubik/resolver-sudokus-1.html Un blog (en castellano) sobre consejos acerca de cómo resolver Sudokus a mano

http://platea.pntic.mec.es/~ablanco/gi/tecnicasudoku.htm Una recopilación, obtenida del blog anterior, de técnicas y estrategias para resolver Sudokus de cualquier nivel de dificultad.

http://www.sudoku.com/howtosolve.htm Instrucciones (en inglés) paso a paso para resolver Sudokus

http://norvig.com/sudoku.html , el problema del Sudoku clásico resuelto en Python por Peter Norvig.

Los siguientes enlaces pueden ser fuentes interesantes para introducir nuevas estrategias para acelerar la propagación de restricciones o definir heurísticas que aceleren el proceso de búsqueda:

· http://www.scanraid.com/Sudoku.htm Un resolutor (en inglés) de Sudokus interactivo, muy ilustrativo sobre las distintas estrategias para la resolución de Sudokus.

· http://www.sadmansoftware.com/sudoku/techniques.htm Un índice (en inglés) de estrategias para Sudokus

Repositorios de Sudokus:

· http://mathschallenge.net/project/sudoku.txt Sudokus clásicos de nivel fácil

· http://magictour.free.fr/top95 Sudokus clásicos de nivel difícil

· http://www.sudocue.net/sudoku-x-12-7193.sdm Sudokus-X sin clasificar.



practica sodoku (final)

Documents