18 Sep 2020
Mi algoritmo Logi-5
Este mes de septiembre comenzamos el reto del Logi-5, un reto que trata sobre generar un puzzle derivado del sudoku, no es mas que un sudoku de 5x5 con piezas de pentominós como regiones.
El planteamiento es encontrar un algoritmo que genere puzzles aleatoriamente además de que el jugador pueda verificar su solución.
En principio suena sencillo de realizar, sin embargo, hay una gran cantidad de combinatorias posibles y hacer el algoritmo sin pensar puede llevarte a callejones sin salida, ya que debes estructurar los números en cada casilla con limitaciones que durante la generación pueden hacer imposible obtener un resultado correcto.
Backtracking
Back tracking es un algorítmo considerado de fuerza bruta que es el método mas común para resolver sudokus. Consiste en utilizar una pila donde vamos almacenando (push) la solución candidata por cada celda y retrocediendo (pop) por cada vez que la solución candidata actual viola una regla, de una manera ordenada podemos conseguir solucionar un sudoku, pero generarlo es otro problema, aunque podemos utilizar el mismo algoritmo, simplemente debemos asignar un valor aleatorio en cada celda, almacenando y retrocediendo hasta obtener un puzzle que contenga todos los requisitos.
Yo ya he utilizado este algoritmo en el pasado, para generar laberintos aleatorios y algo que encontré, es que utilizar un método ordenado puede llevarte a conseguir patrones en tu resultado.
Por ejemplo, en el caso de aplicar backtracking en generación de laberintos, conseguimos laberintos de un solo pasillo, es decir, que podemos resolver estos laberintos con el truco de la "mano derecha" que consiste en poner tu mano a un lado del muro y seguirlo hasta conseguir salir.
Ejemplo de wikipedia usando backtracking para generar laberintos:
Esta experiencia pasada me llevó a explorar otras formas de realizar este puzzle y de ahí surgió mi interés por la búsqueda estocástica o algoritmo estocástico.Búsqueda estocástica
El objetivo de la búsqueda estocástica es utilizar variables aleatorias, es decir, utilizar la aleatoriedad hasta conseguir un resultado válido. Según Wikipedia esto es un método bastante rápido, cosa que no lo creo, considero que es mas rápido utilizar el método anterior, tomando en cuenta que es una matriz de 5x5, que contiene 5 veces números del 1 al 5 y si mi matemática no me falla, entonces estaríamos hablando de un 5! elevado a 5, es decir un total de 24,883,200,000 combinaciones diferentes de las cuales no sé cuantas podrían ser válidas.
Entonces imagina rellenar en cada ciclo las casillas aleatoriamente hasta obtener un resultado válido, obviamente hay que aplicar una optimización a esto para que funcione.
Según el artículo en Wikipedia, se puede optimizar reordenando solo las casillas con errores hasta reducirlas a cero, sin embargo, al probar esto, me llevó a callejones sin salida, esto es porque en ocasiones reducía el número de errores hasta 4, sin embargo, ninguna combinación de esos 4 errores lograba un resultado válido, en ocasiones sí lo logra, pero no siempre.
Búsqueda estocástica con backtracking
Viendome en la situación de encontrarme con callejones sin salida, decidí aplicar una mezcla de ambos métodos, así que el pseudo código en bruto que conseguí fue el siguiente:
rellenar celdas en numeros del 1 al 5 aleatoriamente en cada region.
mientras el tablero tenga errores:
mezclar errores entre si
mientras la configuracion tenga mas errores que al inicio del loop:
mezclar errores entre si
si los nuevos errores son menores que los errores actuales:
push de configuracion actual a la pila
ademas si la pila tiene items:
pop de configuracion actual
si no:
rellenar celdas en numeros del 1 al 5 aleatoriamente en cada region
El objetivo aquí fue intentar reducir lo mas posible la cantidad de errores, es por eso, que decidí ordenar aleatoriamente cumpliendo el requisito de las regiones, luego mezclar los errores hasta que los errores sean iguales o menores, es decir, una solución candidata igual o mejor que la anterior, si la nueva configuración es mejor que la anterior (tiene menos errores) entonces lo apilamos, si tiene la misma cantidad de errores, entonces retrocedemos, esto lo hago ya que antes buscamos aleatoriamente una solución candidata igual o mejor, si la pila está vacía, volvemos a rellenar los números igual que al inicio.
A diferencia de el backtracking no vamos de casilla en casilla, validando una por una, si no que vamos validando en conjunto, reduciendo los errores hasta llegar a cero.
Considero que el pseudo código requiere una optimización, ya que hay código repetido y probablemente se puede mejorar, pero me conformo con el resultado por ahora.