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
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 :
[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 commandeaspell -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 motst.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éenxm
, 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.