[VBA-E]Toutes possibilités dans une matrice

Résolu/Fermé
Morgothal Messages postés 1236 Date d'inscription jeudi 22 avril 2010 Statut Membre Dernière intervention 19 mai 2015 - 17 août 2012 à 14:28
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 - 23 août 2012 à 12:12
Bonjour à tous, j'espère que vous allez bien :)

Je fait actuellement une application Excel (qui je pense mériterait un autre support, mais c'est un challenge ;) ) pour :

-Dans une matrice 4x4, des lettres aléatoires (c'est ok)
-Chercher dans cette matrice tous les mots existant dans une liste (pouvant être apparentée à un dictionnaire) et pouvant être formés (c'est à dire que les lettres doivent se suivre dans la matrice, dans n'importe quel sens (haut, bas, droite, gauche, et diagonales) avec la limite qu'une lettre ne s'utilise qu'une fois)

Le principe auquel j'ai pensé, serait de partir d'une première lettre (mettons matrice(1,1)), et de chercher si une ligne (un mot) de la liste "commence" à correspondre au couple [matrice(1,1);(matrice(1,2)].

C'est la que je sollicite votre(vos) aide(s), auriez-vous un début de piste, un début d'algorithme pour passer sur chaque possibilité de la matrice pour des mots de 3,4,5,6 lettres ?

En écrivant ces lignes j'ai des idées qui commencent à poindre mais je suis quand même un peu bloqué...

Merci du temps que vous pourrez prendre à me répondre !

8 réponses

Morgothal Messages postés 1236 Date d'inscription jeudi 22 avril 2010 Statut Membre Dernière intervention 19 mai 2015 183
Modifié par Morgothal le 17/08/2012 à 14:52
En fait, je n'arrive pas à définir quelles cases sont possibles à partir d'une autre.
Exemple :
A partir de matrice(1,1), les seules secondes cases possibles sont matrice(1,2)(2,2)(2,1).
Et plus compliqué, à partir de matrice(2,2), les possibles sont matrice(1,2)(1,3)(2,3)(3,3)(3,2)(3,1)(2,1)...

Comment définir ceci ?
0
Morgothal Messages postés 1236 Date d'inscription jeudi 22 avril 2010 Statut Membre Dernière intervention 19 mai 2015 183
21 août 2012 à 14:03
Personne pour m'aider ? ^^'
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 2 753
21 août 2012 à 14:33
Salut Morghotal,

En général pas de réponse = pas de réponse (inexistante) ou pas de helper dispo sur le sujet ou question mal posée.

En l'occurence, pour ton cas, même si c'est presque clair, il reste tout de même des éclaircissements nécessaires...

Comment construit tu tes mots à partir de ta matrice 4x4?

Comment fais tu un mot de 6 lettres à partir d'une matrice 4x4?

Donnes nous un exemple "en dur" fait sous une feuille excel avec des couleurs par exemple...

Regarde cet EXEMPLE et dis nous si ça ressemble à ce que tu cherches à faire...
0
Morgothal Messages postés 1236 Date d'inscription jeudi 22 avril 2010 Statut Membre Dernière intervention 19 mai 2015 183
21 août 2012 à 14:46
Salut Pijaku,
Effectivement j'aurais dû me poser les bonnes questions ^^

Comment construit tu tes mots à partir de ta matrice 4x4?
En reliant les lettres dans n'importe quel sens, une lettre n'étant utilisée qu'une seule fois par mot, elle peut l'être sur un second mot.

Comment fais tu un mot de 6 lettres à partir d'une matrice 4x4?
Comme dans ton exemple, ou dans le mien.


Du coup j'avais pour idée de réunir toutes les possibilités de 3, 4, ..., 8 lettres et de chercher ensuite si ces tentatives correspondaient à un mot dans un dictionnaire Access.

Mais la navigation dans la matrice me pose bien des soucis...
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 2 753
21 août 2012 à 15:03
Sans y avoir réfléchi plus que cela, je procèderai comme ceci :
A partir de la liste des mots :
1- élimination de ceux qui comportent une des 10 lettres manquantes.
2- se taper la liste restante et voir si ça colle lettre par lettre...

Non?
0
Morgothal Messages postés 1236 Date d'inscription jeudi 22 avril 2010 Statut Membre Dernière intervention 19 mai 2015 183
21 août 2012 à 15:26
Càd que le principe est que le programme sorte tout seul la liste de mots qui peuvent être construits dans la matrice...

Il m'est venu une autre idée que je vais essayer de ce pas, c'est de filtrer le dico pour n'avoir que les mots de n lettres (par exemple 8 lettre, ce qui donne 40 807 mots), refiltrer ensuite par la première lettre (par exemple lettre1 = "a", 3 127 mots), et de chercher si les cases mitoyennes de ce "a" ont une correspondance avec les lettre2 du dico, si oui, chercher à partir de cette case, etc...

Parce qu'à la limite, une case n'a que 8 cases adjacentes au maximum, ça doit pouvoir se faire...

Je tiendrais au jus dans ce topic pour ceux que ça pourrait intéresser :)
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 2 753
21 août 2012 à 15:31
C'est tout à fait, exactement ou presque, ce que je te suggérais de faire.....

filtre aussi les mots qui contiennent des lettres absentes dans ta matrice....
Ca je peux te le faire si tu veux...
0
Morgothal Messages postés 1236 Date d'inscription jeudi 22 avril 2010 Statut Membre Dernière intervention 19 mai 2015 183
21 août 2012 à 15:34
Ah d'accord excuse moi,
2- se taper la liste restante et voir si ça colle lettre par lettre...
J'avais compris "se taper" = "lire à la main ces 3000 mots restants voir si ça colle avec la matrice"

OK pour filtrage sur mots absents, je suis en train de voir comment requêter Access via Excel, mais ça ne semble pas bien compliqué.
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 2 753
21 août 2012 à 15:49
ya pas moyen d'exporter la table contenant tes mots vers excel? Comme ça tu l'as une fois pour toutes ta liste...
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 2 753
21 août 2012 à 16:30
Un exemple plus complet :
1 procédure principale qui lance les procédures secondaires avec ou non des paramètres
2 procédures secondaires :
- ListerMots(feuille,colonne) ==> va entrer, dans une variable tableau, les mots contenus dans la feuille feuille et dans la colonne colonne
- la procédure d'effacement de mots inutiles, vue plus haut :


Option Explicit

Dim ListeMots() As String

Sub ProcedurePrincipale()
Dim NumCol As Integer, Wsh As Worksheet

'Wsh = stocke la feuille ou sont situés les mots
Set Wsh = ThisWorkbook.Worksheets("Feuil2")
'NumCol = num de la colonne de la feuille Wsh ou sont stockés les mots
NumCol = 2
'on appelle la procédure qui va lister les mots
    'situés dans la feuille et la colonne indiqués
ListerMots Wsh, NumCol

'on lance la procédure pour retirer les mots "en trop"
RetirerMotsLettresManquantes
End Sub

Sub ListerMots(Sh As Worksheet, Col As Integer)
Dim i&

Erase ListeMots
With Sh
    For i = 0 To .Columns(Col).Find("*", , , , xlByColumns, xlPrevious).Row
        ReDim Preserve ListeMots(i)
        ListeMots(i) = .Cells(i + 2, Col)
    Next
End With
End Sub

Sub RetirerMotsLettresManquantes()
Dim alphabet(25), lettresutilisees(), lettresmanquantes()
Dim ListeMotsTemp() As String, lettr As String, mot As String
Dim i&, j&, k&, test As Boolean
Dim MonDico1 As Object, MonDico2 As Object, c

'---------------------------------------- Listage des lettres manquantes dans la grille
'création d'un alphabet
For i = 0 To 25
    alphabet(i) = Chr(65 + i)
Next
'remplissage d'un tableau contenant toutes les lettres de la grille
lettresutilisees = Range("J2:M5") '-----> A Adapter J2:M5 = Matrice 4x4
'utilisation d'un objet dictionary
    '(possibilité d'utiliser ultérieurement la méthode .exists)
Set MonDico1 = CreateObject("Scripting.Dictionary")
For Each c In lettresutilisees
    MonDico1(c) = ""
Next c
Set MonDico2 = CreateObject("Scripting.Dictionary")
For Each c In alphabet
'Si la lettre de l'alphabet n'existe pas dans mondico1
'alors je la rentre dans mondico2
    If Not MonDico1.exists(c) Then MonDico2(c) = ""
Next c
'remplissage de la variable tableau des lettres manquantes
lettresmanquantes = Application.Transpose(MonDico2.keys)

'--------------------------------- Effacement des mots contenant des lettres manquantes
'ListeMots est une variable tableau dans laquelle on a entré tous les mots
'transfert de cette liste dans une liste temporaire
ListeMotsTemp = ListeMots
'on efface la liste des mots pour ne la remplir que des mots utiles
Erase ListeMots
'Boucle sur tous les mots
For i = 0 To UBound(ListeMotsTemp)
    mot = ListeMotsTemp(i)
    'Boucle Lettres manquantes
    For j = 1 To UBound(lettresmanquantes)
        lettr = lettresmanquantes(j, 1)
        'si le mot ne contient la lettre manquante alors
        If InStr(mot, lettr) = 0 Then
            'boolean true on passe à la lettre suivante
            test = True
        'par contre, si le mot contient une lettre manquante
        Else
            'boolean false
            test = False
            'on sort de la boucle des lettres manquantes
            Exit For
        End If
    Next j
    'si boolean est vrai = si le mot ne contient aucune lettre manquante
    If test Then
        'on l'entre dans la variable tableau ListeMots
        ReDim Preserve ListeMots(k)
        ListeMots(k) = ListeMotsTemp(i)
        k = k + 1
    End If
Next i
'[J7].Resize(UBound(ListeMots)) = Application.Transpose(ListeMots)
End Sub

tu dis........
0
Morgothal Messages postés 1236 Date d'inscription jeudi 22 avril 2010 Statut Membre Dernière intervention 19 mai 2015 183
21 août 2012 à 16:52
Ca marche pas mal merci ! L'objet dictionnary est décidément merveilleux.

Mais tout le jeu c'est de filtrer ce dictionnaire, parce qu'il faut que les lettres des mots dans ListeMots soient adjacentes dans lettresutilisees... Je fouille pour trouver une piste :)

Merci encore
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 2 753
21 août 2012 à 17:31
Je reviens demain avec, peut être, un exemple...
Bonne soirée.
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 2 753
22 août 2012 à 11:18
Salut,

Du nouveau?
0
Morgothal Messages postés 1236 Date d'inscription jeudi 22 avril 2010 Statut Membre Dernière intervention 19 mai 2015 183
Modifié par Morgothal le 22/08/2012 à 14:50
Salut !
J'ai adapté tout le code pour que ça fonctionne, et c'est le cas [ dans ce fichier].

J'essaye maintenant de filtrer la liste de mots restants en fonction des 2ème, 3ème lettre, mais faire tous les tests avec des IF me semble une tâche assez colossale...

Du coup on reviens à la première question...

Merci pour ton implication en tout cas :)
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 2 753
22 août 2012 à 16:00
Salut!

