Discussion :

[Robert le débutant]

Bonjour à tous,

Connaissez vous le jeu "RUZZLE" ?

-16 lettres
-1 Fichier dictionnaire

En l'espace de même pas 2 minutes il calcule les combinaisons possibles pour des mots de 2 lettres,3 lettres,4 lettres....etc...
En plus il donne les mots possibles....

Exemples :

Lettres : "NCSEUEAOTEIFNALR"

Réponse : 254 mots possibles

-FILANTES
-RIFLATES
-AILANTES
-FILATES
-ELIATES
.....etc....

Quelqu'un à une idée ? plusieurs posts à ce sujet mais avec 16 lettres ça bloque .....(pour mieux voir cette rapidité :http://france.pieroxy.net/blog/pages/ruzzle/fr.html )


Merci

[tatayo]

Bonjour,
Pour chaque mot, il faut stocker la liste des lettres utilisées classées par ordre alphabétique, et de même pour les lettres proposées.
Ca réduit le nombre de combinaison, vu que l'ordre des lettres ne "compte" plus.

Une deuxième optimisation consiste à mémoriser dans la boucle de recherche les combinaisons déjà recherchées. Ainsi si une lettre apparaît plusieurs fois, les combinaisons identiques ne sont cherchées qu'une seule fois.

Tatayo.

[tbc92]

Habituellement , pour les jeux de lettres, on procède ainsi :
1. Un dictionnaire 'astucieux'
Mot --> Clé
FILANTES --> AEFILNST
ELIATES --> AEEILST

Et on va inverser ce dictionnaire :
Clé --> Mot
AEFILNST --> FILANTES
AEEILST --> ELIATES

etc
Pour chaque mot, on le réécrit en classant les lettres dans l'ordre alphabétique. Eventuellement, plusieurs mots ont la même clé (les anagrammes).
Il y a 15 ou 20 ans, on trouvait dans le commerce des dictionnaires papier 'dictionnaire du scrabble', qui nous donnaient pour chaque clé, la liste des vrais-mots correspondants.

2. Ici, avec la clé de 16 lettres, on va procéder pareil
NCSEUEAOTEIFNALR --> AACEEEFILNNORSTU aux erreurs près.
Et ensuite à partir de cette clé , il sera très facile d'extraire toutes les sous-clé de 2 / 3 / 4 /// 16 lettres, et pour chaque sous-clé, aller chercher dans le dictionnaire si cette sous-clé donne 1 ou plusieurs mots.

3. On doit pouvoir optimiser un petit peu en ajoutant une condition : Si dans la sous-clé envisagée, il n'y a aucune voyelle, alors inutile d'aller lire le dictionnaire pour aller chercher ce mot.
Et on peut aussi optimiser, car il y a des lettres en doubles voire en triple ; donc même si théoriquement on a 65535 combinaisons, on peut réduire de 10 ou 20%.

On a au pire 65 535 Hlitrecherchepremier à effectuer, plus 10 000 ou 20 000 hlitsuivant
Chaque lecture dure quelques millionièmes de secondes. Le traitement devrait pouvoir se faire en quelques secondes. Mais comme Windev est relativement lent pour les calculs/boucles, il faut effectivement prévoir quelques minutes.

Edit : Vu le temps que j'ai mis à taper mon message, je me doutais qu'une autre réponse se serait intercalée !

[Robert le débutant]

Merci pour ton aide, Wouawwww ! il va me falloir traduire cela en code...et vu mon pseudo...j'espère être encore vivant pour vivre cela!!! mais vraiment merci, je n'avais pas pensé à voir les choses comme ça.

[tbc92]

C'est très exactement le problème du jeu télé "Le mot le plus long", sauf que tu as 16 lettres au lieu de 10, et tu veux tous les mots au lieu d'un seul.

Et en cherchant "algorithme jeu le mot le plus long", on trouve différentes choses.

[Robert le débutant]

Merci beaucoup, c'est vrai c'est pas mal....pour l'instant je bosse sur la solution de "tbc92" ( lol, on occupe sa retraite comme on peut !)

Re Bonjour,

J'ai crée une nouvelle rubrique dans mon fichier "DICO" avec les lettres classées.
Mais j'ai pas bien compris l'astuce des sous clés...(Non! on éclate pas de rire !)

Au plaisir de vous lire

[tbc92]

Pour rechercher les sous clé, il va falloir du code, beaucoup de lignes de code, et pas forcément simples.

A partir de la clé AACEEEFILNNORSTU , on peut extraire plein de sous-clés de 2 lettres : AA AC AE, AE à nouveau , AE une 3ème fois , AF AI AL AN AN à nouveau, AO AR AS AT et AU , etc etc etc, la dernièer sous clé de 2 lettres étant TU.
Puis plein de sous-clé de 3 lettres : AAC AAE AAE à nouveau, AAF AAI AAL etc etc ... etc, pour finir avec STU.

Pour faire ça, il y a 2 méthodes. Tu peux faire Plusieurs fonctions :
- fonction1 : Une fonction qui cherchera toutes les sous-clés de 2 lettres,
- fonction2 : Une fonction qui cherchera toutes les sous-clés de 3 lettres.
etc. et donc 15 fonctions différentes.
Toutes ces fonctions vont se ressembler. En terme de programmation , c'est la méthode la plus facile. C'est même très facile. Par contre, en terme de maintenance, c'est une galère, puisque tu as 15 fonctions quasiment identiques à maintenir.

Tu peux aussi essayer de faire une seule fonction, la même quelle que soit la taille de la cous-clé recherchée, mais je pense que c'est BEAUCOUP plus compliqué à faire.

