Friday, July 24, 2009

Creador de crucigramas

Una amiga –que editaba una revista de negocios– me pidió que hiciese una sección de crucigramas, siempre y cuando ésta presentara nombres y términos dedicados a las finanzas y al mundo de los negocios. Yo le dije que lo haría sin dudarlo, pues a priori pensaba que ya en Internet más de una persona habría encarado la creación de crucigramas a través de la computadora.

Para mi sorpresa, encontré que el problema realmente no había sido analizado cuidadosamente. Por un momento pensé que debería haber ya muchos programas que me permitieran crear la malla cuadriculada en donde se pondrán las palabras, así como poner las casillas vetadas (las marcas negras), que separan las palabras. Una vez hecho esto, imaginaba que le podía dar una lista de palabras y el sistema intentaría acomodarlas al mejor estilo de un crucigrama. Pues bien, nada de eso existe estrictamente. ¿Por qué? Había que investigar el fenómeno.

La razón de esto es que la creación de crucigramas necesita de diversos pasos, unos que son labores triviales de la programación, pero que en última instancia los pasos finales son prácticamente difíciles de cumplir adecuadamente. Crear un programa que dibuje la cuadrícula y me permita poner los cuadros negros es algo sencillo, pero la generación del crucigrama representa la gran dificultad. Imaginemos que tenemos las palabras que queremos poner en el crucigrama. Es más supongamos que tenemos palabras de más, para que si una no se puede poner en donde debe ponerse, podamos poner otra de la misma cantidad de letras, por ejemplo.

Imaginemos el siguiente crucigrama elemental. Nótese que no es ni siquiera una cuadrícula con cierta simetría. Nada de eso, pero para efectos ilustrativos es muy interesante. Tenemos cuatro palabras que debemos acomodar en ese crucigrama. La palabra 1 es de 5 letras, la 2 es de 6 letras, la tercera es de 5 letras y la cuarta es de 7 letras. Ahora supongamos que tenemos las siguientes palabras, las cuales podemos usar para crear el crucigrama:

Las palabras que puedo poner son estas: market, trees, monkey, simple, wise, vague, sea, yacht, ocean, foggy, artista, realice, brave y quite. Estas pocas palabras son suficientes para trabajar en el programa demostrativo. ¿Cómo resolveremos el problema? Necesitamos poner lo siguiente: Una palabra de cinco letras con otra de seis letras, en donde se intersecten en la tercera letra de la primera palabra con la segunda letra de la segunda palabra; además, requerimos una tercera palabra de siete letra y una cuarta de cinco letras, en donde la intersección de la segunda con la tercera palabra sea en la posición cinco de la segunda palabra con la tercera posición de la tercera palabra; finalmente necesitamos que la intersección entre la tercera y la cuarta palabra se dé en la posición 5 de la tercera palabra con la posición 3 de la cuarta palabra.

Esto significa que hablamos de restricciones entre las propias palabras y posiciones específicas en donde deben coincidir las letras de ambas palabras en conflicto.

¿Cómo es que prolog resuelve el problema?

Para resolverlo con prolog, apelamos al backtrack, el cual significa regresar sobre sus propios pasos cuando el sistema se encuentra en un callejón sin salida. El sistema funciona así: primero resuelve en la meta la primera instrucción: hallar una palabra de 5 letras (M1). Una vez hecho esto, busca una palabra con 6 letras (M2). Ahora intenta ver si la intersección de M1 con M2 en la posición 3 de M1 con la posición 2 de M2 coinciden en la letra que va ahí, si eso pasa, entonces busca la siguiente meta a resolver, pero si esto falla, el sistema regresa (hacia atrás, es decir hace backtrack), y busca una nueva palabra de seis letras e intenta de nuevo satisfacer la intersección de M1 con M2. Si falla, busca una nueva palabra de seis letras… Y si ninguna de las palabras que tiene de seis letras funciona, sorprendentemente para algunos, el sistema no dice: no se puede resolver el crucigrama, sino que hace backtrack de nuevo y entonces busca una nueva palabra de cinco letras y re-empieza todo el proceso descrito antes con la de seis letras.

Dicho en otras palabras, prolog hace un verdadero esfuerzo de procesamiento, que incluso para resolver este simplísimo crucigrama, lleva cientos de miles de iteracciones a través del backtrack.

