problème dans la mise en place de la récursivité dans un démineur

Version imprimable

Nous sommes en classe de Terminal S en spécialité ISN.
Dans notre spécialité nous devons pour le bac coder le jeu du démineur.
Nous avons réussi entièrement a créer ce démineur mais nous bloquons pour l'action du joueur sur une case vide ou une récursivité doit s'enclencher pour ouvrir a la chaîne toutes les cases vides ainsi que les chiffres autour.

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
#cette fonction s'active en cas de clique sur une case vide
#a correspond a la ligne et b a la colonne
#leur valeur varie entre 0 et 20 dans une matrice de 20x20
def case_vide(a,b):
    if a==0 or a==20 or b==0 or b==20:
        """case_vide_particuliere(a,b)"""
        #on traitera ici les cas particuliers des premieres et derniere ligne/colone
        pass
    else:
        can.create_text(b*25+15, a*25+15,
                    text=grille[a][b], fill='black',font='Arial 16')
        can.create_text((b-1)*25+15, (a-1)*25+15,
                    text=grille[a-1][b-1], fill='black',font='Arial 16')
        if grille[a-1][b-1] == 0:
            case_vide(a-1,b-1)
        else:
            pass
        can.create_text((b-1)*25+15, a*25+15,
                    text=grille[a][b-1], fill='black',font='Arial 16')
        if grille[a][b-1] == 0:
            case_vide(a,b-1)
        else:
            pass
        can.create_text((b-1)*25+15, (a+1)*25+15,
                    text=grille[a+1][b-1], fill='black',font='Arial 16')
        if grille[a+1][b-1] == 0:
            case_vide(a+1,b-1)
        else:
            pass
        can.create_text(b*25+15, (a+1)*25+15,
                    text=grille[a+1][b], fill='black',font='Arial 16')
        if grille[a+1][b] == 0:
            case_vide(a+1,b)
        else:
            pass
        can.create_text((b+1)*25+15, (a+1)*25+15,
                    text=grille[a+1][b+1], fill='black',font='Arial 16')
        if grille[a+1][b+1] == 0:
            case_vide(a+1,b+1)
        else:
            pass
        can.create_text((b+1)*25+15, a*25+15,
                    text=grille[a][b+1], fill='black',font='Arial 16')
        if grille[a][b+1] == 0:
            case_vide(a,b+1)
        else:
            pass
        can.create_text((b+1)*25+15, (a-1)*25+15,
                    text=grille[a-1][b+1], fill='black',font='Arial 16')
        if grille[a-1][b+1] == 0:
            case_vide(a-1,b+1)
        else:
            pass
        can.create_text(b*25+15, (a-1)*25+15,
                    text=grille[a-1][b], fill='black',font='Arial 16')
        if grille[a-1][b] == 0:
            case_vide(a-1,b)
        else:
            pass

Merci de l'aide que vous pourriez nous apporter

Salut,

Citation:

Envoyé par Jean-Baptiste_

Merci de l'aide que vous pourriez nous apporter

Avant de coder, il faut décrire un algorithme puis l'écrire en pseudo-code puis le traduire en Python...
Exemple de pseudo code:
Code:

1 2 3 4 5 6 7 8 9 10 11 case_vide(x, y): si (x, y) n''est pas dans la grille ou case(x, y) est découverte ou case(x, y) non vide: retour découvrir case(x, y) case_vide(x+1, y) case_vide(x, y+1) case_vide(x-1, y) case_vide(x, y - 1)
ce qui permet de faire abstraction des détails du codage.

- W

10/05/2019, 08h34
Jean-Baptiste_

C'est ce que nous avons fait et nous pensions que notre algo était bon.
Nous avons essayé plusieurs logique différente mais nous ni arrivons toujours pas.
10/05/2019, 08h47
wiztricks

Salut,

Citation:

Nous avons essayé plusieurs logique différente mais nous ni arrivons toujours pas.

Ben, vous ajoutez des "print" vous visualiser les cases visitées et vous vous assurez que çà correspond bien à ce que vous attendiez.
note: pour l'instant vous n'avez pas décrit votre algo. et votre code n'a aucune chance de fonctionner...

- W

Nous sommes arrivés a ce jour a ce code qui ne fonctionne toujours pas :

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
 
