Algorithme pour générer une grille de mots croisés

Question

Étant donné une liste de mots, comment les arrangerais-tu dans une grille de mots croisés?

Il n'aurait pas besoin d'être comme une grille de mots croisés "classique" qui est symétrique ou quoi que ce soit : fondamentalement, juste donner une position de départ et une direction pour chaque mot.

Answer 1

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, par ordre décroissant.
2. Prendre le premier mot et le placer sur le plateau.
3. Prendre le mot suivant.
4. Rechercher tous les mots qui sont déjà sur le plateau et voir s'il y a des intersections possibles (des lettres communes) avec ce mot.
5. S'il y a un emplacement possible pour ce mot, parcourir tous les mots qui sont sur le plateau et vérifier si le nouveau mot interfère.
6. Si ce mot ne casse pas le plateau, alors le placer là et passer à l'étape 3, sinon, continuer à chercher un endroit (étape 4).
7. Continuer cette boucle jusqu'à ce que tous les mots soient placés ou ne puissent pas être placés.

Cela crée un mot croisé fonctionnel, mais souvent assez médiocre. J'ai apporté plusieurs 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 plateau (plus petit c'est mieux), et le ratio entre la hauteur et la largeur (plus proche de 1, mieux c'est). Générez plusieurs mots croisés et comparez ensuite leurs scores pour choisir 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 en une durée arbitraire. Si vous avez seulement une petite liste de mots, alors vous obtiendrez des dizaines de mots croisés possibles en 5 secondes. Un plus grand mot croisé ne sera choisi que parmi 5 à 6 possibilités.
• Lorsque vous placez un nouveau mot, au lieu de le placer immédiatement dès que vous trouvez un emplacement acceptable, donnez à cet emplacement de mot un score basé sur la manière dont il augmente la taille du plateau et le nombre d'intersections (idéalement vous voudriez que chaque mot soit croisé par 2-3 autres mots). Suivez toutes les positions et leurs scores puis choisissez le meilleur.

Answer 2

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 cruciverbistes denses de style NYT, mais le style de cruciverbistes que vous pourriez trouver dans un livre de puzzles pour enfants.

Contrairement à quelques algorithmes que j'ai trouvés là-bas et qui ont mis en œuvre une méthode de force brute aléatoire pour placer des mots comme quelques-uns l'ont suggéré, j'ai essayé de mettre en œuvre une approche de force brute légèrement plus intelligente pour le placement des mots. Voici mon processus:

1. Créer une grille de la taille souhaitée et une liste de mots.
2. Mélanger la liste de mots, puis trier les mots du plus long au plus court.
3. Placer le premier et le plus long mot à la position la plus en haut à gauche, 1,1 (verticalement ou horizontalement).
4. Passer au mot suivant, boucler sur chaque lettre du mot et chaque cellule de la grille à la recherche de correspondances lettre par lettre.
5. Lorsqu'une correspondance est trouvée, simplement ajouter cette position à une liste de coordonnées suggérée pour ce mot.
6. Parcourir la liste de coordonnées suggérée et "noter" le placement du mot en fonction du nombre d'autres mots traversés. Les scores de 0 indiquent soit un mauvais placement (à côté de mots existants) soit qu'il n'y avait pas de croisements de mots.
7. Retour à l'étape #4 jusqu'à épuisement de la liste des mots. Deuxième passage facultatif.
8. Nous devrions maintenant avoir un cruciverbiste, mais la qualité peut être aléatoire en raison de certains placements aléatoires. Nous décalons donc ce cruciverbiste et revenons à l'étape n°2. Si le prochain cruciverbiste a plus de mots placés sur la grille, il remplace le cruciverbiste dans le tampon. Cela est limité dans le temps (trouver le meilleur cruciverbiste en x secondes).

À la fin, vous avez un bon puzzle de mots croisés ou un puzzle de recherche de mots, car ils sont à peu près les mêmes. Il tend à fonctionner assez bien, mais faites-moi savoir si vous avez des suggestions d'amélioration. Les grilles plus grandes tournent de manière exponentielle plus lentement ; les listes de mots plus grandes de manière linéaire. Les listes de mots plus grandes ont également beaucoup plus de chances d'obtenir de meilleurs chiffres de placement de mots.

Answer 3

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

Il avait une liste de mots (et les indices associés) stockés dans un fichier trié par utilisation décroissante à ce jour (de sorte que les mots moins utilisés étaient en haut du fichier). Un modèle, essentiellement un masque de bits représentant les cases noires et libres, était choisi aléatoirement parmi une sélection fournie par le client.

Ensuite, pour chaque mot incomplet dans le puzzle (essentiellement trouver la première case vide et voir si celle à droite (mot transversal) ou celle en dessous (mot descendant) 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à dans ce mot. S'il n'y avait pas de mot qui pouvait correspondre, vous marquiez simplement tout le mot comme incomplet et passiez au suivant.

À la fin, il y aurait quelques mots non complets que le compilateur devrait remplir (et ajouter le mot et un indice au fichier si désiré). S'ils ne pouvaient pas avoir aucune idée, ils pouvaient modifier le mot croisé manuellement pour changer les contraintes ou simplement demander une régénération totale.

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

Answer 4

Cet algorithme crée 50 mots fléchés de 6x9 densément tissés en 60 secondes. Il utilise une base de données de mots (avec mots+conseils) et une base de données de tableaux (avec des tableaux préconfigurés).

1) Recherchez toutes les cases de départ (celles avec une flèche), stockez leur taille et leurs directions
2) Parcourez toutes les cases de départ
2.1) Recherchez un mot
2.1.1) Vérifiez s'il n'a pas déjà été utilisé
2.1.2) Vérifiez s'il convient
2.2) Ajoutez le mot au tableau
3) Vérifiez si toutes les cases ont été remplies

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 nécessitent plus de temps pour être remplis correctement!

---

Exemple:

Tableau Préconfiguré 6x9:

(# signifie un conseil dans une case, % signifie deux conseils dans une case, les flèches ne sont pas montrées)

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

Tableau de 6x9 Généré:

# 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: Utilisé pour la météo
[5,0] CATHÉDRALE: L'église principale d'une ville
[0,1] CANADA: Pays à la frontière nord des États-Unis
[0,4] S'IL VOUS PLAÎT: Une façon polie de demander des choses
[0,7] OTTAWA: Capitale du Canada
[1,2] TIBET: Région du Dalaï Lama
[1,8] CHEVALET: Un trépied utilisé pour mettre une peinture
[2,1] NINET: Habillé pour (?)
[4,1] DENSE: Épais; impénétrable
[3,6] ESSENCE: Type de carburant
[1,5] LS: Lori Singer, actrice américaine
[2,7] TA: Assistant d'enseignement (abbr.)
[3,1] AB: Un type de sang
[4,3] NH: New Hampshire (abbr.)
[4,5] ED: (?) Harris, acteur américain
[4,7] NOUS: La première personne du pluriel (Grammaire)

Answer 5

Pourquoi ne pas simplement utiliser une approche probabiliste aléatoire pour commencer. Commencez avec un mot, puis choisissez de manière répétée un mot au hasard et essayez de l'insérer dans l'état actuel du puzzle sans enfreindre les contraintes de taille, etc. Si vous échouez, recommencez simplement tout.

Vous serez surpris de voir à quel point une approche Monte Carlo comme celle-ci fonctionne souvent.