Algorithme de solution Casse-tête

Version imprimable

1 pièce(s) jointe(s)

Bonjour, voici un petit de casse-tete extrêmement basique ébauché avec tkinter pour m’entraîner un peu à la programmation.
( Je sais que le code est loin d'être optimum ^^ c'est une ébauche rapide pour avoir un support...)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
 
 
import random as rd
import numpy as np
import tkinter as tk
 
 
 
def remplissage(liste,tableau,valeur,couleurs):
    l = []
    n = 0
    for i in liste:
        tableau[i] = 0
 
        if i[0] > 0 :
            a = tableau[i[0]-1,i[1]]
            if a == valeur:
                tableau[i[0]-1,i[1]] = 0
                l.append((i[0]-1,i[1]))
                n += 1
            else:
                if a > 0 and a < 5:
                    couleurs[a].append( (i[0]-1,i[1]) )
 
 
 
        if i[0] < 6 :
            c = tableau[i[0]+1,i[1]]
            if c == valeur:
                tableau[i[0]+1,i[1]] = 0
                l.append((i[0]+1,i[1]))
                n += 1
            else:
                if c > 0 and c < 5:
                    couleurs[c].append( (i[0]+1,i[1]) )
 
 
 
        if i[1] > 0 :
            b = tableau[i[0],i[1]-1]
            if b == valeur:
                tableau[i[0],i[1]-1] = 0
                l.append((i[0],i[1]-1))
                n += 1
            else:
                if b > 0 and b < 5:
                    couleurs[b].append( (i[0],i[1]-1) )
 
 
 
        if i[1] < 6 :
            d = tableau[i[0],i[1]+1]
            if d == valeur:
                tableau[i[0],i[1]+1] = 0
                l.append((i[0],i[1]+1))
                n += 1
            else:
                if d > 0 and d < 5:
                    couleurs[d].append( (i[0],i[1]+1) )
 
 
    if n == 0:
        l = []
 
    return l
 
def remplir_bleu():
    cc = set(couleurs[1])
    while len(cc) > 0:
        cc = remplissage(cc,tableau,1,couleurs)
 
    for l,ligne in enumerate(tableau):
        for c,item in enumerate(ligne):
            can.create_rectangle(c*32,l*32,c*32+30,l*32+30,fill=col[item])
            can.update()
    if np.sum(tableau) == 0:
        for c in fen.winfo_children():
            c.destroy()
 
 
 
def remplir_vert():
    cc = set(couleurs[2])
    while len(cc) > 0:
        cc = remplissage(cc,tableau,2,couleurs)
 
    for l,ligne in enumerate(tableau):
        for c,item in enumerate(ligne):
            can.create_rectangle(c*32,l*32,c*32+30,l*32+30,fill=col[item])
            can.update()
    if np.sum(tableau) == 0:
        for c in fen.winfo_children():
            c.destroy()
 
def remplir_rouge():
 
    cc = set(couleurs[3])
    while len(cc) > 0:
        cc = remplissage(cc,tableau,3,couleurs)
 
    for l,ligne in enumerate(tableau):
        for c,item in enumerate(ligne):
            can.create_rectangle(c*32,l*32,c*32+30,l*32+30,fill=col[item])
            can.update()
    if np.sum(tableau) == 0:
        for c in fen.winfo_children():
            c.destroy()
 
def remplir_orange():    
    cc = set(couleurs[4])
    while len(cc) > 0:
        cc = remplissage(cc,tableau,4,couleurs)
 
    for l,ligne in enumerate(tableau):
        for c,item in enumerate(ligne):
            can.create_rectangle(c*32,l*32,c*32+30,l*32+30,fill=col[item])
            can.update()
    if np.sum(tableau) == 0:
        for c in fen.winfo_children():
            c.destroy()
        tk.Label(fen,text="C'est gagné !!!").pack()
 
### Initialisation ###############################
ll = []
tableau = np.zeros((7,7), dtype=int)
couleurs = [[],[],[],[],[]]
for l,ligne in enumerate(tableau):
    for c,item in enumerate(ligne):
        v = rd.randint(1,4)
        tableau[l,c] = v
 
print(tableau)
print()
 
x = rd.randint(0,6)
y = rd.randint(0,6)
 
 
valeur = tableau[y,x]
ll.append((y,x))
 
while len(ll) > 0:
    ll = remplissage(ll,tableau,valeur,couleurs)
 
###################################################
 
col = {0:"black",1:"blue",2:"green",3:"red",4:"orange"}
fen = tk.Tk()
 
can = tk.Canvas(fen,bg="black",height=7*32,width=7*32)
 
