Activa las notificaciones para estar al tanto de lo más nuevo en tecnología.

¿Es posible resolver un crucigrama por computadora?

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...

crucigramas02

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 a este nicho particular. 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.

crucigrama00

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.

Usando Prolog para resolver 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 10×10 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.

crucigrama01

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 en Turbo Prolog:

/*************************************/
/* 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’]).

/* predicado num_lets(T,X1) es verdadero si T */
/* es el número de letras en la palabra 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) es verdfadero si M es de longitud T */

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

/* predicado intersect(C1,C2,N1,N2) extraé */
/* las letras de la posición Ni de la lista C1 */
/* y la letra en la posición N2 de la lista C2. */
/* Entonces preguntamos si son la misma letra extraída */
intersect(C1,C2,N1,N2) :-
extract(C1,N1,R),
extract(C2,N2,R).

/* predicado extract(C,N,R)esverdadero si R es */
/* la enésima letra en la lista C… */

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

/* Programa principal. */
/* selecciona las palabras de la longitud adecuada */
/* en un crucigrama dado. La longitud de las letras aquí */
/* son, respectivamente, 5, 6, 7, y 5. */

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.

A todo esto, si algún alumno de la Facultad de Ciencias quiere hacer tesis de licenciatura sobre este tema, comuníquese conmigo ([email protected]).

Referencias:

An Introduction to programming in Prolog, de Patrick Saint-Dizier, ed Springer-Verlag

Comentarios