para generar crucigramas crucigrama algoritmo algorithm language-agnostic crossword

algorithm - crucigramas - Algoritmo para generar un crucigrama



algoritmo para generar crucigramas (13)

Dada una lista de palabras, ¿cómo harías para organizarlas en una cuadrícula de crucigramas?

No tendría que ser como un crucigrama "apropiado" que sea simétrico o algo por el estilo: básicamente solo da salida a una posición inicial y a una dirección para cada palabra.

¿Habría algún ejemplo de Java disponible?

¿Por qué no utilizar un enfoque probabilístico aleatorio para empezar? Comience con una palabra, y luego elija repetidamente una palabra aleatoria e intente adaptarla al estado actual del rompecabezas sin romper las restricciones sobre el tamaño, etc. Si falla, simplemente comience de nuevo.

Te sorprenderá la frecuencia con la que funciona un enfoque de Monte Carlo como este.

Aquí hay algunos códigos de JavaScript basados ​​en la respuesta de Nickf y el código de pitón de Bryan. Solo publicarlo en caso de que alguien más lo necesite en js.

function board(cols, rows) { //instantiator object for making gameboards this.cols = cols; this.rows = rows; var activeWordList = []; //keeps array of words actually placed in board var acrossCount = 0; var downCount = 0; var grid = new Array(cols); //create 2 dimensional array for letter grid for (var i = 0; i < rows; i++) { grid[i] = new Array(rows); } for (var x = 0; x < cols; x++) { for (var y = 0; y < rows; y++) { grid[x][y] = {}; grid[x][y].targetChar = EMPTYCHAR; //target character, hidden grid[x][y].indexDisplay = ''''; //used to display index number of word start grid[x][y].value = ''-''; //actual current letter shown on board } } function suggestCoords(word) { //search for potential cross placement locations var c = ''''; coordCount = []; coordCount = 0; for (i = 0; i < word.length; i++) { //cycle through each character of the word for (x = 0; x < GRID_HEIGHT; x++) { for (y = 0; y < GRID_WIDTH; y++) { c = word[i]; if (grid[x][y].targetChar == c) { //check for letter match in cell if (x - i + 1> 0 && x - i + word.length-1 < GRID_HEIGHT) { //would fit vertically? coordList[coordCount] = {}; coordList[coordCount].x = x - i; coordList[coordCount].y = y; coordList[coordCount].score = 0; coordList[coordCount].vertical = true; coordCount++; } if (y - i + 1 > 0 && y - i + word.length-1 < GRID_WIDTH) { //would fit horizontally? coordList[coordCount] = {}; coordList[coordCount].x = x; coordList[coordCount].y = y - i; coordList[coordCount].score = 0; coordList[coordCount].vertical = false; coordCount++; } } } } } } function checkFitScore(word, x, y, vertical) { var fitScore = 1; //default is 1, 2+ has crosses, 0 is invalid due to collision if (vertical) { //vertical checking for (i = 0; i < word.length; i++) { if (i == 0 && x > 0) { //check for empty space preceeding first character of word if not on edge if (grid[x - 1][y].targetChar != EMPTYCHAR) { //adjacent letter collision fitScore = 0; break; } } else if (i == word.length && x < GRID_HEIGHT) { //check for empty space after last character of word if not on edge if (grid[x+i+1][y].targetChar != EMPTYCHAR) { //adjacent letter collision fitScore = 0; break; } } if (x + i < GRID_HEIGHT) { if (grid[x + i][y].targetChar == word[i]) { //letter match - aka cross point fitScore += 1; } else if (grid[x + i][y].targetChar != EMPTYCHAR) { //letter doesn''t match and it isn''t empty so there is a collision fitScore = 0; break; } else { //verify that there aren''t letters on either side of placement if it isn''t a crosspoint if (y < GRID_WIDTH - 1) { //check right side if it isn''t on the edge if (grid[x + i][y + 1].targetChar != EMPTYCHAR) { //adjacent letter collision fitScore = 0; break; } } if (y > 0) { //check left side if it isn''t on the edge if (grid[x + i][y - 1].targetChar != EMPTYCHAR) { //adjacent letter collision fitScore = 0; break; } } } } } } else { //horizontal checking for (i = 0; i < word.length; i++) { if (i == 0 && y > 0) { //check for empty space preceeding first character of word if not on edge if (grid[x][y-1].targetChar != EMPTYCHAR) { //adjacent letter collision fitScore = 0; break; } } else if (i == word.length - 1 && y + i < GRID_WIDTH -1) { //check for empty space after last character of word if not on edge if (grid[x][y + i + 1].targetChar != EMPTYCHAR) { //adjacent letter collision fitScore = 0; break; } } if (y + i < GRID_WIDTH) { if (grid[x][y + i].targetChar == word[i]) { //letter match - aka cross point fitScore += 1; } else if (grid[x][y + i].targetChar != EMPTYCHAR) { //letter doesn''t match and it isn''t empty so there is a collision fitScore = 0; break; } else { //verify that there aren''t letters on either side of placement if it isn''t a crosspoint if (x < GRID_HEIGHT) { //check top side if it isn''t on the edge if (grid[x + 1][y + i].targetChar != EMPTYCHAR) { //adjacent letter collision fitScore = 0; break; } } if (x > 0) { //check bottom side if it isn''t on the edge if (grid[x - 1][y + i].targetChar != EMPTYCHAR) { //adjacent letter collision fitScore = 0; break; } } } } } } return fitScore; } function placeWord(word, clue, x, y, vertical) { //places a new active word on the board var wordPlaced = false; if (vertical) { if (word.length + x < GRID_HEIGHT) { for (i = 0; i < word.length; i++) { grid[x + i][y].targetChar = word[i]; } wordPlaced = true; } } else { if (word.length + y < GRID_WIDTH) { for (i = 0; i < word.length; i++) { grid[x][y + i].targetChar = word[i]; } wordPlaced = true; } } if (wordPlaced) { var currentIndex = activeWordList.length; activeWordList[currentIndex] = {}; activeWordList[currentIndex].word = word; activeWordList[currentIndex].clue = clue; activeWordList[currentIndex].x = x; activeWordList[currentIndex].y = y; activeWordList[currentIndex].vertical = vertical; if (activeWordList[currentIndex].vertical) { downCount++; activeWordList[currentIndex].number = downCount; } else { acrossCount++; activeWordList[currentIndex].number = acrossCount; } } } function isActiveWord(word) { if (activeWordList.length > 0) { for (var w = 0; w < activeWordList.length; w++) { if (word == activeWordList[w].word) { //console.log(word + '' in activeWordList''); return true; } } } return false; } this.displayGrid = function displayGrid() { var rowStr = ""; for (var x = 0; x < cols; x++) { for (var y = 0; y < rows; y++) { rowStr += "<td>" + grid[x][y].targetChar + "</td>"; } $(''#tempTable'').append("<tr>" + rowStr + "</tr>"); rowStr = ""; } console.log(''across '' + acrossCount); console.log(''down '' + downCount); } //for each word in the source array we test where it can fit on the board and then test those locations for validity against other already placed words this.generateBoard = function generateBoard(seed = 0) { var bestScoreIndex = 0; var top = 0; var fitScore = 0; var startTime; //manually place the longest word horizontally at 0,0, try others if the generated board is too weak placeWord(wordArray[seed].word, wordArray[seed].displayWord, wordArray[seed].clue, 0, 0, false); //attempt to fill the rest of the board for (var iy = 0; iy < FIT_ATTEMPTS; iy++) { //usually 2 times is enough for max fill potential for (var ix = 1; ix < wordArray.length; ix++) { if (!isActiveWord(wordArray[ix].word)) { //only add if not already in the active word list topScore = 0; bestScoreIndex = 0; suggestCoords(wordArray[ix].word); //fills coordList and coordCount coordList = shuffleArray(coordList); //adds some randomization if (coordList[0]) { for (c = 0; c < coordList.length; c++) { //get the best fit score from the list of possible valid coordinates fitScore = checkFitScore(wordArray[ix].word, coordList[c].x, coordList[c].y, coordList[c].vertical); if (fitScore > topScore) { topScore = fitScore; bestScoreIndex = c; } } } if (topScore > 1) { //only place a word if it has a fitscore of 2 or higher placeWord(wordArray[ix].word, wordArray[ix].clue, coordList[bestScoreIndex].x, coordList[bestScoreIndex].y, coordList[bestScoreIndex].vertical); } } } } if(activeWordList.length < wordArray.length/2) { //regenerate board if if less than half the words were placed seed++; generateBoard(seed); } } } function seedBoard() { gameboard = new board(GRID_WIDTH, GRID_HEIGHT); gameboard.generateBoard(); gameboard.displayGrid(); }

Aunque esta es una pregunta anterior, intentaré una respuesta basada en un trabajo similar que hice.

Hay muchos enfoques para resolver problemas de restricciones (que generalmente están en la clase de complejidad de NPC).

Esto está relacionado con la optimización combinatoria y la programación de restricciones. En este caso, las restricciones son la geometría de la cuadrícula y el requisito de que las palabras sean únicas, etc.

Los enfoques de aleatorización / recocido también pueden funcionar (aunque dentro de la configuración adecuada).

¡La simplicidad eficiente podría ser la sabiduría suprema!

Los requisitos eran para un compilador de crucigramas más o menos completo y un constructor (visual WYSIWYG).

Dejando de lado la parte constructora WYSIWYG, el esquema del compilador era este:

  1. Cargue las listas de palabras disponibles (ordenadas por longitud de palabra, es decir, 2,3, ..., 20)

  2. Encuentre las separaciones de palabras (es decir, palabras de cuadrícula) en la cuadrícula construida por el usuario (por ejemplo, palabra en x, y con longitud L, horizontal o vertical) (complejidad O (N))

  3. Calcule los puntos de intersección de las palabras de la cuadrícula (que deben rellenarse) (complejidad O (N ^ 2))

  4. Calcule las intersecciones de las palabras en las listas de palabras con las diversas letras del alfabeto utilizadas (esto permite buscar palabras coincidentes utilizando una plantilla, por ejemplo, Tesis de Sik Cambon, según lo utilizado por cwc ) (complejidad O (WL * AL))

Los pasos .3 y .4 permiten hacer esta tarea:

a. Las intersecciones de las palabras de la cuadrícula consigo mismas permiten crear una "plantilla" para tratar de encontrar coincidencias en la lista de palabras asociadas de las palabras disponibles para esta palabra de cuadrícula (usando las letras de otras palabras que se cruzan con esta palabra que ya están llenas en cierta paso del algoritmo)

segundo. Las intersecciones de las palabras en una lista de palabras con el alfabeto permiten encontrar palabras coincidentes (candidatas) que coinciden con una "plantilla" determinada (por ejemplo, "A" en el 1er lugar y "B" en el 3er lugar, etc.)

Entonces, con estas estructuras de datos implementadas, el algoritmo utilizado fue algo así:

NOTA: si la grilla y la base de datos de palabras son constantes, los pasos previos solo pueden hacerse una vez.

  1. El primer paso del algoritmo es seleccionar un espacio de palabras vacío (palabra de cuadrícula) al azar y llenarlo con una palabra candidata de su lista de palabras asociada (la aleatorización permite producir diferentes soluciones en ejecuciones consecutivas del algoritmo) (complejidad O (1) u O ( N))

  2. Para cada tragamonedas de palabra todavía vacía (que tienen intersecciones con porciones de palabras ya llenas), calcule una relación de restricción (esto puede variar, tan simple es la cantidad de soluciones disponibles en ese paso) y clasifique las separaciones de palabras vacías por esta razón (complejidad O (NlogN ) o O (N))

  3. Pasa por las líneas de palabras vacías calculadas en el paso anterior y para cada una prueba varias soluciones (asegúrate de que "la consistencia del arco se retiene", es decir, la cuadrícula tiene una solución después de este paso si se usa esta palabra) y ordénalas de acuerdo con disponibilidad máxima para el siguiente paso (es decir, el próximo paso tiene una cantidad máxima de soluciones posibles si esta palabra se usa en ese momento en ese lugar, etc.) (complejidad O (N * MaxCandidatesUtilizado))

  4. Complete esa palabra (márquela como completada y vaya al paso 2)

  5. Si no se encuentra una palabra que satisfaga los criterios del paso .3 trate de dar marcha atrás a otra solución candidata de algún paso anterior (los criterios pueden variar aquí) (complejidad O (N))

  6. Si se ha encontrado una pista atrás, use la alternativa y, opcionalmente, restablezca las palabras ya rellenas que puedan necesitar restablecerse (márquelas como no rellenas nuevamente) (complejidad O (N))

  7. Si no se encuentra una pista atrás, no se puede encontrar la solución (al menos con esta configuración, semilla inicial, etc.)

  8. De lo contrario, cuando se llenan todos los lotes de palabras tiene una solución

Este algoritmo realiza un recorrido consistente al azar del árbol de soluciones del problema. Si en algún punto hay un callejón sin salida, hace un retroceso a un nodo anterior y sigue otra ruta. Hasta que se agote la solución encontrada o el número de candidatos para los distintos nodos.

La parte de consistencia asegura que una solución encontrada sea de hecho una solución y la parte aleatoria permite producir diferentes soluciones en diferentes ejecuciones y también, en promedio, tener un mejor rendimiento.

PD. todo esto (y otros) se implementaron en JavaScript puro (con procesamiento paralelo y WYSIWYG)

PS2. El algoritmo se puede paralelizar fácilmente para producir más de una solución (diferente) al mismo tiempo

Espero que esto ayude

De hecho, escribí un programa de generación de crucigramas hace unos diez años (era críptico, pero las mismas reglas se aplicaban para los crucigramas normales).

Tenía una lista de palabras (y pistas asociadas) almacenadas en un archivo ordenado por uso descendente hasta la fecha (de modo que las palabras menos utilizadas estaban en la parte superior del archivo). Una plantilla, básicamente una máscara de bits que representa el negro y los cuadrados libres, se eligió al azar de un grupo que fue proporcionado por el cliente.

Luego, para cada palabra no completa en el rompecabezas (básicamente, encuentre el primer cuadrado en blanco y vea si el que está a la derecha (a través de la palabra) o el que está debajo (palabra a la baja) también está en blanco), se realizó una búsqueda de el archivo busca la primera palabra que encaja, teniendo en cuenta las letras que ya están en esa palabra. Si no había una palabra que pudiera caber, simplemente marcó la palabra completa como incompleta y siguió adelante.

Al final habrá algunas palabras incompletas que el compilador debería completar (y agregue la palabra y una pista al archivo si lo desea). Si no se les ocurre ninguna idea, podrían editar el crucigrama manualmente para cambiar las restricciones o simplemente pedir una regeneración total.

Una vez que el archivo de palabra / pista alcanzaba un cierto tamaño (y agregaba 50-100 pistas al día para este cliente), rara vez había un caso de más de dos o tres reparaciones manuales que se tenían que hacer para cada crucigrama .

Estaba jugando con el motor generador de crucigramas, y encontré esto lo más importante:

0. !/usr/bin/python

  1. a. allwords.sort(key=len, reverse=True)

    segundo. crea un objeto / objeto similar al cursor que recorrerá la matriz para facilitar la orientación, a menos que quieras iterar por elección aleatoria más adelante.

  2. el primero, toma el primer par y colócalo de 0 a 0; almacene el primero como nuestro actual crucigrama ''líder''.

  3. mover el cursor por orden diagonal o aleatorio con mayor probabilidad diagonal a la siguiente celda vacía

  4. iterar sobre las palabras como y usar la longitud de espacio libre para definir la longitud máxima de palabra: temp=[] for w_size in range( len( w_space ), 2, -1 ) : # t for w in [ word for word in allwords if len(word) == w_size ] : # if w not in temp and putTheWord( w, w_space ) : # temp.append( w )

  5. para comparar palabras contra el espacio libre que utilicé, es decir:

    w_space=[''c'',''.'',''a'',''.'',''.'',''.''] # whereas dots are blank cells # CONVERT MULTIPLE ''.'' INTO ''.*'' FOR REGEX pattern = r''''.join( [ x.letter for x in w_space ] ) pattern = pattern.strip(''.'') +''.*'' if pattern[-1] == ''.'' else pattern prog = re.compile( pattern, re.U | re.I ) if prog.match( w ) : # if prog.match( w ).group() == w : # return True

  6. después de cada palabra utilizada con éxito, cambie de dirección. Haz un bucle mientras todas las celdas están llenas O te quedas sin palabras O por límite de iteraciones, entonces:

# CHANGE ALL WORDS LIST inexOf1stWord = allwords.index( leading_w ) allwords = allwords[:inexOf1stWord+1][:] + allwords[inexOf1stWord+1:][:]

... e iterar nuevamente crucigrama.

  1. Haga el sistema de puntaje por la facilidad de llenado, y algunos calculos de estimación. Dé el puntaje para el crucigrama actual y la elección posterior estrecha agregándolo a la lista de crucigramas hechos si el puntaje es satisfecho por su sistema de puntuación.

  2. Después de la primera sesión de iteración, vuelva a iterar desde la lista de crucigramas realizados para finalizar el trabajo.

Al usar más parámetros, la velocidad se puede mejorar por un factor enorme.

Este algoritmo crea 50 crucigramas densos de 6x9 flechas en 60 segundos. Utiliza una base de datos de palabras (con palabras + consejos) y una base de datos de juntas (con tableros preconfigurados).

1) Search for all starting cells (the ones with an arrow), store their size and directions 2) Loop through all starting cells 2.1) Search a word 2.1.1) Check if it was not already used 2.1.2) Check if it fits 2.2) Add the word to the board 3) Check if all cells were filled

