He escrito un programa de crucigramas anteriormente (críptico pero la teoría detrás de la construcción es idéntica).
Tenía una base de datos de palabras y sus pistas que podían ordenarse por tiempos utilizados (de modo que no tendería a obtener crucigramas duplicados en ejecuciones posteriores).
Lo primero que debes hacer es diseñar tus patrones (negros donde no puedes poner letras y blancos donde puedas). Intentar ajustar palabras en una cuadrícula mientras se crea el patrón sobre la marcha consume mucho tiempo y es propenso a errores. Si observa la mayoría de los crucigramas, tienden a seguir ciertas reglas para hacerlo más fácil. Las cosas son simétricas alrededor de una de las diagonales y rechaza un cuadrado de cuatro glóbulos blancos (para facilitar la tarea de seleccionar palabras adecuadas).
Una vez que tenga el patrón, , entonces comienza a encontrar palabras para colocar en él. De esta forma, sabría que "aplicación" fue start de la palabra y podrá limitar sus búsquedas a aquellas que comiencen con "app", no a cada palabra que tenga "app" en ella. Del mismo modo para las palabras donde tiene letras conocidas en cualquier posición.Es mucho más fácil ubicar palabras con letras en posiciones conocidas que evaluar esas letras en cualquier posición inicial dentro de una palabra.
El mero terminó siendo escrito en un script de shell (créalo o no) y usando el diccionario que vino de Linux como una herramienta de búsqueda de palabras. Si usted sabe que tiene una palabra de 5 letras que empiezan por "aplicación", es muy fácil de usar:
grep '^app..$' words.txt
para obtener una lista de todas las posibilidades válidos.
Y, como se encontró cada palabra, se copió en un archivo clues.txt que contenía tanto la palabra como varias pistas posibles. El formato real era usar {count, word, clue} donde la misma palabra puede existir en múltiples líneas con una pista diferente - esto permitió canalizar grep hasta sort para que las palabras/pistas menos utilizadas flotaran hacia arriba (siempre que una palabra/se usó una pista, su recuento se incrementó, por lo que es menos probable que se use la próxima vez).
Una vez que el archivo tenía un tamaño decente, el programa lo usaría primero para ubicar las palabras y, solo si no se encontraba, revertiría al archivo de palabras (sin pistas) donde se requeriría la intervención manual.
En realidad, terminó siendo bastante bueno en el trabajo. No fue deslumbrantemente rápido, pero no tuve que generar uno cada tres segundos; esto fue para un boletín comunitario enviado una vez a la semana.
Ahora que ha cambiado la pregunta a una variante de Scrabble, en realidad es mucho más difícil.
Debe tener en cuenta las letras que tiene, las letras en el tablero y el hecho de que hay muchos más lugares que debe evaluar. Esto hace que un método de fuerza bruta sea mucho más difícil.
Lo que haría como un corte inicial sería seleccionar posibilidades (posición inicial y dirección en el tablero) elegidas al azar, luego usar el mismo algoritmo que para la variante de crucigrama anterior para ubicar todas las palabras que puedan caber allí. Luego, si tiene las letras para satisfacer esa palabra, guárdela (junto con su puntaje) en una lista.
Tenga en cuenta que debe vigilar para no interferir con otras palabras en el pizarrón.
que seguiría examinando las posibilidades hasta que uno de:
- su lista es lo suficientemente grande como para elegir.
- se te acabó el tiempo.
- ha examinado suficientes posibilidades para satisfacer su nivel de competencia.
Esa última es importante: si está jugando como un principiante, no quiere examinar exhaustivamente millones de posibilidades.
A continuación, elija el mejor movimiento de su lista (o tal vez no el mejor si juega en el nivel de principiante; todo depende de qué tan buena sea la computadora).
¿Cómo buscar este diccionario con restricciones en las letras no primarias? p.ej. la segunda letra debe ser un P? –
Esto se llama árbol "trie" o prefijo. –