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

23 février 2015 · 3 min de lecture
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 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 :

Mots-mélés

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
Mots-mélés

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 :

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


#php   #algorithme   #jeu   #mots   #meles   #generateur   #sqlite  

PARTAGER VIA

 Twitter    Facebook    LinkedIn    Reddit    Email

A LIRE EGALEMENT


comments powered by Disqus