PS : Tu as créé une rubrique dans le fichier dico, avec les lettres classées. Ok. As tu déclaré cette rubrique comme CLE .
Si tu recherches tous les mots qui ont comme clé AEILNPST , il doit te renvoyer PLIANTES, PLAINTES, PLATINES ... mais en combien de temps ? Un millième de seconde ?

PS2 : je crois qu'il y a une série de lettres qui donne une quinzaine de mots valides (une quinzaine d'anagrammes) , mais je n'arrive pas à retrouver cette série de lettres. Tu dois pouvoir la retrouver facilement.

[Robert le débutant]

Oui bien sûr la rubrique est une CLE... regarde ce lien !!! c'est impressionnant ::http://france.pieroxy.net/blog/pages/ruzzle/fr.html
je crois que je devrais créer une nouvelle rubrique avec pour chaque mot son nombre de lettre...
qu'en penses tu ?

[tbc92]

Ca va effectivement très vite, mais j'ai l'impression qu'il manque plein de mots.
Par exemple, avec AADEEIILLNPRSSTT, je m'attendais à trouver DEPLIANTES, ALINEAS, SALI, SALIE, SALIN, SALINE , ... et aucun de ces mots n'apparaît.

En fait, je pense que le nombre de lignes affichées est limité à 60 ou 70, et qu'il arrête la recherche dès qu'il a 70 réponses... Ca divise le temps de traitment de façon considérable.

Ceci étant l'algorithme proposé peut avoir des temps de réponse comparables, à condition de le développer dans un langage rapide (C par exemple).

[Robert le débutant]

En fait les mots qui manquent, c'est normal. Car "Ruzzle" impose une autre règle... C'est un jeu sur tablette et ton doigt doit suivre un chemin continu pour former le mot.
tu comprendras mieux sur ce lien https://words-solver.com/ruzzle-triche-francais/
Je vais abandonner, c'est au dessus de mon niveau de connaissance WinDev !
Dommage, je voulais impressionner ma petite fille...
Merci en tout cas pour tes réponses et pour l'intérêt que tu as apporté à mon projet.

[tatayo]

Bonjour,
Il y a peut-être une solution, en déportant le problème sur le SGBD.
Imaginons les tables suivantes:
mot:
IdMot
Mot
Taille

Lettre:
IeLettre
Lettre

Mot_Lettre
IdLettre
IdMot
Nombre

Il faut en premier enregistrer les lettres de l'alphabet dans la table des lettres.
Ensuite pour chaque mot ajouté, il faut mettre le lien avec ses lettres, en spécifiant le nombre d'occurrence.
Par exemple pour le mot tarte, il y a un lien avec a,r et e (Nombre = 1) et t (nombre = 2).

Maintenant pour chercher les solutions, une simple requête suffit:

Code sql :

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

1
2
3
4
5
6
7
8
9
10
 
select m1.mot
from mot m1,sum(ml1.nombre)
inner join mot_lettre as ml1 on ml1.idmot = mot.idmo
inner join lettre as l on l.idlettre = ml1.idlettre
inner join mot_lettre as ml2 on ml2.idlettre = l.idlettre
inner join mot as m2 on m2.idmot = ml2.idmot
where m2.mot = 'ALPHABET' and ml2.nombre >= ml1.nombre
group by m1.mot
having sum(ml1.nombre) = m1.taille

Ainsi je cherche tous les mots m1 dont les lettres sont dans le mot m2, en nombre suffisant, et pour lesquels la somme des occurrences des lettres trouvées égale la taille du mot. Le deuxième test est important, sinon la requête renvoie aussi des mots pour lesquels il manque des lettres.

Dans l'exemple, je ne trouverai pas de mot avec 2 L, ou avec un R.
La table lettre semble à première vue inutile, mais elle permet d'avoir des id de type entier, et (j'ai souvenir d'avoir lu quelque part que) les jointures sont plus rapieds avec des colonne de type entier...
Maintenant il ne reste plus qu'à voir les temps de réponse avec un gros dictionnaire

Tatayo.

[tbc92]

Effectivement, ça change nettement la règle du jeu. Du coup la piste "" remplacer FILANTES --> AEFILNST ; ELIATES --> AEEILST etc "" ne semble plus bonne.

@tatayo,
Non, ta solution ne marche pas : ""ton doigt doit suivre un chemin continu pour former le mot.""

donc si par exemple la grille contient :
ABCD
EFGH
I J KL
MNOP

Les mots CE, DE, JE, LE ou LA ne sont pas valides ; par contre MIE ou ON sont valides.

Là, il va falloir réfléchir un peu.

PS : le message serait plus à sa place dans la rubrique "Algorithme " : La question est indépendante du langage utilisé ; une fois qu'on a imaginé la solution, il faudra la traduire dans un langage ( Windev ou autre)

[tatayo]

Effectivement, je n'avais pas vu la partie "chemin", et ça complique "un peu" les choses.
Par contre il est possible de partir de la requête pour avoir une liste de mots potentiels, et ensuite pour chacun parcourir la grille pour voir si le mot est possible.
Avec un tableau à 2 dimensions c'est faisable, il faut juste s'assurer de ne pas utiliser 2 fois une même case.
Il suffit de chercher la première lettre du mot, pour chaque "départ" et pour chaque lettre suivante chercher dans les 4 cases adjacente si la lettre s'y trouve, et n'a pas été encore utilisée.
Qui s'y colle ?

Tatayo.

[Robert le débutant]

Moi, je voudrais bien....mais franchement suis pas à votre niveau !!! j'ai appris seul, j'adore faire ça....mais là je suis passablement loin derrière vous !!

"il faut juste s'assurer de ne pas utiliser 2 fois une même case."
Avec finevenement quand tu passes sur la lettre (bouton) ca marche