Normalement, si je ne m'abuse, j'ai réussi à faire ce que tu souhaites...

Bon, deux choix, soit je te donne ma solution (qui est loin d'être la meilleure et la plus simple), soit on continues cette discussion en tâtonnant...
tu dis.

Pas besoin de faire pleins de tests If-End If.
Tu définit un range en fonction de ta cellule.
Admettons. Tu trouves ta 1ère lettre en D5. Les lettres voisines sont forcément, toutes comprises entre C4 et E6. Soit dans le Range("C4:E6"), soit, puisque tu ne connais que "D5" :
Dim Plage As Range, cel As Range
Set cel = Range("D5")
Set Plage = Range(cel.Offset(-1, -1), cel.Offset(1, 1))

Ne te reste plus qu'à trouver, dans ce Range de 9 cellules, la(les)quelle(s) contien(nen)t la lettre suivante, ET n'ont pas encore été sélectionnées...
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 2 753
22 août 2012 à 16:47
non. En fait, je pensais avoir la solution, mais non...

Il faut trouver une fonction récursive qui fonctionne bien et ça... c'est côton!
0
Morgothal Messages postés 1236 Date d'inscription jeudi 22 avril 2010 Statut Membre Dernière intervention 19 mai 2015 183
Modifié par Morgothal le 22/08/2012 à 17:04
En partant de ton bout de code, j'ai trouvé un moyen d'avoir toutes les possibilités de 3 lettres dans la matrice :
Sub trois_lettres() 
Dim Plage, Plage2, matrice As Range As Range 

Set matrice = Range("D4:G7") ' A ADAPTER 

For Each cell In matrice 
    Set Plage = Range(cell.Offset(-1, -1), cell.Offset(1, 1)) 
     
    For Each cell2 In Plage 
        If cell2 <> "" Then 
            Set Plage2 = Range(cell2.Offset(-1, -1), cell2.Offset(1, 1)) 
                 
                For Each cell3 In Plage2 
                    If cell3 <> "" Then 
                        MsgBox cell & cell2 & cell3 
                    End If 
                Next 
        End If 
    Next 
Next 

End Sub
Cependant je cherche encore pour trouver comment ne pas réutiliser la lettre d'avant... Si tu as une idée je prends :)

-------------------
Cordialement,
Clément
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 2 753
23 août 2012 à 11:55
Bonjour,

Je crois être parvenu à réaliser le bouzin......

J'en ai profité pour créer un p'tit jeu sur Excel. Tu peux le trouver ICI.
Il t'appartient en partie, donc sers t'en, use le comme tu l'entends.
Attention toutefois à la licence creative commons de CCM qui t'oblige à citer l'article en référence.
Teste le pour voir si cela corresponds bien à tes attentes.
Parfois des bugs surviennent, dans le sens ou il ne trouve pas certains mots pourtant fort évidents... Je ne comprends pas pourquoi, mais le tirage suivant est bon...
J'attends volontiers ton retour.
A+
0
Morgothal Messages postés 1236 Date d'inscription jeudi 22 avril 2010 Statut Membre Dernière intervention 19 mai 2015 183
23 août 2012 à 12:05
Impressionnant !
Ce qu'il me manquait c'était la partie CellulesVoisines, qui résous bien des soucis !
Et effectivement il répond à une grande partie de mes attentes. Je pense l'adapter un tout petit peu pour fignoler, mais ça reste très léger.

Je ne pense pas enfreindre creative commons au sens où je ne pense pas ni à le diffuser ni à publier les futures modifications... Me trompe-je peut-être ?

En tout cas félicitations et merci beaucoup pour ton aide :)

A+
0
pijaku Messages postés 12263 Date d'inscription jeudi 15 mai 2008 Statut Modérateur Dernière intervention 4 janvier 2024 2 753
23 août 2012 à 12:12
La partie CellulesVoisines est une procédure récursive. Elle s'appelle elle même. C'était indispensable pour pouvoir traiter tous les cas. Ce qui m'a le plus posé problème c'est les conditions de sortie de cette procédure.............
Mais c'est vrai que cela semble fonctionner. Des petits bugs encore mais bon, ça n'est qu'un jeu dans mon cas.

En ce qui concerne la licence CCM, la seule obligation, si tu utilises l'intégralité de l'astuce, et de mettre un lien qui y mène quelque part dans ton fichier.
Comme de toutes façons, il est convenable de citer ces sources, je te recommande, si tu utilises beaucoup de code extrait d'un même endroit, de noter, en haut de module, en commentaire, le lien vers l'endroit ou tu as tout trouvé.

Bonne continuation à toi.
0