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.

Para tomarse un breve descanso en el trabajo

Todos los seres que nos consideramos productivos, estamos prácticamente obligados a trabajar diario. Muchos de nosotros tenemos horarios y a veces incluso, estamos obligados a quedarnos más tiempo porque la "chamba" no se acabó y como de costumbre, "urge" sacarla antes de retirarnos. Así entonces, a veces tenemos largas, pero muy largas jornadas de trabajo.

Quizás no sería mala idea relajarnos de vez en cuando y tomarnos un descanso, aunque eso se ve difícil si tenemos un jefe cerca, porque si se nos sorprende rascándonos las narices, entonces probablemente recibamos una reprimenda, por decir lo menos. Por ello, muchas veces los empleados no producen lo que podrían producir. Están cansados y cometen errores y pifias que después hay que enmendar, con la consecuente pérdida de tiempo.

La solución del problema

Considerando esto, en La_Morsa Software Co. se nos ocurrió que podríamos ayudar a paliar estos problemas que ocurren sistemáticamente en las oficinas, sobre todo en quienes trabajan con computadoras todo el día. Es claro que la atención contínua a la pantalla puede ser desgastante y por ende hemos implantado una solución:

Se trata del "Instalador falso", sí. Un programa que se configura para instalar falsamente algúna actualización de Microsoft (para Windows), la cual -al ejecutarse- impide que sigamos trabajando hasta que ésta termine. El Instalador Falso no instala nada, sino que simula instalar algún paquete popular: actualizaciones de Windows, Bibliotecas de programación de Microsoft, etc., (el usuario elige la que mejor le conviene), y además, el propio usuario puede definir cuánto debe tardarse la instalación. Los valores adecuados son de 1, 2, 3, 5, 10, 20, 25 y 30 minutos. Es decir, en realidad quien empleé este programa podrá descansar el tiempo que decida va a tardar la instalación. Se puede además decirle al programa que simule la actividad de escribir a disco, para que así el sistema parezca que está escribiendo archivos y copiando manejadores, etc., asunto típico cuando se instala cualquier paquete de software.

Una vez que se ha definido todo esto, se manda crear un archivo (llamado setup1.ini), el cual contiene la especificación de los parámetros para la simulación del programa de instalación. Cuando se crea este proceso, se crea también un directorio llamado 'tempdummy' que tiene dos archivos, uno llamado 'project1.exe'y otro 'setup1.ini'. El 'project1.exe' es precisamente el simulador de instalaciones. Ejecútese y el programa leerá los parámetros creados en el archivo 'setup1.ini', el cual es un simple archivo de texto (modificable con cuaqluier editor elemental como Notepad, por ejemplo, y mostrará en la pantalla una ventana con una barra de progreso que mostrará los avances de la 'instalación'.

Usos del software

Utilícese el instalador falso cuando necesite tomarse un breve descanso. No abuse del programa, pues su jefe puede sospechar por qué usted instala tantas cosas en su computadora. Igualmente, puede ser útil cuando se tiene que dejar la computadora y no se quiere prestar a nadie. Si se ve que hay un sistema instalando 'quien sabe qué cosa', es probable que nadie decida tocar nada en su máquina hasta que usted regrese y lo autorice.

Algunos detalles técnicos

• El Instalador Falso contiene dos programas ejecutables, uno que hemos llamado 'editor', que es el que permite al usuario crear los parámetros para que el 'instalador' actúe.
• El Instalador Falso se encuentra en la carpeta tempdummy y se llama 'project1.exe'. Éste es el programa que debe ejecutarse cuando queremos realizar la simulación.
• La simulación de escribir al disco duro es muy simple. El instalador escribe un archivo llamado datosdummy.hdd, el cual contiene solamente caracteres ascii. Escribe 64 kbytes cada segundo de la instalación pero cada segundo recrea el archivo. Éste puede -al final de la simulación- si se desea, borrarse. La intención es que el sistema escriba a disco para hacer la simulación más realista.
• El directorio tempdummy, que es desde donde se ejecuta el Instalador Falso, se creó ahí porque en muchas computadoras, los permisos que da Windows a los usuarios impiden que el programa pueda ejecutarse correctamente. Por ende, se generó este directorio cuya función es únicamente impedir que por un problema de permisos, el instalador no funcione.

¿Comentarios?

Si le interesa este programa, escriba a morsa@la-morsa.com y a vuelta de correo recibirá instrucciones para descargarlo y usarlo.