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.

La medida del desempeño en ajedrez

El ajedrez tiene una virtud sobre muchas otras actividades lúdicas/deportivas, que es la posibilidad de medir el desempeño y actuación de quienes practican esta actividad. Así, tenemos la medida del rating, la cual nos indica la fuerza ajedrecística de un jugador en comparación con la de otros. Esto se basa en los cálculos de Arpad Elo, inventor del sistema de rating, el cual parte que entre dos jugadores, cuya diferencia en puntuación Elo es de 100 puntos, el de mayor rating hará estadísticamente más del 68% de los puntos. Lo simpático de esta afirmación es que se cumple para jugadores cuyos ratings son 1300 y 1400 o 2600 y 2700 puntos, respectivamente.

Pues bien, otra medida que en algún momento se puso de moda y que sigue en boga, es la del desempeño o "performance", la cual supuestamente es el rating que un jugador tendría al haber hecho los puntos que hizo en un evento. Algunas organizaciones usan un algoritmo muy popular, denomina "algoritmo de los 400", para calcular el rating desempeño. De acuerdo a este algoritmo, el desempeño en términos de rating, para un evento, se calcula tomando

1. el rating de cada jugador al que se le ha ganado y añadiendo 400 puntos
2. el rating de cada jugador con el que se perdió y restándole 400 puntos
3. el rating de cada jugador con quienes empató

Se suman todos estos números y se divide por el número de juegos jugador. Esto puede expresarse por la fórmula:

    Performance/desempeño = [(rating total de los oponentes + 400 * (triunfos - derrotas)) / juegos jugados].

Sin embargo, esta es una simplificación porque no toma en cuenta el factor k de la fórmula del rating, la cual es diferente de acuerdo al nivel del jugador de ajedrez. Una k de 25 es para alguien de 2000 puntos. Una k de 5 es la que se usa para jugadores del más alto rating. Sin embargo, ofrece una fórmula simple para estimar el valor del desempeño de un jugador.

La FIDE, no obstante, calcula el desempeño mediante otra fórmula:

el promedio del rating de los oponentes + la diferencia en ratings.

La diferencia en ratings dp está basada en el porcentaje p que debe hacer un jugador en un torneo, el cual se usa como valor clave en la siguiente tabla:

  p       dp
--------------
0.99    +677
0.9     +366
0.8     +240
0.7     +149
0.6     + 72
0.5        0
0.4     - 72
0.3     -149
0.2     -240
0.1     -366
0.01    -677

p es simplemente los puntos hechos divididos entre el número de partidas jugadas. Note que, en el caso de un score perfecto, dp está indeterminado. La tabla que aquí presentamos no es la tabla completa. Ésta puede hallarse en el handbook de la FIDE.

Pues con estos valores en mente, sabemos que Karpov, en el torneo de Linares de 1994, ganó con 11 puntos de 13, frente a los mejores del momento: Kasparov, Shirov, Topalov, Bareev, Lautier, Kramnik, Kamsky, Anand, Ivanchuk, Gelfand, Illescas, Polgar y Beliavsky. Su desempeño se calculó en 2985 puntos Elo, el más alto de la historia hasta el 2009, en donde Carlsen hizo un performance de 3002 puntos. Cabe señalar que ese Linares 1994 fue uno de los torneos más fuertes de todos los tiempos. El desempeño de Karpov fue verdaderamente asombroso.

Pero toda esta reflexión viene a cuento porque leo que el GM Kuljasevic, de Croacia, tuvo un desempeño de 2714 puntos Elo, de acuerdo a la página de Susan Polgar, cuando este GM, de 2537 puntos Elo jugó con rivales de estos ratings: 2127, 2224, 2430, 2388, 2230 y 2479, y haciendo 5.5 puntos de 6 posibles. Bueno, la realidad es que este GM difícilmente haría este desempeño contra un grupo de 6 GMs de unos 2700 puntos, por lo cual, dudo mucho de esta medida y de sí realmente dice algo o es una mera especulación divertida.


_____

(*) La gráfica que ilustra este artículo es el desarrollo del rating del fortísimo GM Peter Svidler a través de los años, a partir del año 2000.