Algoritmo para generar un crucigrama

Acabo de escribir mi propio en Python recientemente. Puedes encontrarlo aquí: http://bryanhelmig.com/python-crossword-puzzle-generator/. No crea crucigramas densos al estilo del NYT, sino más bien del tipo que podrías encontrar en un libro de pasatiempos para niños.

A diferencia de algunos algoritmos que encontré que implementaban un método de fuerza bruta aleatorio para colocar palabras como algunos han sugerido, intenté implementar un enfoque de fuerza bruta ligeramente más inteligente en la colocación de palabras. Aquí está mi proceso:

1. Crear una cuadrícula de cualquier tamaño y una lista de palabras.
2. Barajar la lista de palabras y luego ordenar las palabras de más largas a más cortas.
3. Colocar la primera y más larga palabra en la posición más a la izquierda arriba, 1,1 (vertical u horizontal).
4. Pasar a la siguiente palabra, recorrer cada letra de la palabra y cada celda de la cuadrícula buscando coincidencias letra a letra.
5. Cuando se encuentre una coincidencia, simplemente añadir esa posición a una lista de coordenadas sugeridas para esa palabra.
6. Recorrer la lista de coordenadas sugeridas y "calificar" la colocación de la palabra según cuántas otras palabras cruce. Calificaciones de 0 indican una mala colocación (adyacente a palabras existentes) o que no hubo cruces de palabras.
7. Volver al paso #4 hasta que la lista de palabras se haya agotado. Pase opcional.
8. Deberíamos tener ahora un crucigrama, pero la calidad puede ser irregular debido a algunas de las colocaciones aleatorias. Por lo tanto, almacenamos este crucigrama y volvemos al paso #2. Si el siguiente crucigrama tiene más palabras colocadas en el tablero, reemplaza al crucigrama almacenado. Esto está limitado en tiempo (encontrar el mejor crucigrama en x segundos).

Al final, tendrás un crucigrama decente o un rompecabezas de búsqueda de palabras, ya que son prácticamente lo mismo. Tiende a funcionar bastante bien, pero avísame si tienes alguna sugerencia de mejora. Cuadrículas más grandes se ejecutan de manera exponencial más lenta; listas de palabras más grandes de manera lineal. Las listas de palabras más grandes también tienen una probabilidad mucho mayor de obtener mejores números de colocación de palabras.

En realidad escribí un programa generador de crucigramas hace unos diez años (era enigmático pero las mismas reglas se aplicarían para crucigramas normales).

Tenía una lista de palabras (y pistas asociadas) almacenadas en un archivo ordenadas por uso descendente hasta la fecha (para que las palabras menos usadas estuvieran en la parte superior del archivo). Se elegía un template, básicamente una máscara de bits que representaba los cuadrados negros y libres, al azar de un conjunto proporcionado por el cliente.

Luego, para cada palabra incompleta en el rompecabezas (básicamente encontrar el primer cuadrado en blanco y ver si el de la derecha (palabra horizontal) o el de abajo (palabra vertical) también estaba en blanco), se hacía una búsqueda en el archivo en busca de la primera palabra que encajara, teniendo en cuenta las letras ya en esa palabra. Si no había una palabra que pudiera encajar, simplemente se marcaba toda la palabra como incompleta y se pasaba a la siguiente.

Al final habría algunas palabras incompletas que el compilador tendría que completar (y agregar la palabra y una pista al archivo si así lo deseaba). Si no podían encontrar ninguna idea, podrían editar el crucigrama manualmente para cambiar las restricciones o simplemente solicitar una regeneración total.

Una vez que el archivo de palabras/pistas alcanzó cierto tamaño (y se agregaban 50-100 pistas al día para este cliente), rara vez hubo más de dos o tres correcciones manuales que debían hacerse para cada crucigrama.

¿Por qué no utilizar un enfoque probabilístico aleatorio para empezar? Comienza con una palabra, y luego elige repetidamente una palabra al azar e intenta encajarla en el estado actual del rompecabezas sin romper las restricciones de tamaño, etc. Si fallas, simplemente comienza de nuevo.

Te sorprenderá cuántas veces un enfoque de Monte Carlo como este funciona.

Generaría dos números: Longitud y Puntuación de Scrabble. Supongamos que una puntuación baja de Scrabble significa que es más fácil unirse en (puntuaciones bajas = muchas letras comunes). Ordene la lista por longitud descendente y puntuación de Scrabble ascendente.

A continuación, simplemente vaya por la lista. Si la palabra no se cruza con una palabra existente (verifique contra cada palabra por su longitud y puntuación de Scrabble, respectivamente), entonces colóquela en la cola y verifique la siguiente palabra.

Repite esto y esto debería generar un crucigrama.

Por supuesto, estoy bastante seguro de que esto es O(n!) y no está garantizado que complete el crucigrama para ti, pero quizás alguien pueda mejorarlo.