Orekaria  
  El Equilibrista  
  Contacto  

 

Orekaria Gamers Window Relocator
 
 

 

Presentación
Algoritmo
Download
Forum

Algoritmo

Este programa nació como un ejercicio de Inteligencia Artificial. Al principio, comencé a 'enseñarle' al programa los procesos deductivos que yo mismo realizaba, como estos: miro si hay líneas que tienen todas las casillas llenas, luego aquellas en las que sólo hay un dato y el espacio es menor que la cantidad de casillas llenas, relleno lo que puedo a partir de casillas llenas situadas en los márgenes, coloco puntos donde es obvio que no hay llenos, reviso las intersecciones entre datos, etc.
Después de una semana, el programa funcionaba muy, muy rápido aunque los algoritmos necesarios eran cada vez más complejos.
Y, un día, entre algoritmo y algoritmo, cansado de meter algoritmos específicos para cada forma deductiva y cansado de que fueran ganando en complejidad y empezando a prever que siempre habría uno más, se me ocurrió algo que me pareció un poco salvaje: calcular todas las posibles combinaciones de una línea y , después, hacer un AND entre todas las posibilidades que hubieran aparecido para cada casilla. Cuando miraba algunas pinturas que tenían 8, 9, 10 o más datos por línea, e intentaba calcular las posibilidades que tendría que calcular el ordenador (¿millones?, ¿Cientos de millones? por línea), me parecía que no habría potencia en mi ordenador para procesarlas en un tiempo aceptable. Tampoco tenía claro que solucionara completamente las pinturas...
Sólo hacer la parte del algoritmo que 'propone' todas las combinaciones posibles, me costó un día, pero... es precioso. Utiliza una técnica recursiva con auto-finalización, como un proceso obsesivo con llave. Después, le añadí la parte del algoritmo responsable de sacar conclusiones.
Resultó una maravilla. Sencillo, robusto, fiable. Resolvía toda la pintura... salvo en las que hace falta cálculo probabilístico.
Pero, empezaron los problemas con las pinturas grandes. Al guardar todas las combinaciones en memoria, mi giga de memoria ultra rápida, se llenaba y el sistema operativo empezaba la paginación a disco, un desastre para el rendimiento...
Lo solucioné comprobando cada combinación en el momento en que es propuesta. Si no es válida, se detiene el generador de combinaciones. El resultado es que el rendimiento es bueno, es decir, tarda menos que un humano, pero no es satisfactorio para pinturas complejas.
En una futura versión, tengo la intención de añadir cálculo de probabilidades para que pueda resolver las pinturas que lo requieran. Pero, antes, debe mejorar mucho la velocidad del algoritmo, probablemente, reduciendo las posibilidades a comprobar.
Si te interesa participar en la elaboración del algoritmo, eres bienvenido/a.