Algorithme pour générer un mot croisé

Question

É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.

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, 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.

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 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.

Answer 3

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é.

Answer 4

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)

Answer 5

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.