Ahora bien, extrapolemos esto a un crucigrama de 10x10 casilleros, en donde la cuadrícula tiene un dibujo incluso simétrico (esto es clásico de los crucigramas profesionales). Imaginemos entonces que no tenemos una decena de palabras, sino unas miles. Si definimos todas las restricciones, ¿cuánto tiempo le llevará al sistema hallar una solución si es que la hay? No lo sabemos. El sistema es no decidible, es decir, no podemos saber si hay una solución o no al crucigrama que acabamos de dibujar para que el sistema nos ponga las palabras adecuadas. La única manera de saberlo es intentar generar todos los posibles crucigramas con esas palabras (y con las restricciones definidas), para ver si existe semejante crucigrama o no.

El tema da para más. ¿Podrá escribirse un programa que genere un crucigrama dadas ciertas palabras? ¿qué otras restricciones habría que poner para que por lo menos, un programa de esta naturaleza ayudase a los creadores humanos en esta labor? Quizás éste es uno de esos programas que parecen simples pero que en el fondo contienen un sinfín de problemas no del todo resolubles incluso a través del cómputo.

Por cierto, ésta es la solución que entrega el sistema:


Éste es el código fuente:

/*************************************/
/* Crucigramas */
/* Por: La_Morsa */
/* Versión: 1.0 beta */
/* */
/* programa basado en el que aparece */
/* en el libro: An Introduction to */
/* programming in Prolog, de Patrick */
/* Saint-Dizier, ed Springer-Verlag */
/* */
/*************************************/

domains
wordlist = char*

predicates
word(wordlist)
num_lets(integer,wordlist)
long(integer,wordlist)
intersect(wordlist,wordlist,integer,integer)
extract(wordlist,integer,char)
crisscross(wordlist,wordlist,wordlist,wordlist)

clauses

word(['m','a','r','k','e','t']).
word(['t','r','e','e','s']).
word(['m','o','n','k','e','y']).
word(['s','i','m','p','l','e']).
word(['w','i','s','e']).
word(['v','a','g','u','e']).
word(['s','e','a']).
word(['y','a','c','h','t']).
word(['o','c','e','a','n']).
word(['f','o','g','g','y']).
word(['a','r','t','i','s','t']).
word(['r','e','a','l','i','z','e']).
word(['b','r','a','v','e']).
word(['q','u','i','t','e']).

/* predicate num_lets(T,X1) is true if T */
/* is the number of letters in the word X1 */

num_lets(0,[]). /* el total de letras que tiene la palabra [] es 0 */
num_lets(T,[M1|M2]) :-
num_lets(T1,M2),
T = T1 + 1.

/* predicate long(T,M) is true if M has lenght T */

long(T,M) :-
word(M),
num_lets(T,M).

/* predicate intersect(C1,C2,N1,N2) extracts */
/* the letters in position N1 from the list C1 */
/* and the one in position N2 from the list C2. */
/* It then ask whether the two extracted */
/* letters are the same. This is expressed */
/* through the ocurrence of the same variable */
/* R in both calls to extract. */

intersect(C1,C2,N1,N2) :-
extract(C1,N1,R),
extract(C2,N2,R).

/* predicate extract(C,N,R) is true if R is the */
/* Nth letter in the list C of letter... */

extract([C1|C2],1,C1).
extract([C1|C2],N,R) :-
M=N-1,
extract(C2,M,R).

/* predicate crisscross is the main call. It */
/* selects words of the appropiate lenght for */
/* a given grid. The lenght of the words here */
/* is, respectively, 5, 6, 7, and 5. It places */
/* constrains on the words through predicate */
/* intersect... */

crisscross(M1,M2,M3,M4) :-
long(5,M1), long(6,M2),
intersect(M1,M2,3,2),
long(7,M3),
intersect(M2,M3,5,2),
long(5,M4),
intersect(M3,M4,5,3).

goal
crisscross(M1,M2,M3,M4),
write(M1),nl,
write(M2),nl,
write(M3),nl,
write(M4),nl.

1 comment:

Akheron said...

Voy a probarlo para ver que tal...=D, la verdad es que se oye sencillo, se lee sencillo, pero se hace complejo como bien lo dijiste. =D