Algorithme pour générer un mot croisé

Avec une liste de mots, comment feriez-vous pour les ranger dans une grid de mots croisés?

Cela ne devrait pas être comme un jeu de mots croisés “correct” qui est symésortingque ou quelque chose du genre: il suffit simplement de générer une position de départ et une direction pour chaque mot.

Y aurait-il des exemples Java disponibles?

Je suis venu avec une solution qui n’est probablement pas la plus efficace, mais elle fonctionne assez bien. Fondamentalement:

  1. Trier tous les mots par longueur, en descendant.
  2. Prenez le premier mot et placez-le sur le tableau.
  3. Prenez le mot suivant
  4. Cherchez parmi tous les mots déjà présents sur le tableau et voyez s’il y a des intersections possibles (des lettres communes) avec ce mot.
  5. S’il y a un emplacement possible pour ce mot, parcourez tous les mots qui se trouvent sur le tableau et vérifiez si le nouveau mot interfère.
  6. Si ce mot ne casse pas le tableau, placez-le là et passez à l’étape 3, sinon continuez à chercher une place (étape 4).
  7. Continuez cette boucle jusqu’à ce que tous les mots soient placés ou ne peuvent pas être placés.

Cela rend les mots croisés fonctionnels, mais souvent assez pauvres. J’ai apporté un certain nombre de modifications à la recette de base ci-dessus pour obtenir un meilleur résultat.

  • À la fin de la génération des mots croisés, atsortingbuez-lui un score basé sur le nombre de mots placés (le meilleur possible), la taille du tableau (le plus petit est le mieux) et le rapport hauteur / largeur à 1 le mieux). Générez un certain nombre de mots croisés, puis comparez leurs scores et choisissez le meilleur.
    • Au lieu d’exécuter un nombre arbitraire d’itérations, j’ai décidé de créer autant de mots croisés que possible dans un laps de temps arbitraire. Si vous n’avez qu’une petite liste de mots, vous obtiendrez des dizaines de mots croisés possibles en 5 secondes. Un mot croisé plus grand ne peut être choisi que parmi 5-6 possibilités.
  • Lorsque vous placez un nouveau mot, au lieu de le placer immédiatement au moment de trouver un emplacement acceptable, atsortingbuez à ce mot une note basée sur la taille de la grid et le nombre d’intersections (idéalement, chaque mot doit être traversé par 2-3 autres mots). Gardez une trace de toutes les positions et de leurs scores, puis choisissez le meilleur.

Je viens de rédiger moi-même récemment en Python. Vous pouvez le trouver ici: http://bryanhelmig.com/python-crossword-puzzle-generator/ . Il ne crée pas les mots croisés de style NYT denses, mais le style de mots croisés que vous pourriez trouver dans un livre de puzzle pour enfants.

Contrairement à quelques algorithmes que j’ai trouvés là et qui implémentaient une méthode aléatoire de force brute pour placer des mots comme quelques-uns l’ont suggéré, j’ai essayé d’implémenter une approche brute-force légèrement plus intelligente au placement de mots. Voici mon processus:

  1. Créez une grid de toute taille et liste de mots.
  2. Mélangez la liste de mots, puis sortingez les mots du plus long au plus court.
  3. Placez le premier et le plus long mot en haut à gauche, 1,1 (vertical ou horizontal).
  4. Passez au mot suivant, faites une boucle sur chaque lettre du mot et chaque cellule de la grid recherche des correspondances de lettre à lettre.
  5. Lorsqu’une correspondance est trouvée, ajoutez simplement cette position à une liste de coordonnées suggérée pour ce mot.
  6. Bouclez la liste de coordonnées suggérée et marquez le placement des mots en fonction du nombre de mots croisés. Les scores de 0 indiquent soit un mauvais emplacement (à côté des mots existants) soit l’absence de croix de mots.
  7. Retour à l’étape 4 jusqu’à ce que la liste de mots soit épuisée. Deuxième passage facultatif.
  8. Nous devrions maintenant avoir des mots croisés, mais la qualité peut être très difficile en raison de certains emplacements aléatoires. Donc, nous tamponnons ces mots croisés et revenons à l’étape # 2. Si le mot croisé suivant contient plus de mots, il remplace les mots croisés dans le tampon. Ceci est limité dans le temps (trouvez les meilleurs mots croisés en x secondes).

