3 de Noviembre, 2011

Algoritmo para generar crucigramas

Después de comprobar que no es nada fácil encontrar crucigramas para el excelente Xword, me he puesto a darle vueltas al tema y resulta que es interesante :P.

He implementado un algoritmo genérico para generar crucigramas™. Partiendo una lista de palabras con una descripción asociada y un tablero vacío, sigo los pasos siguientes:

  1. Empezamos con horizontal.
  2. Para cada palabra, repetir lo siguiente:
    • Calcular la puntuación de la palabra en todas las posiciones del tablero. Si cruza otra palabra, puntúa extra, al igual que si evitamos los bordes del tablero (he comprobado que si no los resultados son más aburridos).
    • Hay casos que descartan una posición: nos salimos del tablero, las casillas no están libres y no cruzamos la otra palabra (compartimos letra), o no hay espacio libre rodeando la palabra (salvo los cruces; esto también lo he comprobado por experiencia: los tableros resultantes quedan mejor).
  3. Escogemos la posición con mayor puntuación (si es que hay alguna que puntúe, que a veces una palabra no encaja).
  4. Cambiamos de sentido (horizontal a vertical y viceversa), y vamos al punto 2 hasta que nos quedamos sin palabras en la lista.

Con la suma de todas las puntuaciones de las posiciones elegidas, tenemos la puntuación del tablero.

Además de las condiciones particulares que he introducido tras probar varias ejecuciones, también evitaremos usar palabras que estén contenidas en otras palabras (por ejemplo: pelo y pelota), porque detectar esos casos resulta algo complicado y por ahora no me parece que compense ;).

Xword mostrando mi crucigrama
Xword está desarrollado en Python con GTK+, y lee ficheros .puz

Con este algoritmo es evidente que la puntuación total depende de las palabras, pero además también es importante el orden en que las procesamos por las interaciones con las palabras ya ubicadas en el tablero. Así que para un tablero de 13x13, con 16 palabras de entrada, calculamos el tablero para todas las permutaciones posibles y nos quedamos con el de mayor puntuación. Sí, claro :D.

Se trata de n! permutaciones, que en este ejemplo son 20922789888000. Dado que calcular un tablero en mi nuevo portátil tarda 34.88ms (usando solo una CPU), me llevaría obtener el mejor tablero unos 23141 años (redondeando), o 5785 años si usara toda la potencia de cálculo que tengo.

El problema se puede prestar a utilizar una estrategia map/reduce (tentador, no digo que no :P), pero como tampoco tengo un número de máquinas razonable para despiezar el problema, por ahora calculo un número de tableros aleatorios, y me quedo con el mejor. Y los resultados parecen aceptables.

Por ejemplo (la lista de palabras se me ocurrió tal cual, simplemente empiezan todas por p):

-----pelota-p
-----i------a
---pastilla-t
---e-t------a
-p-s-a-----p-
parco-percha-
-l-a--i----r-
pendiente--t-
-n-o--o----e-
-c----c-p--s-
piano-c-a----
-a---pincel--
------o-o----

1: Adulador
2: Ayuda a resolver el acertijo
3: Hembra del pato
4: Para el dolor de garganta
5: Pez extraído del mar con una caña
6: Capital de provincia del mismo nombre a orillas del río Carrión
7: Su suma es el todo
8: Corto, simple
9: Se dice que le sientan bien los trajes
10: Personaje de madera que mentía
11: Cuelga de la oreja
12: Nombre, Francisco
13: Instrumento musical con teclas
14: Herramienta del pintor

En esta ejecución sobre 100 tableros (requiere unos 3 segundos), este es el que más alta puntuación ha obtenido... y ha colocado 14 palabras de 16. No está mal.

He generado un fichero puz (complicado e indocumentado, pero parece ser el formato estándar :S), que puede usarse (entre otros) con Xword: crossword.puz.

La verdad es que el problema me está gustando. ¿Alguna idea de cómo mejorar el algoritmo para acercarnos todo lo posible al mejor tablero en un tiempo razonable?

Anotación por Juan J. Martínez, clasificada en: programming.

Hay 1 comentario

Gravatar

Te vas a quedar con todos los trabajos de la sección de pasatiempos de los periódicos :-)

por alidhaey, en 2011-11-04 07:00:36

Los comentarios están cerrados: los comentarios se cierran automáticamente una vez pasados 30 días. Si quieres comentar algo acerca de la anotación, puedes hacerlo por e-mail.

Algunas anotaciones relacionadas: