Desde hace pila hasta hoy, de vez en vez, me vuelve a la cabeza pensar si se puede convertir el problema de rellenar un crucigrama en un algoritmo devorador.
El problema básico es de complejidad espacial lineal y temporal factorial. Se puede, con años de cpu, obtener todas las combinaciones posibles para una figura dada. Para uno de calidad comercial, extraida la cuadrícula de una dibujada en la revista Quiz, antes de que el ordenador de la primera solución, yo ya he hecho una y media.
¿Cómo y por qué? Qué carajo hace mi intuición en probar palabras que no sepa programar?
He empezado de cero el problema no se cuántas veces cuando se me ocurre una forma de acotar el árbol. Hasta el punto de que he llegado a pensar cosas que ya había pensado pero para aplicar en otro momento del algoritmo.
Allá en las rusias, en lo mas crudo del crudo invierno. Cuando las noches eran todo menos la hora de comer, se me ocurrió precalcular las intersecciones de las palabras y montar un índice en base de datos. Cuando llevaba unos treinta gigas de datos generados con sólo mil palabras, las mas usadas del español según la el corpus de la RAE, acoté el problema a las palabras de tres a diez letras: Unos catorce gigas de datos.
Crear los índices de las tablas llevaba horas pero la impaciencia de generar los datos me hizo no crearlos antes porque, las inserciones, cuestan más.
Todo eso por no buscar la siguiente palabra a probar, en una sola consulta a base de datos podría saber si la palabra a probar con las letras que ya se habían generado tenía posibilidades de devolver una solución. Esa era la idea de ese día. Bajando la complejidad de prueba de una palabra, el algoritmo sería, al fin, un devorador.
El primer ensayo del algoritmo no tardaba nada pero al tener cinco cruces o seis la query no terminaba. Ojo, las tablas tenían nombres de la forma w5_a2_w31, palabras de cinco letras con la a en la segunda que se cruzan con palabras de tres que empiezan con a. Sólo un par de columnas o tres por tabla con los identificadores de las palabras.
Cuando una solución no me funciona, la medida desesperada es meter hilos. Eso nunca funciona mientras base de datos y código corran en la misma máquina. Se carga el procesamiento para nada. Eso lo se ahora.
Y, hoy, he despertado al monstruo otra vez. Pero creo que la ocurrencia del día era demasiado parecida a la del invierno Letón.
Pasaremos del tema otra vez.
