Algorithmie : générateur de mots-mêlés

Un jeu de mots mêlés, ou “word search” en anglais, consiste à trouver des mots déterminés dans une grille remplie de lettres.

Comment programmer un jeu de mots mêlés ?

Les éléments sont :

Une grille

Considerons une grille carrée, de côté variable n. Elle contient n² cases indexées dans un tableau de 0 à n²-1. Par exemple, pour une grille de côté 5, on a 25 cases, numérotées de 0 à 24 :

Chaque case contiendra une seule lettre.

Des mots

Chaque mot a les attributs suivants :

• Orientation : horizontale, verticale, diagonale
• Texte inversé ou non
• Une case de départ
• Une case de fin

Dans l’exemple ci-dessus, le mot ROYAL est inversé, il est vertical, commence dans la case 1 et se termine dans la case 21.

Une base de données de mots

Les mots seront piochés au hasard. Les sites suivants proposent des dictionnaires libres de droit :

• ELIOT
• Polyglotte
• CNRTL

Vous disposez également du Wiktionnaire où il est possible de récupérer des définitions avec le script Wikparser (et en respectant la licence Creative Commons).

NB : Le code source dont le lien se trouve en bas de page contient une base SQLite de 30 000 mots.

Algorithme

Voici ma solution :

• On part d’une case au hasard. Ceci pour éviter de placer systématiquement un mot en première case de la grille.
• On tire au hasard l’orientation et l’inversion du mot.
• On tire au hasard une longueur de mot, comprise entre 3 et n (longueur du côté de la grille).
• Selon l’orientation :
  • HORIZONTALE : Si le mot sort de la grille à droite et se retrouve placé sur 2 lignes, on le décale à gauche.
  • VERTICALE : Si le mot dépasse de la grille en bas, on le décale vers le haut.
  • DIAGONALE (haut gauche - bas droite) : Si le mot dépasse de la grille à droite, on décale à gauche. Si le mot dépasse de la grille en bas, on décale vers le haut.
  • DIAGONALE (haut droite - bas gauche) : Si le mot sort de la grille à gauche, on décale à droite. Si le mot dépasse de la grille en bas, on décale vers le haut.
• On regarde si le mot placé passe sur des cases déjà occupées et on construit un pattern SQL. Par exemple dans l’image précédente contenant le mot ROYAL. On veut dans la case 11 (contenant le Y), placer un mot horizontal de 4 caractères. Le pattern sera Y___.
• On tire un mot au hasard correspond à ce pattern.
• Si on en trouve un, on l’ajoute à la liste des mots à chercher.
• Et on recommence avec la case suivante jusqu’à ce qu’elles soient toutes parcourues.

Remarque :

• lors de la boucle sur toutes les cases de la grille, on peut en sauter pour réduire le nombre de mots à trouver.

Implémentation en PHP

Démonstration en ligne
Code source