b1 = tk.Button(fen,text="     ",bg="blue", command=remplir_bleu).grid(row = 1, column = 0)
b2 = tk.Button(fen,text="     ",bg="green", command=remplir_vert).grid(row = 1, column = 1)
b3 = tk.Button(fen,text="     ",bg="red", command=remplir_rouge).grid(row = 1, column = 2)
b4 = tk.Button(fen,text="     ",bg="orange", command=remplir_orange).grid(row = 1, column = 3)
 
for l,ligne in enumerate(tableau):
    for c,item in enumerate(ligne):
        can.create_rectangle(c*32,l*32,c*32+30,l*32+30,fill=col[item])
 
can.grid(row = 0, column = 0, columnspan = 4)    
 
fen.mainloop()

Pièce jointe 382870

je voudrais y intégrer un algorithme qui indique la meilleur combinaison de couleurs pour vider le plateau en un minimum de coups afin d'afficher un objectif a atteindre au joueur du genre un malus si il dépasse un certain nombre de coups, et un bonus si la meilleur solution est trouvée.

Pour ceux qui ne connaissent pas ce type de jeu, testez code et cliquez sur les boutons de couleur ^^

Merci pour les piste que vous pourrez me donner

24/05/2018, 07h25
BufferBob

salut,

en clair le principe du jeu est à chaque coup d'enlever tous les cubes de la couleur choisie qui sont en contact avec du vide
du coup une solution va se symboliser par 121323142 ou 4134341, une suite de chiffres compris entre 1 et 4 (si l'on a 4 couleurs), la question étant de trouver la séquence la plus courte

Citation:

Envoyé par narcibrook21

je voudrais y intégrer un algorithme qui indique la meilleur combinaison de couleurs pour vider le plateau en un minimum de coups

j'imagine qu'un arbre de recherche serait une bonne idée, à chaque tour on évalue chacune des couleurs qui donnent autant de branches, et sur les feuilles on stocke le nombre de cases non-vides restantes, la première feuille arrivée à 0 on a plus qu'à remonter jusqu'au tronc pour avoir la solution, en clair on teste toutes les possibilités en même temps au fur et à mesure qu'elles existent, reste à voir comment l'implémenter...
24/05/2018, 09h05
Flodelarab

Bonjour :coucou:

Citation:

du coup une solution va se symboliser par 121323142 ou 4134341, une suite de chiffres compris entre 1 et 4 (si l'on a 4 couleurs), la question étant de trouver la séquence la plus courte

:oops: Même en base 3. Pas 4. (Ni 5)

Pas 5 car le 0 est absent.
Pas 4 car le jeu interdit généralement de choisir 2 fois la même couleur.
Donc 1 choix parmi 3.
La solution sera donc de la forme 021201002100121002111111212121 (Dans l'exemple initial).
Un nombre en base 3.
24/05/2018, 10h41
tbc92

L'idée de jeu est originale, bravo.

Sur la partie algorithme, on a un arbre, et il faut parcourir toutes les branches de l'arbre... Avec probablement des astuces pour éliminer plus ou moins vite les branches les moins prometteuses.
Par exemple, si les scénarios 1231 et 231 nous emmènent à la même position, alors on peut rejeter le scénario 1231.
Idem, si les scénarions 1231 et 1321 nous emmènent à la même position, inutile d'explorer à fond ces 2 scénarios.
24/05/2018, 10h59
dinobogan

Ce puzzle est généralement appelé "flood fill". Il y a très longtemps, j'avais réfléchi à un solveur.
Voici une première approche : pour chaque coup, choisir la couleur qui retire le plus de case.
Une seconde approche : donner une valeur à chaque case en partant de la zone noire. Plus la case est éloignée de la zone noire, plus sa valeur augmente. Ensuite, associer cela avec la première approche : pour chaque coup, on additionne toutes les valeurs des cases noircies et on prend le meilleur coup.
Une troisième approche : calculer la distance maximale à parcourir entre la zone noire et la case la plus loin. C'est cette case qui va déterminer le nombre de coups minimum en dessous duquel il n'est pas possible de descendre. Alors jouer les couleurs dans l'ordre pour atteindre cette case la plus éloignée. L'identité de la case la plus éloignée doit être recalculée à chaque tour.
24/05/2018, 21h44
narcibrook21

Merci pour vos éclaircissements a tous ^^ dès que j'ai un moment je vais faire des recherches sur les "Arbre de recherche" , un concept que je ne connais pas et qui je le sens va bien me servir.
Dès que j'ai un truc potable ou qui en tout cas fait le boulot je poste la solution ^^
Ensuite si un amateur veux retravailler mon code et implémenter sa solution ... :mrgreen: