Friday, September 09, 2011

Usando Prolog para resolver sudokus


Hace tiempo ya, empecé con este asunto de los sudokus y la programación. La realidad es que este pasatiempo mental da muchas posibilidades para la ciencia de la computación. Por ejemplo, aquí esbozamos un sistema en Prolog para generar sudokus legales. El problema realmente es que puede llevar muchísimo tiempo que el sistema dé con una solución, pues Prolog está pensado para ser exhaustivo, para hallar todas las posibles soluciones. Si tomamos en cuenta que cada línea, columna y caja (3x3) debe tener 9 números diferentes, podemos usar un algoritmo primero para poner las 9 cifras diferentes en los casilleros y entonces hacer los cálculos que se necesitan. Sin embargo, para un sudoku real, de 9x9, es decir, 81 casillas, tenemos que calcular las permutaciones de 9 objetos, en 9 columnas. Ya escribí al respecto aquí.

Hoy me di a la tarea de escribir un programa en Prolog que resolviese sudokus. Se le da al sistema el sudoku con los números que son interrogantes y el sistema empieza a buscar todas las posibles soluciones. Por ejemplo, tomé este primer sudoku, uno muy sencillo:


Generé entonces mi programa en Prolog para resolver este sudoku en particular:

predicates

   sudoku
   suma(integer, integer, integer, integer, integer, 

        integer, integer, integer, integer, integer)
   num(integer)
  
clauses
  
   num(1).
   num(2).
   num(3).
   num(4).
   num(5).
   num(6).
   num(7).
   num(8).
   num(9).
  
   suma(A,B,C,D,E,F,G,H,I,R) :-
                                A+B+C+D+E+F+G+H+I = R.  

   sudoku :- num(A1), num(B1), num(C1), num(D1),
             num(A2), num(B2), num(C2), num(D2), 

             num(E2), num(F2), num(G2), num(H2),
             num(A3), num(B3), num(C3), num(D3), 

             num(E3),
             num(A4), num(B4), num(C4), num(D4),
             num(A5), num(B5), num(C5), num(D5),
             num(A6), num(B6), num(C6), num(D6),
             num(A7), num(B7), num(C7), num(D7), 

             num(E7),
             num(A8), num(B8), num(C8), num(D8), 

             num(E8),        
             num(F8), num(G8), num(H8),
             num(A9), num(B9), num(C9), num(D9),
            
             /* horizontales */
            
             suma(5,A1,4,3,B1,6,C1,7,D1,45),
             suma(A2,B2,1,C2,D2,E2,F2,G2,H2,45),
             suma(A3,7,6,B3,C3,2,9,D3,E3,45),
             suma(A4,8,B4,7,C4,5,6,D4,1,45),
             suma(7,6,A5,B5,3,C5,D5,8,9,45),
             suma(9,A6,3,8,B6,4,C6,2,D6,45),
             suma(A7,B7,8,1,C7,D7,2,9,E7,45),
             suma(A8,B8,C8,D8,E8,F8,3,G8,H8,45),
             suma(A9,3,B9,4,C9,7,1,D9,6,45),
            
             /* verticales */
            
             suma(5,A2,A3,A4,7,9,A7,A8,A9,45),
             suma(A1,B2,7,8,6,A6,B7,B8,3,45),
             suma(4,1,6,B4,A5,3,8,C8,B9,45),
             suma(3,C2,B3,7,B5,8,1,D8,4,45),
             suma(B1,D2,C3,C4,3,B6,C7,E8,C9,45),
             suma(6,E2,2,5,C5,4,D7,F8,7,45),
             suma(C1,F2,9,6,D5,C6,2,3,1,45),
             suma(7,G2,D3,D4,8,2,9,G8,D9,45),
             suma(D1,H2,E3,1,9,D6,E7,H8,6,45),
            
            
             /* cajas */
            
             suma(5,A1,4,A2,B2,1,A3,7,6,45),
             suma(3,B1,6,C2,D2,E2,B3,C3,2,45),
             suma(C1,7,D1,F2,G2,H2,9,D3,E3,45),
             suma(A4,8,B4,7,6,A5,9,A6,3,45),
             suma(7,C4,5,B5,3,C5,8,B6,4,45),
             suma(6,D4,1,D5,8,9,C6,2,D6,45),
             suma(A7,B7,8,A8,B8,C8,A9,3,B9,45),
             suma(1,C7,D7,D8,E8,F8,4,C9,7,45),
             suma(2,9,E7,3,G8,H8,1,D9,6,45).

            
Evidentemente éste es el enfoque de "fuerza bruta", el cual es clásico en Prolog. Los sudokus son un ejemplo de programa que en Prolog se vuelven no deterministico, es decir, no podemos saber a priori si existe una solución al problema hasta que Prolog no busque todas las soluciones posibles.

Curiosamente, aunque Prolog se usa como un enfoque de la Inteligencia Artificial (IA) para resolver problemas de forma inteligente, valga la redundancia, el programa que presentamos aquí no exhibe ninguna inteligencia, a lo más una terquedad del algoritmo de Robinsson, para poner todos las posibles valores en las incógnitas y así poderlo resolver.

¿Podrá mi programa resolver el sudoku planteado? ¿Cuánto tiempo le llevará? No voy a contestar por el momento a esto (se analizará en el siguiente artículo). En el mientras, ¿qué cree estimado lector/a que pase? ¿Cuánto tiempo sería el estimado para resolver este sudoku al cual le faltan 44 números? Será poco tiempo? ¿será mucho tiempo?  ¿Qué mejoras podrían hacerse al programa? ¿Esta técnica exhaustiva es lo correcto en este problema en particular?

3 comments:

Eduardo Ramos said...

Manuel: se me ocurre que sí hay cosas que se podrían hacer para hacer el programa más eficiente, empezando por no considerar los 9 dígitos para todas las posiciones donde falta un dígito, y evitar así dedicarle tiempo de procesamiento a combinaciones de dígitos que no van a resultar en soluciones válidas. Luego, en lo posible, las reglas más fáciles de evaluar las pondría primero (para que las combinaciones inválidas se descarten rápido y sin procesar mucho) y las más costosas de evaluar las pondría al final. Desgraciadamente (o afortunadamente, según se quiera ver) ninguna de las reglas del sudoku necesitan mucho procesamiento.
Me da miedo tratar de adivinar si el programa tal como está resuelve el sudoku rápido o no pero estoy seguro que ya nos dirás que pasa en el próximo artículo.
Hace fácil 20 años que fue la última vez que ví un programa en Prolog. En ese entonces se usaba Turbo Prolog (Borland era la onda en ese entonces). ¿Hay algún prolog gratuito con el que se pueda correr el programa que pusiste en el artículo? Le dediqué solo unos minutos ayer a buscar, y bajé el GNU Prolog pero cuando copié y pegué el programa del artículo generó errores y en eso me tuve que ir y ya no seguí investigando.
Saludos!

Morsa said...

Eduardo,

El turbo prolog creo que ya es público (funciona en una ventana de DOS)... Si no lo tienes, te lo puedo mandar. Hay además una versión ya para windows, llamada Visual Prolog, la cual es el sucesor de turbo prolog. Existe una versión descargable y gratuita, amén de funcional. La encontrarás buscando en Google.

Con respecto a lo que dices, en mi siguiente artículo del blog pongo mis conclusiones al respecto.

saludos
Manuel

Daniel Ricci said...
This comment has been removed by the author.