À la fin, vous avez un puzzle de mots croisés ou de recherche de mots décent, car ils sont à peu près les mêmes. Cela a tendance à fonctionner plutôt bien, mais laissez-moi savoir si vous avez des suggestions d’amélioration. Les grandes grids sont exponentiellement plus lentes; plus grandes listes de mots linéairement. Les listes de mots plus grandes ont également beaucoup plus de chance d’obtenir de meilleurs nombres de mots.

J’ai en fait écrit un programme de génération de mots croisés il y a une dizaine d’années (c’était cryptique mais les mêmes règles s’appliquaient aux mots croisés normaux).

Il contenait une liste de mots (et d’indices associés) stockés dans un fichier sortingé par utilisation décroissante à ce jour (de sorte que les mots moins utilisés se trouvaient en haut du fichier). Un modèle, essentiellement un masque de bits représentant les carrés noirs et libres, a été choisi au hasard dans un pool fourni par le client.

Ensuite, pour chaque mot non complet du puzzle (essentiellement trouver le premier carré vide et voir si celui à droite (à travers le mot) ou celui en dessous (en bas) est également vide), une recherche a été faite de le fichier à la recherche du premier mot correspondant, en tenant compte des lettres déjà présentes dans ce mot. S’il n’y avait pas de mot qui pourrait convenir, vous avez simplement marqué le mot entier comme incomplet et vous êtes passé à autre chose.

A la fin, il y aurait des mots incomplets que le compilateur devrait remplir (et append le mot et un indice au fichier si désiré). S’ils ne pouvaient pas trouver d’idées, ils pourraient modifier les mots croisés manuellement pour modifier les contraintes ou simplement demander une régénération totale.

Une fois que le fichier mot / indice a atteint une certaine taille (et qu’il ajoutait 50 à 100 indices par jour pour ce client), il y avait rarement plus de deux ou trois corrections manuelles à faire pour chaque mot croisé. .

Cet algorithme crée 50 mots croisés de flèche dense 6×9 en 60 secondes. Il utilise une firebase database de mots (avec word + tips) et une firebase database de cartes (avec des cartes pré-configurées).

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 

Une firebase database de mots plus volumineuse réduit considérablement le temps de génération et certains types de cartes sont plus difficiles à remplir! Les grandes planches nécessitent plus de temps pour être remplies correctement!


Exemple:

Carte 6×9 pré-configurée:

(# signifie une pointe dans une cellule,% signifie deux pointes dans une cellule, les flèches ne sont pas affichées)

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

Tableau 6×9 généré:

 # C # # P % # O # SATELLITE # NINES # TA % AB # A # GAS % DENSE % WECATHEDRAL 

Astuces [ligne, colonne]:

 [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 sortingpod 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) 

Pourquoi ne pas simplement utiliser une approche probabiliste aléatoire pour commencer. Commencez avec un mot, puis choisissez un mot au hasard et essayez de l’adapter à l’état actuel du puzzle sans casser les contraintes de taille, etc. Si vous échouez, recommencez tout.

Vous serez surpris de la fréquence avec laquelle une approche Monte Carlo fonctionne comme cela.

Bien qu’il s’agisse d’une question plus ancienne, tentera une réponse basée sur un travail similaire que j’ai effectué.

Il existe de nombreuses approches pour résoudre les problèmes de contraintes (qui sont généralement en classe de complexité NPC).

Ceci est lié à l’optimisation combinatoire et à la programmation par contraintes. Dans ce cas, les contraintes sont la géomésortinge de la grid et l’exigence que les mots soient uniques, etc.

Les approches de randomisation / recuit peuvent également fonctionner (bien que dans les parameters appropriés).

La simplicité efficace pourrait bien être la sagesse ultime!

Les exigences concernaient un compilateur de mots croisés plus complet et un générateur (visuel WYSIWYG).

Laissant de côté la partie constructeur WYSIWYG, la description du compilateur était la suivante:

  1. Charger les listes de mots disponibles (sortingées par longueur de mot, c.-à-d. 2,3, .., 20)

  2. Recherchez les mots (par exemple les mots de la grid) sur la grid construite par l’utilisateur (par exemple, mot à x, y de longueur L, horizontal ou vertical) (complexité O (N))

  3. Calculer les points d’intersection des mots de la grid (à remplir) (complexité O (N ^ 2))

  4. Calculer les intersections des mots dans les listes de mots avec les différentes lettres de l’alphabet utilisé (cela permet de rechercher des mots correspondants en utilisant un modèle, par exemple la thèse de Sik Cambon utilisée par cwc ) (complexité O (WL * AL))

Les étapes .3 et .4 permettent d’effectuer cette tâche:

une. Les intersections des mots de la grid avec eux-mêmes permettent de créer un “modèle” pour essayer de trouver des correspondances dans la liste de mots associée des mots disponibles pour ce mot de grid (en utilisant les lettres d’autres mots croisés avec ce mot qui sont déjà remplis étape de l’algorithme)

b. Les intersections des mots d’une liste de mots avec l’alphabet permettent de trouver des mots correspondants (candidats) correspondant à un “modèle” donné (par exemple “A” en 1ère place et “B” en 3ème place etc.)

Donc, avec ces structures de données implémentées, l’algorithme utilisé était comme ceci:

REMARQUE: si la grid et la firebase database de mots sont constantes, les étapes précédentes peuvent être effectuées une seule fois.

  1. La première étape de l’algorithme consiste à sélectionner un bloc de mots vide (mot de grid) au hasard et à le remplir avec un mot candidat de sa liste de mots associée (la randomisation permet de produire différents solutons dans des exécutions consécutives de l’algorithme) (complexité O (1) ou O N))

  2. Pour chaque intervalle de mots encore vide (qui a des intersections avec des lignes de mots déjà remplies), calculez un rapport de contrainte (cela peut varier, simple est le nombre de solutions disponibles à cette étape) et sortingez les mots vides par ce rapport (complexité O (NlogN ) ou O (N))

  3. Bouclez à travers les lignes de mots vides calculées à l’étape précédente et essayez pour chacune un certain nombre de solutions de cancdidate (en veillant à ce que la cohérence de l’arc soit conservée). disponibilité maximale pour la prochaine étape (c.-à-d. la prochaine étape a un maximum de solutions possibles si ce mot est utilisé à ce moment là, etc.) (complexité O (N * MaxCandidatesUsed))

  4. Remplissez ce mot (marquez-le comme rempli et passez à l’étape 2)

  5. Si aucun mot trouvé ne satisfait aux critères de l’étape .3, essayez de revenir sur une autre solution candidate d’une étape précédente (les critères peuvent varier ici) (complexité O (N))

  6. Si le backtrack est détecté, utilisez l’alternative et réinitialisez éventuellement les mots déjà remplis qui pourraient nécessiter une réinitialisation (marquez-les comme non remplis) (complexité O (N))

  7. Si aucun backtrack n’a été trouvé, la solution nulle peut être trouvée (au moins avec cette configuration, graine initiale, etc.)

  8. Sinon, lorsque tous les wordlots sont remplis, vous avez une solution

Cet algorithme effectue une marche cohérente aléatoire de l’arbre de solution du problème. Si, à un moment donné, il y a une impasse, il fait un retour en arrière sur un nœud précédent et suit une autre route. Jusqu’à ce qu’une solution trouvée ou le nombre de candidats pour les différents nœuds soit épuisé.

La partie cohérence veille à ce que la solution trouvée soit effectivement une solution et la partie aléatoire permet de produire différentes solutions dans différentes exécutions et, en moyenne, d’excellentes performances.

PS tout cela (et d’autres) ont été implémentés en JavaScript pur (avec parallel processing et WYSIWYG)

PS2. L’algorithme peut être facilement parallélisé afin de produire plus d’une solution (différente) en même temps

J’espère que cela t’aides

Je générerais deux nombres: Longueur et Scrabble. Supposez qu’un score Scrabble faible signifie qu’il est plus facile de se joindre (scores faibles = beaucoup de lettres communes). Trier la liste en fonction de la longueur en descendant et du score Scrabble en croissant.

Ensuite, allez simplement dans la liste. Si le mot ne croise pas un mot existant (vérifiez chaque mot par sa longueur et son score Scrabble, respectivement), mettez-le dans la queue et vérifiez le mot suivant.

Rincer et répéter, et cela devrait générer des mots croisés.

Bien sûr, je suis sûr que c’est O (n!) Et que ce n’est pas la garantie de compléter les mots croisés pour vous, mais peut-être que quelqu’un peut l’améliorer.

Voici un code javascript basé sur la réponse de nickf et le code python de Bryan. Il suffit de le poster au cas où quelqu’un d’autre en aurait besoin 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 += "" + grid[x][y].targetChar + ""; } $('#tempTable').append("" + rowStr + ""); 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(); } 

Je jouais sur un moteur de génération de mots croisés, et j’ai trouvé cela le plus important:

0. !/usr/bin/python

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

    b. faire un object / object comme un curseur qui contournera la masortingce pour une orientation facile à moins que vous ne vouliez effectuer une itération par choix aléatoire plus tard.

  2. la première, prenez la première paire et placez-la de 0,0 à stocker le premier comme notre mot-clé actuel «leader».

  3. déplacer le curseur par ordre diagonal ou aléatoire avec une plus grande probabilité diagonale vers la prochaine cellule vide

  4. itérer sur les mots comme et utiliser la longueur de l’espace libre pour définir la longueur maximale des mots: 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. comparer le mot avec l’espace libre que j’ai utilisé, c’est-à-dire:

     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.ssortingp('.') +'.*' if pattern[-1] == '.' else pattern prog = re.comstack( pattern, re.U | re.I ) if prog.match( w ) : # if prog.match( w ).group() == w : # return True 
  6. après chaque mot utilisé avec succès, changez de direction. Boucle pendant que toutes les cellules sont remplies OU vous manquez de mots OU par limite d’itérations puis:

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

… et réitérer de nouveaux mots croisés.

  1. Faire le système de notation par la facilité de remplissage, et quelques calculs d’estimation. Donnez le score pour les mots croisés actuels et les choix plus étroits par la suite en l’ajoutant à la liste des mots croisés faits si le score est satisfait par votre système de notation.

  2. Après la première itération, réitérer la session à partir de la liste des mots croisés créés pour terminer le travail.

En utilisant plus de parameters, la vitesse peut être grandement améliorée.

Je voudrais obtenir un index de chaque lettre utilisée par chaque mot pour connaître les croix possibles. Ensuite, je choisirais le plus grand mot et l’utiliserais comme base. Sélectionnez le grand suivant et croisez-le. Rincer et répéter. C’est probablement un problème de NP.

Une autre idée consiste à créer un algorithme génétique dans lequel la mesure de la force correspond au nombre de mots que vous pouvez insérer dans la grid.

La partie difficile que je trouve est de savoir quand connaître une certaine liste ne peut pas être franchie.

J’ai réfléchi à ce problème. À mon avis, pour créer des mots croisés vraiment denses, vous ne pouvez pas espérer que votre liste de mots limitée suffira. Par conséquent, vous pouvez choisir un dictionnaire et le placer dans une structure de données “sortinge”. Cela vous permettra de trouver facilement des mots qui remplissent les espaces restants. Dans un sortinge, il est assez efficace de mettre en œuvre un parcours qui, par exemple, vous donne tous les mots de la forme “c? T”.

Donc, ma pensée générale est la suivante: créer une sorte d’approche de force relativement brutale, comme celle décrite ici pour créer un croisement de faible densité, et remplir les espaces avec des mots de dictionnaire.

Si quelqu’un d’autre a adopté cette approche, faites-le moi savoir.

Voici une version Swift du générateur de mots croisés basé sur le code python de Bryan.

Il suffit de le partager au cas où quelqu’un en aurait besoin.

J’ai codé une solution 100% jQuery à ce problème.

Exemple de démonstration: http://www.earthfluent.com/crossword-puzzle-demo.html

Code source: https://github.com/HoldOffHunger/jquery-crossword-puzzle-generator

L’intention de l’algorithme que j’ai utilisé:

  1. Minimiser autant que possible le nombre de carrés inutilisables dans la grid.
  2. Avoir autant de mots mélangés que possible.
  3. Calculez dans un temps extrêmement rapide.

Je vais décrire l’algorithme que j’ai utilisé:

  1. Regroupez les mots en fonction de ceux qui partagent une lettre commune.

  2. A partir de ces groupes, créez des ensembles d’une nouvelle structure de données (“blocs de mots”), qui est un mot primaire (qui parcourt tous les autres mots), puis les autres mots (qui parcourent le mot principal).

  3. Commencez les mots croisés avec le tout premier de ces blocs de mots dans la position tout en haut à gauche du mot croisé.

  4. Pour le rest des blocs de mots, en partant de la position la plus à droite du mot croisé, déplacez-vous vers le haut et la gauche jusqu’à ce qu’il n’y ait plus de créneaux à remplir. S’il y a plus de colonnes vides vers le haut que vers la gauche, déplacez-vous vers le haut et vice versa.