129 votes

Algorithme pour générer un mot croisé

Étant donné une liste de mots, comment allez-vous les arranger dans une grille de mots croisés ?

Il n'est pas nécessaire que ce soit comme une "vraie" grille de mots croisés qui est symétrique ou quelque chose comme ça : en gros, il suffit de sortir une position de départ et une direction pour chaque mot.

67voto

nickf Points 185423

J'ai trouvé une solution qui n'est probablement pas la plus efficace, mais qui fonctionne assez bien. En gros :

  1. Trier tous les mots par longueur, en ordre décroissant.
  2. Prenez le premier mot et placez-le au tableau.
  3. Prenez le mot suivant.
  4. Cherchez parmi tous les mots qui sont déjà 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, passez en boucle tous les mots qui sont sur le tableau et vérifiez si le nouveau mot interfère.
  6. Si ce mot ne casse pas la planche, alors placez-le là et passez à l'étape 3, sinon, continuez à chercher un endroit (étape 4).
  7. Continuez cette boucle jusqu'à ce que tous les mots soient placés ou ne puissent pas être placés.

Cela donne un mot croisé fonctionnel, mais souvent assez pauvre. 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 d'un mot croisé, donnez-lui un score basé sur le nombre de mots placés (plus il y en a, mieux c'est), la taille du tableau (plus il est petit, mieux c'est) et le rapport entre la hauteur et la largeur (plus il est proche de 1, mieux c'est). Générez un certain nombre de mots croisés, puis comparez leurs scores et choisissez le meilleur.
    • Au lieu de lancer un nombre arbitraire d'itérations, j'ai décidé de créer autant de mots croisés que possible en un temps arbitraire. Si vous avez seulement une petite liste de mots, alors vous obtiendrez des dizaines de mots croisés possibles en 5 secondes. Un mot croisé plus grand pourrait être choisi seulement parmi 5-6 possibilités.
  • Lorsque vous placez un nouveau mot, au lieu de le placer immédiatement après avoir trouvé un emplacement acceptable, donnez à cet emplacement un score basé sur la mesure dans laquelle il augmente la taille de la grille et le nombre d'intersections (idéalement, vous voudriez que chaque mot soit traversé par 2 ou 3 autres mots). Gardez une trace de toutes les positions et de leurs scores, puis choisissez la meilleure.

7 votes

Je suis en train d'écrire ce programme en ce moment même, et c'est le même algorithme que j'ai choisi. Pour un petit nombre de mots (10 ou moins), le programme n'a aucun mal à calculer toutes les solutions possibles en quelques millisecondes. L'algorithme est cependant exponentiel. La partie la plus facile est d'écrire l'algorithme de base qui calcule par force brute toutes les combinaisons possibles. La partie difficile est la douzaine de "raccourcis" dont vous avez besoin pour empêcher le programme d'essayer toutes les solutions sans issue.

2 votes

"5. ... et vérifier si le nouveau mot interfère" Comment rendre compte des situations où le nouveau mot est placé à côté d'un mot existant, qui génère du charabia aux endroits où il a des cases adjacentes ? Par exemple : LEMON ERASE Si "LE", "ER" et "MA" etc. ne sont pas des mots dans votre liste, c'est faux. D'un autre côté, rejeter catégoriquement de telles adjacences pourrait rejeter de très bonnes grilles, comme : W CITRON EFFACER NEXUS T T

4 votes

@Kaffeine, oui, je vois ce que vous voulez dire - j'ai dû écarter ces options parce que même si elles pouvaient créer de très bonnes grilles, c'est trop difficile à vérifier. (lire : je ne pouvais pas être dérangé) et il y a des chances que ce ne soit que des interférences de toute façon.

24voto

Bryan Points 343

J'ai récemment écrit le mien en Python. Vous pouvez le trouver ici : http://bryanhelmig.com/python-crossword-puzzle-generator/ . Il ne crée pas les mots croisés denses du style NYT, mais le style de mots croisés que vous pourriez trouver dans un livre de puzzle pour enfants.

Contrairement aux quelques algorithmes que j'ai trouvés et qui mettent en œuvre une méthode aléatoire de force brute pour placer les mots, comme certains l'ont suggéré, j'ai essayé de mettre en œuvre une approche de force brute légèrement plus intelligente pour placer les mots. Voici mon processus :

  1. Créez une grille d'une taille quelconque et une liste de mots.
  2. Mélangez la liste de mots, puis triez les mots du plus long au plus court.
  3. Placez le premier mot et le plus long à la position supérieure gauche, 1,1 (vertical ou horizontal).
  4. Passez au mot suivant, passez en revue chaque lettre du mot et chaque cellule de la grille à la recherche de correspondances lettre à lettre.
  5. Lorsqu'une correspondance est trouvée, il suffit d'ajouter cette position à une liste de coordonnées suggérées pour ce mot.
  6. Passez en revue la liste des coordonnées suggérées et "notez" le placement du mot en fonction du nombre d'autres mots qu'il croise. Un score de 0 indique soit un mauvais placement (adjacent à des mots existants), soit qu'il n'y a pas eu de croisement de mots.
  7. Retournez à l'étape 4 jusqu'à ce que la liste de mots soit épuisée. Deuxième passage facultatif.
  8. Nous devrions maintenant avoir un mot-croisé, mais la qualité peut être aléatoire en raison de certains des placements aléatoires. Ainsi, nous tamponnons ce mot croisé et retournons à l'étape #2. Si le mot croisé suivant a plus de mots placés sur le tableau, il remplace le mot croisé dans le tampon. Ceci est limité dans le temps (trouver le meilleur mot croisé en x secondes).

