• Author / Uploaded
• Víctor Beltrán Barrera

Citation preview

UNIVERSIDAD AUTÓNOMA DE QUERÉTARO

FACULTAD DE INGENIERÍA DIVISIÓN DE INVESTIGACIÓN Y POSGRADO

PRIMER REPORTE

DATOS GENERALES TÍTULO: ALGORITMO PARA RESOLVER SUDOKU. NOMBRE DEL ALUMNO: VÍCTOR BELTRÁN BARRERA.

NÚM. EXPEDIENTE: 163656.

NOMBRE DEL PROFESOR: DR. MARCO ANTONIO ACEVES FERNÁNDEZ. NOMBRE DE LA MATERIA: CÓMPUTO EVOLUTIVO.

FECHA DE ENTREGA: 24/01/2020.

ÍNDICE 1.- INTRODUCCIÓN …………………………………………………………………… 3

2.- MARCO TEÓRICO …………………………………………………………………. 4

3.- MATERIAL Y MÉTODOS …………………………………………………………. 6

4.- PSEUDOCÓDIGO …………………………………………………………………… 8

5.- DESARROLLO ……………………………………………………………………… 9

6.- RESULTADOS ……………………………………………………………………… 12

7.- DISCUCIÓN DE RESULTADOS …………………………………………………… 16

8.- CONCLUSIONES ……………………………………………………………………. 17

9.- REFERENCIAS ……………………………………………………………………… 18

1 INTRODUCCIÓN. El SUDOKU es un juego matemático desarrollado por el matemático Leonhard Euler en el año de 1738. (Salazar, 2010). En un principio, el juego no contaba con muchos seguidores debido al poco conocimiento que se tenía de éste, sin embargo, en 1970 se divulgó su existencia en Nueva York cuando Walter MacKey lo publica en la revista de pasatiempos “Math Puzzles and Logic Problems” bajo el nombre de “Number Place”. En el año de 1984 Maki Kaji, originario de Japón, publicó en la revista de su compañía de rompecabezas “Nikoli” dicho juego bajo el nombre de “Suji wa dokushin ni kagiru”, abreviado y mejor conocido como “Sudoku” el cual significa “números individuales”. El juego se volvió muy popular en Japón y gracias a esto, en el año de 1997, el neozelandés Wayne Gould, inventó un programa de computadora para generar sudokus publicándolos en el diario británico “The Times” en 2004. A partir de allí, el sudoku se ha convertido en un juego de rompecabezas regular en periódicos y revistar líderes de todo el mundo y es disfrutado por público de todas las edades en el mundo entero. (Dhanya & Varghese, 2016).

2 MARCO TEÓRICO. DEFINICIÓN DEL JUEGO. Un sudoku consiste en un cuadrado con celdas y columnas de 9x9, en total 81 celdas, dichas celdas se subdividen en bloques de 3x3, en un principio algunas de estas celdas son llenadas con números del 1 al 9. Estas celdas rellenas se conocen como datos o pistas, como se muestra en la Figura 1. El objetivo del jugador es completar toda la cuadrícula utilizando los nueve dígitos para que cada fila, columna y bloque contenga cada número exactamente una vez. (Dhanya & Varghese, 2016).

Figura 1. Ejemplo de un arreglo de Sudoku. (Salazar, 2010). La solución de un Sudoku Puzzle requiere que cada fila, columna y bloque contenga todos los números en el conjunto [1,2, ... .9] y cada celda estará ocupada por un solo número. En resumen, resolver un sudoku se puede describir de la siguiente manera: 

Se busca rellenar con números una cuadrícula de 9x9 celdas. Esta cuadrícula está dividida en subcuadrículas de 3x3.



Los números a utilizar son los dígitos del 1 al 9 partiendo de algunos números ya

dispuestos en algunas celdas. 

No se debe repetir ninguna cifra en una misma fila, columna o subcuadrícula. MÉTODOS DE RESOLUCIÓN EN COMPUTADORAS. Algunos de los algoritmos más comúnmente usados para resolver sudokus en ordenadores son: el algoritmo de Backtracking, Rule-based y Boltzmann machine. BACKTRACKING. El método de backtracking es probablemente la estrategia de resolución de juegos de Sudoku más básica para algoritmos informáticos. Este algoritmo es un método de fuerza bruta que prueba diferentes números y, si falla, retrocede e intenta un número diferente. RULE-BASED. El algoritmo Rule-based utiliza varias reglas que han demostrado lógicamente que un cuadrado debe tener un cierto número o descartar números que son imposibles. Este método es muy similar a cómo los humanos resuelven el Sudoku y las reglas utilizadas se derivan de los métodos de resolución humanos. BOLTZMANN MACHINE. El algoritmo Boltzmann machine modela Sudokus usando una restricción para resolver problemas de redes neuronales artificiales. Los rompecabezas se ven como restricciones o límites que describen qué nodo no se puede conectar entre sí. Estas restricciones se codifican en pesos de una red neuronal artificial y luego se resuelven hasta que aparece una solución válida, con nodos activos que indican que se han elegido los dígitos apropiados. Este algoritmo es un algoritmo estocástico en contraste con los otros dos algoritmos.

