Bosquejo para crear software que genere y resuelva crucigramas

Uno de los temas que tengo en el tintero, desde hace años, es cómo se crean los crucigramas que vemos publicados en los periódicos. Y eso me lleva siempre a preguntarme: ¿Usan algún software específico para eso? ¿Es posible escribir un software que genere crucigramas "profesionales", es decir, crucigramas que contienen ciertas características (de las que hablaré más adelante)? Y más aún, es posible escribir software que -dado un diccionario de palabras (quizás muy grande), pueda resolverlos automáticamente.

Si lo pensamos, muchos juegos se resuelven ya hoy en día a través de software, por ejemplo, los sudokus, el cubo de Rubik, etc. La idea de software que genere y resuelva crucigramas cae probablemente en la "programación lúdica" y sin embargo, es un interesante reto a resolver. Para ello, primero definamos lo que quiero decir con un crucigrama "profesional". Básicamente es aquel que en la mayoría de los casos es una malla cuadrada de letras, en donde los límites entre las palabras son cuadros negros que forman una imagen geométrica, muchas veces incluso simétrica. Por ejemplo, el siguiente crucigrama no es muy profesional. El dibujo de los cuadros negros está más puesto por las necesidades de cómo están puestas las palabras que por el hacer un dibujo simétrico.

El siguiente crucigrama, es uno profesional. Obsérvese que el dibujo que se genera es simétrico. Esto es lo común en los crucigramas que aparecen en los periódicos y otras publicaciones.

Podemos pues definir el problema en dos partes: i. generación de un crucigrama y ii. resolución del mismo. Analicemos brevemente ambos temas:

i. Generación de un crucigrama

Crear crucigramas requiere de una lista de palabras y de una cuadrícula, que no necesariamente debe ser cuadrada, en donde aparecen las palabras elegidas. Desde luego que esas palabras deben poderse definir de acuerdo al diccionario de la Real Academia de la Lengua para así crear el acertijo completo. No es fácil, al menos en esta primera incursión, saber si primero debemos dibujar los cuadros negros, los límites de las palabras o bien, empezar a poner palabras y después poner el correspondiente dibujo de cuadros negros. En primera instancia pareciera que es necesario primero definir la imagen de cuadros negros y entonces empezar a acomodar las palabras. Hacerlo de manera inversa parece más difícil en el momento de querer dibujar una figura simétrica.

Desde luego, podemos en un principio obviar el problema de la figura de cuadros negros simétrica, pero claramente es importante en el momento de escribir un software que bien podría usarse en publicaciones comerciales. Así, dada una colección de palabras, tenemos que tener una manera de revisar de forma automática su definición, para poder incorporar después esto en el acertijo final. Una idea sería tener un diccionario de la Real Academia de la Lengua Española en formato electrónico para así hallar por software las definiciones que necesitamos. Afortunadamente hay más de una versión de este diccionario en PDF.

Una vez teniendo esto, probablemente lo que haya que hacer es categorizar las palabras que se quieren poner en el crucigrama en el número de letras, de una letra, dos, tres, hasta N letras. Esto parece ser una buena idea porque también podemos hacer un dibujo de cuadros negros y hacerlo de manera tal que haya espacio para palabras de una letra, dos letras, tres letras, etc.

Y una vez que tenemos todo esto, empezar por asignar a alguna parte de las cuadrícula una palabra... y entonces ver si podemos poner alguna otra que sea en el sentido opuesto, es decir, si pusimos una palabra en vertical, la siguiente debería ser quizás horizontal. No podemos poner todas las palabras horizontales o verticales porque entonces tendríamos zonas con palabras sin sentido. Podemos seguir este proceso hasta que ocurra un camino cerrado y entonces, al no tener ninguna palabra para poner tenemos dos opciones: a. buscar una palabra que cumpla con ciertos requisitos y entonces ponerla o bien, b. desechar la última palabra puesta y buscar otra, en un proceso de backtracking que bien podría irse casi hasta la primera palabra puesta si es necesario. Si hacemos esto último, el problema es que no podríamos garantizar que el crucigrama se generara. Es decir, tendríamos un programa indecidible. Sin embargo, este problema, el núcleo de la creación de un crucigrama, lo hace un problema fascinante.

ii. Resolución de un crucigrama

He visto desde hace mucho programas que buscan resolver crucigramas automáticamente. De hecho, en un libro en Prolog vi un pequeño programita que resuelve un crucigrama trivial, el cual lo hace a través de backtrack (ver aquí - https://la-morsa.blogspot.com/2009/07/creador-de-crucigramas.html). La idea es simple: se busca una primera palabra de la lista que contenga el número de letras que llenen el espacio de letras que estamos buscando. La ponemos y ahora buscamos la segunda palabra, que intersecte con la primera en alguna letra y qué, además, tenga la cantidad de letras necesarias para llenar el espacio. Si la encontramos la ponemos en el crucigrama y seguimos buscando. Pero... ¿qué pasa si hay un error y no tenemos ningunas palabra que resuelva el siguiente espacio de letras? Pues hacemos backtrack, es decir, nos regresamos al paso anterior, buscamos otra palabra que cumpla con las condiciones de la última palabra requerida (que sea diferente a la que ya pusimos). Si la hallamos, la ponemos y seguimos. Si no encontramos ninguna palabra, entonces hacemos backtrack sobre la palabra anterior a esta, y así sucesivamente. Eventualmente -si el crucigrama se puede resolver- el sistema lo podrá solucionar. Sin embargo, de nuevo caemos en el terreno de lo indecidible.

Otros detalles

Cabe decir que los crucigramas profesionales ya usan algunas palabras que ocurren frecuentemente cuando se generan este tipo de acertijos. Por ejemplo, muchas veces aparece "Dios del Sol egipcio", lo cual es "Ra". Hay así algunas palabras comodines que nos ayudan a la creación de un crucigrama profesional. En cambio, un crucigrama no profesional, de aficionado, cuando tiene que llenar un espacio y le quedaron las letras AVZ, por ejemplo, lo resuelve definiendo esa palabra como "Arturo Vázquez Zetina (iniciales)". Esto es muy poco profesional y me parece que este recurso no se usa en los crucigramas comerciales.

El problema de generación y resolución de crucigramas, creo yo, da para una tesis de licenciatura en la carrera de ciencias de la computación y/o matemáticas. Si alguien quiere hacer tesis con este tema, escríbame a morsa@la-morsa.com y lo platicamos.