##s'active quand nous cliquons sur le canevas
#a et b sont les cases sur lesquels nous cliquons
#a=ligne
#b=colonne
def verification(a,b):
    ## On définit ce qu'il se passe lorsque le joueur fais un clic gauche
    ## sur une case
    if face[a][b] == "drapeau":
        pass
    elif grille[a][b] == 'bombe':
        echec(a,b)
        init = 0
    elif grille[a][b] == 0:
        can.create_rectangle(b*25+3, a*25+3,b*25+27, a*25+27,width=0, fill="ivory")
        if a ==0 and b==0:
            verification (a,b+1)
            verification(a+1,b+1)
            verification(a+1,b)
        if a==0 and b==19:
            verification(a,b-1)
            verification(a+1,b-1)
            verification(a+1,b)
        if a ==19 and b==0:
            verification (a-1,b)
            verification(a-1,b+1)
            verification(a,b+1)
        if a==19 and b==19:
            verification(a,b-1)
            verification(a-1,b-1)
            verification(a-1,b)
        if a==0:
            verification(a,b-1)
            verification(a+1,b-1)
            verification(a+1,b)
            verification(a+1,b+1)
            verification(a,b+1)
        if a==19:
            verification(a-1,b-1)
            verification(a,b-1)
            verification(a,b+1)
            verification(a-1,b+1)
            verification(a-1,b)
        if b==0:
            verification(a+1,b)
            verification(a+1,b+1)
            verification(a,b+1)
            verification(a-1,b+1)
            verification(a-1,b)
        if b==19:
            verification(a-1,b-1)
            verification(a,b-1)
            verification(a+1,b-1)
            verification(a+1,b)
            verification(a-1,b)
        else:
            verification(a-1,b-1)
            verification(a,b-1)
            verification(a+1,b-1)
            verification(a+1,b)
            verification(a+1,b+1)
            verification(a,b+1)
            verification(a-1,b+1)
            verification(a-1,b)
 
    else:
        coul = ['blue','green','orange','red','brown','purple','black','black']
        can.create_rectangle(b*25+3, a*25+3,
                             b*25+27, a*25+27,width=0, fill="ivory")
        can.create_text(b*25+15, a*25+15,
        text=grille[a][b], fill=coul[grille[a][b]-1], font='Arial 18')

Nous voyons ou passe notre programme puisque les cases se découvrent sur son passage. Il se contente de parcourir le premier chemin si toute les possibilités lui sont offerte ou alors le premier qu'il peut parcourir puis s’arrête subitement. Nous avons en message d'erreur python une suite d'action qui semble être celle qu'il na pas pu réaliser ainsi que la mention maximum recursive.
Les algorithmes on était fait en amont sur papier et pour nous la logique était la bonne.

14/05/2019, 14h53
wiztricks
Citation:

Envoyé par Jean-Baptiste_

Les algorithmes on était fait en amont sur papier et pour nous la logique était la bonne.

Un algorithme se termine au bout d'un nombre fini d'étapes.
Et pour pouvoir faire çà, il faut déjà garantir que toute case x, y ne sera traitée qu'une fois.
Dans le pseudo-code que je vous ai donné, çà se traduit par:
Code:

1 2 3 4 5 6 7 8 case_vide(x, y): si (x, y) n''est pas dans la grille ou case(x, y) est découverte ou case(x, y) non vide: retour découvrir case(x, y) ...
Une lecture en diagonale de votre code ne montre rien de tel: la descente récursive des appels n'est bornée que par la limite de la pile de récursion.

- W

résolution

Après quelques recherche en groupe nous avons réussi a obtenir une récursivité fonctionnelle et donc finir notre programme.
Notre programme tournais en boucle, nous avons donc ajouter "verif" dans une grille a part, celle ou se trouver les drapeau puisqu'elle était vide.

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
def verification(a,b):
    ## On définit ce qu'il se passe lorsque le joueur fais un clic gauche
    ## sur une case
    if face[a][b] == "drapeau":
        pass
    elif face[a][b] == "verif":
        pass
    elif grille[a][b] == 'bombe':
        echec(a,b)
        init = 0
    elif grille[a][b] == 0:
        can.create_rectangle(b*25+3, a*25+3,b*25+27, a*25+27,width=0, fill="ivory")
        face[a][b] = "verif"
        if a ==0 and b==0:
            verification (a,b+1)
            verification(a+1,b+1)
            verification(a+1,b)
        elif a==0 and b==19:
            verification(a,b-1)
            verification(a+1,b-1)
            verification(a+1,b)
 
        elif a ==19 and b==0:
            verification (a-1,b)
            verification(a-1,b+1)
            verification(a,b+1)
 
        elif a==19 and b==19:
            verification(a,b-1)
            verification(a-1,b-1)
            verification(a-1,b)
 
        elif a==0:
            verification(a,b-1)
            verification(a+1,b-1)
            verification(a+1,b)
            verification(a+1,b+1)
            verification(a,b+1)
 
        elif a==19:
            verification(a-1,b-1)
            verification(a,b-1)
            verification(a,b+1)
            verification(a-1,b+1)
            verification(a-1,b)
 
        elif b==0:
            verification(a+1,b)
            verification(a+1,b+1)
            verification(a,b+1)
            verification(a-1,b+1)
            verification(a-1,b)
 
        elif b==19:
            verification(a-1,b-1)
            verification(a,b-1)
            verification(a+1,b-1)
            verification(a+1,b)
            verification(a-1,b)
        else:
            verification(a-1,b-1)
            verification(a,b-1)
            verification(a+1,b-1)
            verification(a+1,b)
            verification(a+1,b+1)
            verification(a,b+1)
            verification(a-1,b+1)
            verification(a-1,b)
 
    else:
        coul = ['blue','green','orange','red','brown','purple','black','black']
        can.create_rectangle(b*25+3, a*25+3,
                             b*25+27, a*25+27,width=0, fill="ivory")
        can.create_text(b*25+15, a*25+15,
        text=grille[a][b], fill=coul[grille[a][b]-1], font='Arial 18')
        face[a][b] = "verif"