3 MATERIAL Y MÉTODOS. En esta práctica se implementó el algoritmo Backtracking para la resolución del Sudoku. Backtracking es una técnica de búsqueda por fuerza bruta que explora un conjunto limitado de posibilidades hasta llegar a una solución. Este método recorre todos los arreglos posibles de un espacio de búsqueda y que debe personalizarse para una sola aplicación. En el caso general, se modela la solución como un vector x=( x1 , x2 , … , xn ) donde cada elemento es seleccionado de un conjunto finito ordenado S. dicho vector podría representar una disposición donde x 1 contiene el elemento i-ésimo de la permutación. A grandes rasgos, lo que hace este algoritmo es buscar e ir llenando los espacios vacíos con los posibles números que faltan y si llega a equivocarse entonces regresa, quita el número antes puesto y prueba con otra solución. MÉTODO. Lo que se plantea para resolver el problema es hacer un chequeo general de cada celda del sudoku para revisar los espacios vacíos como se muestra en la Figura 2.

Figura 2. Identificación de espacios vacíos (ceros).

Una vez que se tienen identificados esos espacios vacíos, se proponen las posibles soluciones, esto es, se identifican los números que posiblemente pueden colocarse en dichas celdas vacías como se muestra en la Figura 3.

Figura 3. Identificación de los números que posiblemente pueden colocarse en una celda vacía. Lo siguiente es ir colocando números para llenar el sudoku y revisar si están correctamente colocados, en caso contrario se regresa un paso atrás para colocar números diferentes. De esta manera se irá rellenando el sudoku hasta que no quede ningún espacio vacío, siempre respetando las reglas del juego.

4 PSEUDOCÓDIGO. Resolver(Sudoku) { if(celdas vacías == 0)//No se encuentran celdas vacías return true;//Se completó el sudoku else//Se encontró una celda vacía for(i=1:9)//opciones de 1-9 { if(Posible solución)//Hay posibles soluciones { sudoku(celda vacía)=i;//se asigna el número a la celda resolver(sudoku);//Recursividad } } sudoku(celda vacía)=0;//retroceso para nuevo intento }

5 DESARROLLO. El algoritmo de resolución del sudoku fue desarrollado en MATLAB y consta de tres funciones, a continuación, se explica paso a paso cada una de ellas. El primer paso es verificar si existen espacios vacíos en las celdas, esto es, si se encuentra algún cero ya que, en caso de que no se encuentre ningún cero significará que el sudoku está completamente relleno. Para esto se implementó la función CheckZ y lo que hace es escanear cada una de las celdas del sudoku para revisar si hay o no algún cero como se muestra en la Figura 4.

Figura 4. Revisión de celdas vacías. Cuando se logra identificar un espacio vacío, se toman las coordenadas de la celda y se procede a encontrar los números que puedan ocupar posiblemente dicha celda. La función PosIn realiza esta tarea, para ello se genera un vector de posibles soluciones x=( x1 , x2 , … , x 9) igualado en un principio a cero para todos sus valores y se comienza a revisar el renglón, la columna y la sub-

matriz de la celda en cuestión. Cada vez que se encuentre una pista (valor original) el elemento del vector de posibles soluciones con dicho índice toma el valor de 1, esto para marcar como un valor ya establecido y que no puede cambiar o que no es una posible solución como se muestra en la Figura 5. Al final de la función, el vector de posibles soluciones toma los valores de los posibles números que pueden colocarse en la celda. Ver Figura 6.

Figura 5.- Generación del vector de posibles soluciones.

Figura 6.- Vector final de posibles soluciones. Una vez obtenido el vector de las posibles soluciones, se comienza a colocar los valores de dicho vector en la celda inicial, comenzando por el número con el índice más bajo y se vuelve a repetir el proceso. En la Figura 7 se puede apreciar el sudoku generado al final del primer ciclo del algoritmo.

Figura 7.- Sudoku generado después del primer ciclo del algoritmo. En caso de no haber ningún valor en el vector de posibles soluciones significa que los números introducidos no son una solución y se hace el backtracking colocando nuevamente en cero el valor de la celda y se prueba con un número diferente dentro del vector de posibles soluciones antes dado.

6 RESULTADOS. A continuación, se muestra una parte de la salida en consola del proceso del algoritmo realizado. En la siguiente figura se muestra la salida de consola después de haber llenado el último renglón del sudoku, se empieza a realizar el análisis de la celda (8,1) marcada en azul. Se observa que no hay ningún valor en el vector de posibles soluciones por lo que los valores introducidos en el último renglón están acomodados de manera incorrecta y por lo tanto el algoritmo realiza el backtracking.

Figura 8.- Análisis de la celda (8,1). Como se espera, la función de backtracking retrocede y vuelve a poner el último valor modificado en cero y repite este proceso de tal manera que vuelve al punto donde haya otra posible solución.

Figura 9.- Backtracking.

Figura 10.- Backtracking. Una vez llegado a una nueva ramificación de las soluciones, comienza nuevamente el análisis e introduce una combinación diferente de los números dentro de las posibles soluciones. En la siguiente figura se observa que nuevamente, al hacer el análisis de la celda (9,7) no se generan posibles soluciones por lo que es necesario retroceder nuevamente.

Figura 11.- Celda (9,7) sin posibles soluciones. Al regresar e introducir un valor diferente se vuelve a realizar todo el proceso y se vuelve a generar un vector de posibles soluciones para la celda siguiente.

Figura 12.- Nuevo vector de posibles soluciones generado. Nuevamente se realiza el análisis y se genera una única posible solución en el espacio restante del renglón.

Figura 13.- Último valor de posibles soluciones generado para la celda (9,7). Al realizar esto, se completa el primer renglón y el algoritmo procede a realizar el análisis de la celda (8,1) como se muestra en la Figura 14, generando una única posible solución y por consiguiente se coloca dicho valor en la celda.

Figura 14.- Análisis de la celda (8,1) con única solución.

Figura 15.- Nuevo valor introducido en el sudoku. Este proceso se repite hasta que se llegue a la solución correcta del sudoku.

Figura 16.- Solución final dada por el algoritmo realizado.

7 DISCUCIÓN DE RESULTADOS. Los resultados obtenidos en la implementación del algoritmo de backtracking para la resolución del sudoku fueron satisfactorios. Una de las características principales de este algoritmo es que, si existe una solución, el algoritmo la va a encontrar, es uno de los puntos fuertes que tiene esta técnica. A pesar de eso, este algoritmo también es conocido como un algoritmo de uso rudo por la manera en que resuelve el problema ya que tiene que ir revisando celda por celda si hay un espacio vacío, calculando las posibles soluciones, probarlas y cada vez que se equivoca tiene que dar marcha atrás para probar con una combinación distinta, de tal forma que va haciendo muchas ramificaciones para todas las posibles soluciones. Basados en los resultados se puede decir que, aunque se encuentra una solución, no se hace de la manera más eficiente ya que realiza una gran cantidad de iteraciones para poder llegar al resultado correcto. Es una técnica sencilla, pero demanda muchos recursos.

8 CONCLUSIONES. El algoritmo de backtracking es uno de los algoritmos más fáciles de implementar computacionalmente pero también es un algoritmo poco eficiente en comparación con algoritmos más robustos, como lo son el algoritmo basado en reglas y la máquina de Boltzmann, debido a su parte recursiva ya que genera una gran demanda en el consumo de la memoria de la computadora y tiene un gran tiempo de ejecución por las tantas ramificaciones de soluciones posibles para el juego. Otro aspecto a considerar es que se puede implementar en distintas aplicaciones, pero se tiene que adecuar para cada una de ellas. En conclusión, se puede decir que las principales ventajas de este algoritmo son:   

Fácil de implementar. Resuelve el problema. Adaptable a problemas.

Las principales desventajas de este algoritmo:   

Sólo funciona con soluciones finitas. Demanda muchos recursos a la computadora. Tiempo de ejecución.

9 REFERENCIAS. Dhanya, J. & Varghese, P. (2016). Recursive Backtracking for Solving 9*9 Sudoku Puzzle. International Journal of Data Mining. Vol. 6, No. 1. doi: 10.9756/BIJDM.8128. Salazar, F. INCURSIONANDO EN EL SUDOKU. Boletín Electrónico No. 07. PDF visto en http://www.fsalazar.bizland.com/LANDIVAR/ING-PRIMERO/boletin07/URL_07_BAS04.pdf. Consultado el 22 de enero del 2020.