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.