Sunday, September 11, 2011

Sobre resolver con Prolog el problema de los sudokus

En mi último artículo sobre programación y sudokus, hablé de un programa que podría resolver, en esencia, cualquier sudoku que se le pusiese, utilizando para ello fuerza bruta, es decir, considerando todas las posibilidades de números a poner en cada casilla. Alguna combinación debe ser la adecuada y con ello el asunto estaría resuelto.

Cuando corrí mi programa, pensé que se tardaría algunas horas quizás, de hecho no lo sabía, pero sospechaba que así sería. Un par de horas después de haber empezado el proceso lo aborté porque me hartó. No se veía para cuando terminaría. Así que decidí primero ver cuántos cálculos tiene que hacer el programa para poder resolver el sudoku planteado, que en ese caso hablamos de 46 números por hallar. Si usamos Prolog, tenemos que calcular la cantidad de combinaciones con repetición de 9 números tomados de 46 en 46.

La fórmula para ello es:
                               (n+r-1)!
Combinaciones =  ----------
                                r!(n-1)!

 donde n es la cantidad de números diferentes y r es la cantidad de espacios a llenar. Además, se pueden repetir los números, es decir, no todos tienen que ser siempre distintos. El resultado de esto es 1,040,465,790, es decir, mil cuatrocientos millones de posibles combinaciones. Para entender la magnitud de este número, si cada combinación se genera en un segundo (muy lento), entonces tardará unos 32 años en probar todas las posibles combinaciones. Si hace 1000 combinaciones por segundo (una aproximación más razonable), el sistema tardará unos 120 días en resolver todas las posibles combinaciones de números. Algo sin duda, demasiado lento. Vaya, si hiciese 10000 combinaciones por segundo, tardaría 12 días en resolverlo. Aún así es muy lento.

La razón de esto es que el programa, como originalmente está escrito, está obligado a prtimero poner a todos los números que buscamos, un "1". Se prueban entonces la combinación (como si fuese una caja fuerte). Si no "se abre", entonces probamos con otra combinación, haciendo backtrack. El resultado es un gigantesco proceso de ir cambiando números.

¿Cómo se podría mejorar? Desde luego que la técnica de prolog de examinar hasta agotar todas las posibilidades (simple fuerza bruta), no es práctica en este caso. Se necesita más inteligencia. Aún así, si no se quiere pensar mucho, bien podría intercalarse la búsqueda de unos pocos números, y entonces checar algunas de las ecuaciones, si eso está correcto, entonces buscar las restantes. Esto es lo que en principio sugirió el buen amigo Eduardo Ramos, aunque aún así los resultados pueden tardar si bien nos va, muchos días. De hecho, el programa se vería esta intercalación así:

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 :-
            / horizontales */
          
             num(A1), num(B1), num(C1), num(D1),
             suma(5,A1,4,3,B1,6,C1,7,D1,45),
           
             num(A2), num(B2), num(C2), num(D2), num(E2),   

             num(F2), num(G2), num(H2),
             suma(A2,B2,1,C2,D2,E2,F2,G2,H2,45),
           
             num(A3), num(B3), num(C3), num(D3), num(E3),
             suma(A3,7,6,B3,C3,2,9,D3,E3,45),
           
             num(A4), num(B4), num(C4), num(D4),
             suma(A4,8,B4,7,C4,5,6,D4,1,45),
                       
             num(A5), num(B5), num(C5), num(D5),
             suma(7,6,A5,B5,3,C5,D5,8,9,45),
           
             num(A6), num(B6), num(C6), num(D6),
             suma(9,A6,3,8,B6,4,C6,2,D6,45),
           
             num(A7), num(B7), num(C7), num(D7), num(E7),
             suma(A7,B7,8,1,C7,D7,2,9,E7,45),

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

             num(F8), num(G8), num(H8),
             suma(A8,B8,C8,D8,E8,F8,3,G8,H8,45),

             num(A9), num(B9), num(C9), num(D9),
             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).
            

por cierto, este programa está en el antiguo turbo Prolog 2.0 de Borland.

La conclusión inicial es que si tuviésemos memoria infinita y poder de procesamiento infinito, las soluciones tipo prolog, resolviendo todo el árbol de búsquedas (árbol solución), podría llegar a la conclusión del resultado correcto. Pero en la vida real, al tener limitaciones en memoria y velocidad de proceso, esto desde luego vuelve impráctico este enfoque.

