Hola usuario de nuestra página, tenemos la solución a tu pregunta, has scroll y la verás a continuación.
Solución:
Se me ocurrió una solución que probablemente no sea la más eficiente, pero funciona lo suficientemente bien. Básicamente:
- Ordene todas las palabras por longitud, de forma descendente.
- Tome la primera palabra y colóquela en la pizarra.
- Toma la siguiente palabra.
- Busque entre todas las palabras que ya están en el tablero y vea si hay alguna posible intersección (alguna letra común) con esta palabra.
- Si hay una ubicación posible para esta palabra, recorra todas las palabras que están en el tablero y verifique si la nueva palabra interfiere.
- Si esta palabra no rompe el tablero, colóquela allí y vaya al paso 3; de lo contrario, continúe buscando un lugar (paso 4).
- Continúe este ciclo hasta que todas las palabras estén colocadas o no puedan colocarse.
Esto lo convierte en un crucigrama funcional, aunque a menudo bastante pobre. Hice una serie de modificaciones en la receta básica anterior para obtener un mejor resultado.
- Al final de generar un crucigrama, déle una puntuación basada en cuántas de las palabras se colocaron (cuanto más, mejor), qué tan grande es el tablero (cuanto más pequeño, mejor) y la relación entre la altura y el ancho (cuanto más cerca a 1 mejor). Genere varios crucigramas y luego compare sus puntuaciones y elija el mejor.
- En lugar de ejecutar un número arbitrario de iteraciones, he decidido crear tantos crucigramas como sea posible en un período de tiempo arbitrario. Si solo tiene una pequeña lista de palabras, obtendrá docenas de posibles crucigramas en 5 segundos. Un crucigrama más grande solo se puede elegir entre 5 y 6 posibilidades.
- Al colocar una nueva palabra, en lugar de colocarla inmediatamente después de encontrar una ubicación aceptable, asigne una puntuación a la ubicación de la palabra en función de cuánto aumenta el tamaño de la cuadrícula y cuántas intersecciones hay (lo ideal es que desee que cada palabra sea cruzado por 2-3 otras palabras). Realice un seguimiento de todas las posiciones y sus puntuaciones y luego elija la mejor.
Recientemente escribí el mío en Python. Puede encontrarlo aquí: http://bryanhelmig.com/python-crossword-puzzle-generator/. No crea los crucigramas densos del estilo NYT, sino el estilo de los crucigramas que puede encontrar en un libro de rompecabezas para niños.
A diferencia de algunos algoritmos que descubrí que implementaron un método aleatorio de fuerza bruta para colocar palabras como algunos han sugerido, traté de implementar un enfoque de fuerza bruta un poco más inteligente en la colocación de palabras. Este es mi proceso:
- Crea una cuadrícula de cualquier tamaño y una lista de palabras.
- Mezcle la lista de palabras y luego ordene las palabras de la más larga a la más corta.
- Coloque la primera palabra y la más larga en la posición más alta a la izquierda, 1,1 (vertical u horizontal).
- Pase a la siguiente palabra, recorra cada letra de la palabra y cada celda de la cuadrícula en busca de coincidencias de letra con letra.
- Cuando se encuentra una coincidencia, simplemente agregue esa posición a una lista de coordenadas sugeridas para esa palabra.
- Recorra la lista de coordenadas sugeridas y “puntúe” la ubicación de la palabra según la cantidad de otras palabras que cruza. Las puntuaciones de 0 indican una mala ubicación (junto a las palabras existentes) o que no hubo cruces de palabras.
- Vuelva al paso 4 hasta que se agote la lista de palabras. Segundo pase opcional.
- Ahora deberíamos tener un crucigrama, pero la calidad puede ser impredecible debido a algunas de las ubicaciones aleatorias. Entonces, almacenamos este crucigrama en el búfer y volvemos al paso 2. Si el siguiente crucigrama tiene más palabras colocadas en el tablero, reemplaza el crucigrama en el búfer. Esto es por tiempo limitado (encuentra el mejor crucigrama en x segundos).
Al final, tienes un crucigrama decente o un rompecabezas de búsqueda de palabras, ya que son casi lo mismo. Suele funcionar bastante bien, pero avíseme si tiene alguna sugerencia de mejora. Las redes más grandes funcionan exponencialmente más lento; listas de palabras más grandes linealmente. Las listas de palabras más grandes también tienen muchas más posibilidades de obtener mejores números de ubicación de palabras.
De hecho, escribí un programa de generación de crucigramas hace unos diez años (era críptico, pero las mismas reglas se aplicarían a los crucigramas normales).
Tenía una lista de palabras (y pistas asociadas) almacenadas en un archivo ordenadas por uso descendente hasta la fecha (de modo que las palabras menos utilizadas estaban en la parte superior del archivo). Se eligió al azar una plantilla, básicamente una máscara de bits que representa los cuadrados negros y libres, de un grupo proporcionado por el cliente.
Luego, para cada palabra incompleta en el rompecabezas (básicamente busque el primer cuadrado en blanco y vea si el que está a la derecha (palabra transversal) o el que está debajo (palabra abajo) también está en blanco), se realizó una búsqueda de el archivo buscando la primera palabra que encajaba, teniendo en cuenta las letras que ya estaban en esa palabra. Si no había una palabra que pudiera encajar, simplemente marcó la palabra completa como incompleta y siguió adelante.
Al final habría algunas palabras incompletas que el compilador tendría que completar (y agregar la palabra y una pista al archivo si lo desea). Si no pudieran pensar alguna ideas, podrían editar el crucigrama manualmente para cambiar las limitaciones o simplemente pedir una regeneración total.
Una vez que el archivo de palabra / pista alcanzó un cierto tamaño (y agregaba de 50 a 100 pistas por día para este cliente), rara vez había un caso de más de dos o tres arreglos manuales que debían hacerse para cada crucigrama. .
Nos puedes añadir valor a nuestra información añadiendo tu experiencia en las notas.