Discussion :

[Rano_intelo]

Bonjour,
Je cherche un algorithme standard de génération de grille qui soit un peu rapide et qui s'adapte avec les grilles géantes ,j'ai fait beaucoup de recherches mais je fini toujours par trouver des algorithmes qui passe 2 min pour générer une toute petite grille
-La deuxième question : connaissez vous un bon dictionnaire de mots croisés à télécharger (une liste de mots ou une bdd).
Merci pour votre aide !

[kolodz]

Ton algorithme doit probablement passer son temps à chercher les mots qui contiennent une certaine lettre ou deux lettre séparé à X d’intervalle.
Ceci peut-être indexé pour une très grande partie. Ce qui fait que ton algorithme n'aura plus qu'à prendre les mots qui correspondent au lieu de rechercher dans la liste.
Personnellement, si je devais faire un index par rapport à deux lettres à une distance X, j’utiliserai un index de ce type :

Code Java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
// Premier index le numéro de la lettre à rechercher en position A
// Second index la distance entre la première lettre et la seconde
// Troisième index le numéro de la lettre rechercher en position A+X
// Quatrième index la liste des mot matchant (tableau initialisé vide à remplacer)
String[][][][] indexMot= new String[26][10][26][0];

L'index risque d'être volumineux par rapport au nombre de mot que tu as. Et il faudrait probablement un second index du même style pour indiqué la position A dans le mot.
Pour avoir tester ce genre d'indexation par rapport à une résolution, qui itérè sur les éléments, tu as un facteur 100.

Pour être plus précis, il faudrait voir l’algorithme que tu utilise.

Cordialement,
Patrick Kolodziejczyk.

[Flodelarab]

Bonjour,

connaissez vous un bon dictionnaire de mots croisés à télécharger (une liste de mots ou une bdd)

Un bon mot-croisés est un mot-croisés dont les définitions sont astucieuses. C'est à toi de les fabriquer.
Sinon, il traine des dictionnaires sur internet, dont certains protégés, qui doivent te suffirent.

Pour l'algorithme, je fabriquerais un arbre dont la racine est le début du mot, les premières branches la première lettre possible, les secondes branches la deuxième lettre possible, etc... en indiquant pour chaque noeud la quantité.
Ainsi pour construire la grille, je tirerais les mots au sort. 1 coup horizontal, 1 coup vertical, 1 coup horizontal, 1 coup vertical, etc.

@kolodz: il ne cherche pas à résoudre un mot-croisés mais à fabriquer un mot-croisés.

[kolodz]

@kolodz: il ne cherche pas à résoudre un mot-croisés mais à fabriquer un mot-croisés.

La fabrication doit nécessairement prendre en compte le croisement des mots. Une fois un mot placé, il est nécessaire de le prendre en compte pour ajouter un nouveau mot(avec sa définition).
Or une fois que on a placé plusieurs mots en horizontale, si on veut placer un mot en vertical par-dessus :

Il est nécessaire que celui-ci match au niveau des deux intersections.

C'est là que l'algorithme va faire le plus de calcul. En l'endroit où il va décidé du mot qu'il va utiliser par rapport au mot qu'il peut utiliser. Il faut donc faire un parcours sur l'ensemble des mots pour savoir ceux qui sont valide. Ce qui prendre beaucoup de temps. Sauf, si tu as un index pré-existant qui te donne la réponse directement.

D'ailleurs plus, le mots-croisés est dense au niveau des croisements, plus les contraintes sont fortes. Après, par rapport à l'algorithme en lui-même, il me semble qu'il faut placer les mot long en premier, car ceux-ci crée plus de contraintes et sont plus rare. Mais, cela ne change pas qu'il te sera nécessaire d'avoir une indexation/optimisation quelconque.

Après, il est possible de donnée des contraintes de constructions à l'algorithme pour que celui-ci n'autorise pas l'ajout d'un mot contenant certaines lettres (ou suite de lettre) là où il est sensé avoir une intersection. Va trouver un mot en "kr" par exemple. (Pas besoin de parcourir le dictionnaire pour savoir que c'est (trop) rare.)

Cordialement,
Patrick Kolodziejczyk.

[Flodelarab]

L'expression qui m'a arrêté est "deux lettres à une distance X". Il n'y a aucune raison d'avoir des genres de regex. Car tu n'auras jamais B__R avec le milieu à compléter.

Quand aux mots commençant par KR, l'arbre que je proposais donne instantanément la réponse.

[ol9245]

Un début dans cet article : http://lestourtereaux.free.fr/papers/data/grilles.pdf