Cabe decir que no por ello prolog no es útil para resolver problemas. Simplemente el sudoku -utilizando el esquema de fuerza bruta- no es el más adecuado.

11 comments:

Eduardo Ramos said...

Resulta que uno de los ejemplos que trae el Visual Prolog 7.3 es precisamente un programa para resolver sudokus que demuestra de manera fehaciente que se puede usar prolog para escribir un programa que resuelva sudokus de manera eficiente. Dicho programa resuelve de manera instantánea el sudoku del artículo. De hecho, la interface gráfica ofrece la opción de hacer que el programa corra lento para que pueda uno ver de manera gráfica cómo el programa va llenando las casillas.
Lo que también es cierto es que dicho código no es fácil de leer, como el código del artículo que es básicamente la descripción de las reglas de Sudoku escritas en Prolog. Uno de los mayores atractivos de Prolog es que, para ciertos problemas, el programa para resolverlos es básicamente la descripción lógica del problema. Tristemente, los programas fáciles de entender pocas veces son los más eficientes.

HD said...

Sigo sin entender porque insistes en usar la suma, como si se tratara del cuadro mágico de 3x3. La regla no es "la suma" sino "que no se repitan"

Morsa said...

Sin duda que un programa que resuelva sudokus en prolog debe exhibir más inteligencia. Voy a ver el ejemplo que dices. Lo interesante en todo caso es que mi código es prolog puro, sin trucos, basándome sólo en backtrack.

saludos

Morsa said...

HD,

insisto en la suma porque puedo por ejemplo, sacar las permutaciones de nueve números diferentes, pero eso lo tengo que hacer para cada fdila del sudoku. ¿Cómo voy a saber que en cada columna hay números diferentes? tendría que hacer las comparaciones de todos contra todos... 1 con los demás (8 comparaciones), 2 con los demás (7 comparaciones), 3 con los demás (6 comparaciones), 4 con los demás (5 comparaciones), 5 con los demás (4 comparaciones), 6 con los demás (3 comparaciones), 7 con los demás (2 comparaciones) y 8 con el restante (1 comparación)... total: 28 comparaciones por cada renglón. Más eficiente es sumar que dé 45.

Primero, sabes que si calculas las permutaciones, todos los números serán diferentes en cada renglón. Ahora tienes que probar que en cada columna suma 45 y la única condición es precisamente que dé 45. Aún así, pudiese haber combinaciones de números que hagan eso, pero la restricción de las cajas de 3x3 los elimina.

De hecho, pensándolo mejor, la suma de los renglones no es necesaria si se usan las permutaciones, porque eso asegura que ya son 9 números diferentes.

saludos
Manuel

Armando Estrada said...

Hola Morsa,

El sudoku se puede resolver planteándolo como un problema de optimización en software especializado en investigación de operaciones. En el sistema SAS modulo SAS/OR se puede programar con un procedimiento llamado “proc optmodel” en pocas líneas. El problema se resuelve en fracciones de segundo.

Saludos

Morsa said...

Armando,

desconozco de lo que me hablas. Dame más datos, por favor.

saludos
Manuel

Armando Estrada said...

Hola Morsa,

http://en.wikipedia.org/wiki/Sudoku_algorithms#Solving_Sudokus_via_stochastic_search_.2F_optimization_methods

http://www.sascommunity.org/wiki/Solving_Sudoku_with_PROC_OPTMODEL_using_MILP_solver

Solucion:

5 9 4 3 1 6 8 7 2
3 2 1 9 7 8 5 6 4
8 7 6 5 4 2 9 1 3
4 8 2 7 9 5 6 3 1
7 6 5 2 3 1 4 8 9
9 1 3 8 6 4 7 2 5
6 4 8 1 5 3 2 9 7
1 5 7 6 2 9 3 4 8
2 3 9 4 8 7 1 5 6

Saludos

Morsa said...

Armando,

Gracias... le echaré un ojo. Muchos saludos
Manuel

Javier Frias said...

muchas gracias me ayudo muchisimo a resolver un ejercio parecido

Javier Frias said...

muchisimas gracias me ayudo mucho para resolver un trabajo practico

Morsa said...

Javier, y qué problema quisiste resolver?