Available nodes

 Générateur de mots croisés

Les mots croisés (faut-il le rappeler ?), sont une forme de casse-tête constituée d'une grille rectangulaire ou carrée, remplie de cases noires ou blanches, chaque case blanche contenant exactement une lettre de l'alphabet [a-z], de manière à ce que dans chaque ligne et colonne, les suites de lettres forment des mots d'un dictionnaire.
Le but de ce projet est de construire un générateur de grilles de mots croisés, en utilisant les mots d'un dictionnaire donné. Il est ainsi envisageable de faire des mots croisés avec seulement des mots de 3 lettres, ou avec des mots d'une langue donnée. Noter que, dans le cadre de ce projet, il n'est pas demandé de construire les définitions associées (même si il peut être intéressant de trouver des solutions à ce problème particulier).
Le challenge posé par ce sujet consiste à construire une grille de mots croisés comportant le moins de cases noires possibles. Les résultats des algorithmes seront évalués sur des grilles carrées de taille 3 à 12, voire plus selon les performances des algorithmes.
Le sujet consiste à réaliser les phases suivantes :
  • Afficher une grille de mots croisés

    A cet effet, il sera nécessaire de définir un format texte de représentation des grilles, de charger les fichiers représentant ces grilles et de pouvoir les afficher à l'écran en utilisant une représentation quelconque.
  • Charger un dictionnaire existant

    Pour pouvoir construire une grille, il est nécessaire de partir d'un dictionnaire de mots existant. Par exemple, la commande aspell -l fr dump master permet d'obtenir une liste de mots de la langue française. Il faudra charger un fichier de mots existant (par exemple au format texte, un mot par ligne), et pouvoir effectuer des recherches à l'intérieur (par exemple les mots t.t., où le caractère . peut représenter n'importe quelle lettre).
  • Générer une grille de mots croisés

    Pour une taille donnée nxm, il doit être possible de générer une grille de cette taille qui soit une grille de mots croisés au sens de la définition ci-dessus. Il est demandé de créer des grilles avec le moins de cases noires possibles, mais il est possible de commencer avec des mots croisés plus ou moins arborescents (comme par exemple le british-style grid de Wikipedia).
L'affichage des mots croisés est censé représenter une partie mineure du sujet. Il est donc demandé de travailler surtout sur l'algorithme de génération de grilles. Néanmoins, il semble logique de faire un effort pour exporter les mots croisés dans un format graphique correct, en utilisant LaTeX et une bibliothèque de dessin comme pstricks ou tikz.

 Contact

Pour toute information complémentaire, contacter : David Renault présent aux séances d'encadrement le vendredi après-midi.