¡Una base de datos de palabras más grande disminuye considerablemente el tiempo de generación y algunos tipos de tableros son más difíciles de llenar! ¡Los tableros más grandes requieren más tiempo para llenarse correctamente!

Ejemplo:

Tablero preconfigurado de 6x9:

(# significa una propina en una celda,% significa dos propinas en una celda, no se muestran las flechas)

# - # # - % # - # - - - - - - - - - # - - - - - # - - % - - # - # - - - % - - - - - % - - - - - - - - - - -

Tablero generado 6x9:

# C # # P % # O # S A T E L L I T E # N I N E S # T A % A B # A # G A S % D E N S E % W E C A T H E D R A L

Sugerencias [línea, columna]:

[1,0] SATELLITE: Used for weather forecast [5,0] CATHEDRAL: The principal church of a city [0,1] CANADA: Country on USA''s northern border [0,4] PLEASE: A polite way to ask things [0,7] OTTAWA: Canada''s capital [1,2] TIBET: Dalai Lama''s region [1,8] EASEL: A tripod used to put a painting [2,1] NINES: Dressed up to (?) [4,1] DENSE: Thick; impenetrable [3,6] GAS: Type of fuel [1,5] LS: Lori Singer, american actress [2,7] TA: Teaching assistant (abbr.) [3,1] AB: A blood type [4,3] NH: New Hampshire (abbr.) [4,5] ED: (?) Harris, american actor [4,7] WE: The first person of plural (Grammar)

Generaría dos números: Puntuación de Scrabble y Longitud. Supongamos que un puntaje bajo de Scrabble significa que es más fácil unirse (puntajes bajos = muchas letras comunes). Ordene la lista por longitud descendiendo y la puntuación Scrabble ascendente.

Luego, solo ve por la lista. Si la palabra no se cruza con una palabra existente (verifique cada palabra por su longitud y puntaje de Scrabble, respectivamente), póngala en la cola y verifique la siguiente palabra.

Enjuague y repita, y esto debería generar un crucigrama.

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

He codificado una solución 100% jQuery para este problema.

Muestra demo: http://www.earthfluent.com/crossword-puzzle-demo.html

Código fuente: https://github.com/HoldOffHunger/jquery-crossword-puzzle-generator

La intención del algoritmo que utilicé:

  1. Minimice la cantidad de cuadrados inutilizables en la cuadrícula tanto como sea posible.
  2. Tener tantas palabras entremezcladas como sea posible.
  3. Compute en un tiempo extremadamente rápido.

Describiré el algoritmo que utilicé:

  1. Agrupe las palabras juntas de acuerdo con aquellas que comparten una letra común.

  2. De estos grupos, construye conjuntos de una nueva estructura de datos ("bloques de palabras"), que es una palabra primaria (que se ejecuta a través de todas las demás palabras) y luego las otras palabras (que se ejecutan a través de la palabra primaria).

  3. Comience el crucigrama con el primero de estos bloques de palabras en la posición superior izquierda del crucigrama.

  4. Para el resto de los bloques de palabras, comenzando desde la posición más abajo a la derecha del crucigrama, mueva hacia arriba y hacia la izquierda, hasta que no haya más espacios disponibles para llenar. Si hay más columnas vacías hacia arriba que hacia la izquierda, mueve hacia arriba y viceversa.

He estado pensando en este problema. Mi sensación es que para crear un crucigrama verdaderamente denso, no puedes esperar que tu lista limitada de palabras sea suficiente. Por lo tanto, es posible que desee tomar un diccionario y colocarlo en una estructura de datos "trie". Esto le permitirá encontrar fácilmente las palabras que llenan los espacios sobrantes. En un trie, es bastante eficiente implementar un recorrido que, digamos, le da todas las palabras de la forma "c? T".

Entonces, mi pensamiento general es: crear algún tipo de enfoque de fuerza relativamente bruta, como se describe aquí para crear una cruz de baja densidad, y completar los espacios en blanco con palabras del diccionario.

Si alguien más ha adoptado este enfoque, házmelo saber.

Me gustaría obtener un índice de cada letra utilizada por cada palabra para saber posibles cruces. Entonces elegiría la palabra más grande y la usaría como base. Seleccione el siguiente grande y cruzarlo. Enjuague y repita. Es probable que sea un problema de NP.

Otra idea es crear un algoritmo genético en el que la medida de la fuerza sea la cantidad de palabras que puede poner en la cuadrícula.

La parte difícil que encuentro es cuando saber una cierta lista no se puede cruzar.

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 el libro de acertijos de un niño.

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

  1. Crea una grilla de cualquier tamaño y una lista de palabras.
  2. Mezcle la lista de palabras, y luego clasifique las palabras por el más largo al más corto.
  3. Coloque la primera y más larga palabra en la posición más a la izquierda superior, 1,1 (vertical u horizontal).
  4. Pase a la siguiente palabra, recorra cada letra de la palabra y cada celda de la cuadrícula buscando coincidencias de letra a letra.
  5. Cuando se encuentra una coincidencia, simplemente agrega esa posición a una lista de coordenadas sugeridas para esa palabra.
  6. Pasa el cursor por encima de la lista de coordenadas sugeridas y "puntúa" la colocación de palabras en función de cuántas otras palabras cruce. Las puntuaciones de 0 indican una ubicación incorrecta (adyacente a las palabras existentes) o que no se cruzaron palabras.
  7. Regrese al paso # 4 hasta que la lista de palabras se agote. Segundo pase opcional.
  8. Ahora deberíamos tener un crucigrama, pero la calidad puede ser impredecible debido a algunas de las ubicaciones aleatorias. Por lo tanto, protegemos este crucigrama 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 tiene un límite de tiempo (encuentra el mejor crucigrama en x segundos).

Al final, tienes un crucigrama decente o un acertijo de búsqueda de palabras, ya que son más o menos lo mismo. Suele funcionar bastante bien, pero avíseme si tiene alguna sugerencia de mejora. Las cuadrículas más grandes corren exponencialmente más lentamente; listas de palabras más grandes de forma lineal. Las listas de palabras más grandes también tienen una probabilidad mucho mayor de tener mejores números de colocación de palabras.

Se me ocurrió una solución que probablemente no sea la más eficiente, pero funciona bastante bien. Básicamente:

  1. Ordena todas las palabras por longitud, descendiendo.
  2. Tome la primera palabra y colóquela en el tablero.
  3. Toma la siguiente palabra.
  4. Busque entre todas las palabras que ya están en el tablero y vea si hay posibles intersecciones (letras comunes) con esta palabra.
  5. Si hay una ubicación posible para esta palabra, recorra todas las palabras que están en la pizarra y verifique si la nueva palabra interfiere.
  6. Si esta palabra no rompe el tablero, colóquelo allí y vaya al paso 3, de lo contrario, continúe buscando un lugar (paso 4).
  7. Continúe este ciclo hasta que todas las palabras estén ubicadas o no puedan colocarse.

Esto hace un crucigrama funcional, aunque a menudo bastante pobre. Hubo una serie de modificaciones que hice a la receta básica anterior para obtener un mejor resultado.

  • Al final de la generación de un crucigrama, proporciónele una puntuación basada en cuántas palabras se colocaron (cuanto más, mejor), qué tamaño tiene la pizarra (cuanto más pequeña mejor) y la relación entre la altura y el ancho (cuanto más cerca se encuentre) a 1, mejor). Genere una cantidad de crucigramas y luego compare sus puntajes 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 tienes una pequeña lista de palabras, obtendrás docenas de posibles crucigramas en 5 segundos. Un crucigrama más grande solo se puede elegir entre 5-6 posibilidades.
  • Cuando coloque una nueva palabra, en lugar de ubicarla inmediatamente después de encontrar una ubicación aceptable, déle a esa palabra una puntuación basada en cuánto aumenta el tamaño de la cuadrícula y cuántas intersecciones hay (lo ideal sería que cada palabra fuera cruzado por otras 2-3 palabras). Mantenga un registro de todas las posiciones y sus puntajes y luego elija la mejor.

Here hay alguna versión Swift del generador de crucigramas basado en el código python de Bryan.

Solo compartirlo en caso de que alguien lo necesite.