/* Habiendo leído El curioso incidente del perro a medianoche le tomé cierto buen gusto a los títulos largos :-) */
Hace unas semanas, Mahoo me regaló un pequeño libro con un montón de sudokus para resolver. Si bien conocía el juego, nunca me atrajo particularmente. En esos días, yo estaba buscando algún tema original para uno de los trabajos prácticos de Inteligencia Artificial. La consigna se refería al uso de algoritmos genéticos para la resolución de algún problema. Lo importante no era el programa, sino el análisis de su comportamiento: estudiando, por ejemplo, qué método de cruzamiento se aplica mejor o qué función de aptitud es más representativa.
Viendo como Mahoo se entretenía con alguno de ellos (práctica en la que también se iniciaba) se me ocurrió que un resolver de sudokus podría ser una linda propuesta para mi TP.
Los algoritmos genéticos intentan emular a la naturaleza, a base de prueba y error, favoreciendo a las soluciones más aptas y castigando a las que no lo son tanto. Suponiendo que el cruzamiento de las buenas-soluciones generan aún-mejores-soluciones. Se trata de la búsqueda probabilística, muy parecida a meter muchas soluciones en un cubilete gigante y agitarlas hasta encontrar algo útil.
Al tratarse de un problema determinístico, la solución dista muchísimo de ser óptima. De hecho, ni siquiera se asegura que vaya a haber una solución. Pero me pareció algo simpático de intentar.
El resultado, escrito en mi rústico Python, puede ser bajado de aquí (incluye instrucciones para correrlo en Windows). No, no esperen que funcione bien, advertidos están. Es uno de los peores métodos posibles para este tipo de problemas. Sólo llega a una solución cuando la cantidad de incógnitas es (muy) limitada. Se plantean soluciones a base de llenar de random cada uno de los casilleros vacíos y chequeando cuantos valores se repiten en cada fila, columna y región. Cuando este chequeo da 0, se llega a una solución. Bastante cavernícola como notarán.
Es natural pensar en cuál sería la forma correcta de llegar a una solución. Recordé las clases de Investigación Operativa y la utilización del método simplex para la solución a problemas con restricciones. De hecho, es una solución que muchos proponen. No se si alguno de ustedes lo ha intentado. Yo sí, durante las clases aburridas me senté a pensar como sería el conjunto de ecuaciones y me encontré con una demencial y frustrante cantidad de ecuaciones. Acá hay una linda explicación, la que resumo, haciendo énfasis en las complicaciones:
Se necesitan variables binarias de la forma xijk donde 1 significa que el símbolo k (de 1 a 9) va en la celda (i,j) de la solución. 0 significa que no está. Esto genera un total de 729 variables (93) lo que, como mínimo, asusta. Veamos las ecuaciones:
(1) Para que cada celda (i,j) tenga un símbolo y éste sea único. Se necesitan 81 ecuaciones como éstas (una por cada celda).
(2) Para que en la fila i cada símbolo esté una vez y que en todas las columnas sea distinto. Se necesitan 81 ecuaciones como éstas(una por cada columna y cada símbolo posible).
(3) Para que en la columna j cada símbolo esté una vez y que en todas las filas sea distinto. Se necesitan 81 ecuaciones como éstas(una por cada fila y cada símbolo posible).
(4) Para que en cada región cada símbolo esté una y solo una vez. Se necesitan 81 ecuaciones como éstas (una por cada región y cada símbolo posible).
(5) Representa el enunciado, es decir, el problema a resolver. Por ejemplo, x115=1 significa que en la celda (1,1) hay un 5. Dependiendo cuantos casilleros vengan asignados es la cantidad de igualdades como estas que se necesitan; típicamente, ~30.
(6) Restringe las variables al conjunto binario.
¡En total son más de 350 ecuaciones! Hay propuestas con menos ecuaciones, pero siempre serán muchísimas. Evidentemente, ésta tampoco es la solución óptima (aunque es mucho mejor que los algoritmos genéticos). Y su problema radica en que, desde algún punto de vista, el método simplex no se ajusta al problema. Gráficamente, las ecuaciones representan semiplanos en un hiperespacio multidimencional (de 9 dimensiones?) cuya intersección es, en caso que haya una única solución, un único punto. /* Puede que le esté pifiando en esta conclusión final y cualquier ratificación o rectificación es bienvenida */
Simplex está pensado para restricciones de máximos y mínimos donde el objetivo es maximizar o minimizar y las variables binarias intentan ampliar el método para restricciones de este tipo. Da soluciones múltiples en forma de un polígono, donde a una o más se las llama óptima, porque maximiza o minimiza la función objetivo. Es claro que el problema del sudoku no usa sus ventajas y abusa de sus debilidades.
Curiosamente, cuando comenté este problema a un reciente conocido, surgió que también él tuvo que hacer un trabajo práctico que resolvía sudokus. En este caso, el TP giraba entorno a la gestión de la pila para recorrer árboles. Particularmente, árboles empleados en la estrategia de backtracking. Así pues, éste es su programita, sencillo, simpático y rápido. Gracias Nacho :).
Los métodos basados en búsqueda combinatoria sobre árboles parecen ser particularmente buenas para el problema del sudoku. En la wikipedia figuran dos interesantes formas: backtracking y ramificación y poda.
Para terminar, una última casualidad: Por razones que no vienen al caso ahora y que seguramente provocarán un nuevo post en el futuro estoy aprendiendo un lenguaje para el procesamiento de señales llamado R. Estoy trabajando mucho con una biblioteca llamada sound. Buscándola en el repositorio de bibliotecas, me encuentro con una llamada sudoku. No resistí la tentación de probarla :). Un ejemplo de su uso:
> install.packages("sudoku")
> # es necesario instalar tcltk si se quiere la parte gráfica
> install.packages("tcltk")
> library(sudoku)
> library(tcltk)
> library(tkrplot)
> miSudoku <- generateSudoku(Nblank=50, print.it=TRUE)
+-------+-------+-------+
| 6 | 7 | 8 2 |
| 4 8 | 1 | 7 |
| | 8 2 | 5 |
+-------+-------+-------+
| | 1 | 9 7 |
| | 2 | 5 1 |
| 5 1 6 | 9 7 | |
+-------+-------+-------+
| | 4 8 | |
| 6 5 | 7 9 | 8 |
| | | 9 7 |
+-------+-------+-------+
> # la variable miSudoku es una matriz
> miSudoku
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
[1,] 0 6 0 0 7 0 0 8 2
[2,] 4 8 0 0 0 1 7 0 0
[3,] 0 0 0 8 2 0 5 0 0
[4,] 0 0 0 1 0 0 9 7 0
[5,] 0 0 0 0 0 2 0 5 1
[6,] 5 1 6 0 9 7 0 0 0
[7,] 0 0 0 0 4 8 0 0 0
[8,] 6 5 0 7 0 9 8 0 0
[9,] 0 0 0 0 0 0 0 9 7
> #La biblioteca incluye una función para para solucionarlo
> solveSudoku(miSudoku)
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
[1,] 1 6 5 9 7 3 4 8 2
[2,] 4 8 2 5 6 1 7 3 9
[3,] 3 7 9 8 2 4 5 1 6
[4,] 2 4 8 1 5 6 9 7 3
[5,] 7 9 3 4 8 2 6 5 1
[6,] 5 1 6 3 9 7 2 4 8
[7,] 9 3 7 2 4 8 1 6 5
[8,] 6 5 1 7 3 9 8 2 4
[9,] 8 2 4 6 1 5 3 9 7
> # Incluso trae soporte gráfico para resolverlo en una ventanita :)
> playSudoku()
Así fue como, un simple regalo, un TP universitario y un montón de simpáticas casualidades tuvieron su punto de conexión. Y que divertido que resultó ser :). Ahora tengo que escribir el informe sobre los algoritmos genéticos en el sudoku. La semana que viene espero publicarlo aquí.
UPDATE August 6th: El informe y los archivos relacionados ya está publicados.
.
Anoche me hallé frente a la biblioteca buscando nada en espacial. Necesitaba despejar la cabeza, olvidarme de los asuntos terrenales asociados con las complejas interacciones y relaciones humanas.