À la fin, vous avez une bonne grille de mots croisés ou de mots cachés, car ils sont à peu près identiques. Il a tendance à fonctionner plutôt bien, mais faites-moi savoir si vous avez des suggestions d'amélioration. Les grilles plus grandes fonctionnent exponentiellement plus lentement ; les listes de mots plus grandes linéairement. Les plus grandes listes de mots ont aussi beaucoup plus de chances d'obtenir de meilleurs chiffres de placement des mots.

0 votes

@Neil N : Probablement une meilleure possibilité de correspondance des lettres pour les autres mots. Ce serait peut-être aussi une approche pour trier par le nombre de lettres distinctes contenues par mot, ce qui mènera en grande partie au même résultat.

0 votes

@NeilN Python's array.sort(key=f) est stable, ce qui signifie (par exemple) que le simple fait de trier une liste de mots alphabétiques par longueur permet de conserver tous les mots de 8 lettres triés par ordre alphabétique.

4 votes

@Bryan, Le lien de votre site web ne fonctionne pas pour moi, et le domaine primaire ne fait que rediriger vers Twitter. Avez-vous un lien mis à jour vers votre code ?

20voto

paxdiablo Points 341644

J'ai en fait écrit un programme de génération de mots croisés il y a environ dix ans (c'était cryptique mais les mêmes règles s'appliqueraient pour des mots croisés normaux).

Il contenait une liste de mots (et d'indices associés) stockés dans un fichier trié par ordre décroissant d'utilisation jusqu'à la date (de sorte que les mots les moins utilisés se trouvaient en haut du fichier). Un modèle, essentiellement un masque binaire représentant les cases noires et libres, était choisi au hasard dans une réserve fournie par le client.

Ensuite, pour chaque mot incomplet du puzzle (il s'agit de trouver la première case vide et de voir si celle de droite (mot transversal) ou celle d'en dessous (mot vertical) est également vide), une recherche était effectuée dans le fichier à la recherche du premier mot qui correspondait, en tenant compte des lettres déjà présentes dans ce mot. Si aucun mot ne correspondait, il fallait simplement marquer le mot entier comme incomplet et passer à autre chose.

À la fin, il y aurait des mots non complétés que le compilateur devrait remplir (et ajouter le mot et un indice au fichier si désiré). S'ils ne parviennent pas à trouver tout idées, ils pourraient éditer les mots croisés manuellement pour modifier les contraintes ou simplement demander une re-génération totale.

Une fois que le fichier de mots/indices a atteint une certaine taille (et il ajoutait 50-100 indices par jour pour ce client), il y avait rarement plus de deux ou trois corrections manuelles qui devaient être faites pour chaque mot croisé.

0 votes

Cela ne m'aide pas vraiment dans ma situation, puisque je n'aurai qu'une liste de 6 à 12 mots. Le mien est plus un exercice d'apprentissage pour l'utilisateur qu'un puzzle de mots. +Mais je vous félicite quand même pour cet algorithme intéressant !

1 votes

Belle description. J'y ai pensé plusieurs fois dans le passé, mais je n'ai jamais essayé. Maintenant, la question magique : est-ce que ça a bien marché ? Seulement pour les puzzles épars, ou également pour les puzzles denses (comme dans l'article) ? Et de combien d'indices avez-vous besoin pour les puzzles denses ?

1 votes

@dmckee, c'était il y a un moment mais de mémoire, même les puzzles denses étaient plutôt bons. Beaucoup d'entre eux étaient terminés sans intervention, mais vous en obteniez peut-être un cinquième nécessitant l'ajout d'un ou deux mots supplémentaires. Et nous parlons de milliers de mots dans le fichier. Il est certain que le retour en arrière aurait pu aider, mais il était plus facile pour le client de rejeter une énigme avec (par exemple) 5 mots non terminés que de s'inquiéter d'essayer de trouver des indices supplémentaires. Cinq était à peu près la limite extrême que je voyais pour les mots inachevés.

17voto

thiagolr Points 2218

Cet algorithme crée 50 6x9 denses Mots croisés flèche en 60 secondes. Il utilise une base de données de mots (avec mots+informations) et une base de données de tableaux (avec des tableaux préconfigurés).

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 plus grande base de données de mots réduit considérablement le temps de génération et certains types de tableaux sont plus difficiles à remplir ! Les tableaux plus grands demandent plus de temps pour être remplis correctement !


Exemple :

Carte 6x9 pré-configurée :

(# signifie une pointe dans une cellule, % signifie deux pointes dans une cellule, flèches non montrées)

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

Planche 6x9 générée :

# 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 

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

9voto

Yogi Points 1083

Pourquoi ne pas simplement utiliser une approche probabiliste aléatoire pour commencer. Commencez par un mot, puis choisissez à plusieurs reprises un mot aléatoire et essayez de l'intégrer à l'état actuel du puzzle sans enfreindre les contraintes de taille, etc. Si vous échouez, recommencez tout simplement.

Vous serez surpris de voir combien de fois une approche Monte Carlo comme celle-ci fonctionne.

2 votes

Oui, c'est l'approche que j'ai choisie. Vous n'avez pas besoin d'essayer d'être très intelligent. Ordonnez les mots du plus long au plus court. Dans une boucle, choisissez une cellule au hasard (coordonnées de colonne et de ligne) et placez le mot sur la grille en vérifiant qu'il ne déborde pas ou qu'il n'interfère pas avec un autre mot (avant d'écrire le mot sur la grille, vérifiez que chaque cellule est vide ou que si elle contient une lettre, celle-ci correspond à la lettre que vous essayez d'écrire). Il y a d'autres logiques pour vérifier les limites et autres. Je génère par force brute un tas de grilles de plus en plus petites, puis je classe les plus petites en fonction des mots qui se croisent.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X