Fonction récursive en R, soucis !

**Rproblème** · 23/06/2011, 15h51

Bonjour,bonjour,

Me lançant dans la programmation d'un algo de résolution de sudoku avec R, je boue en ce moment même !

J'arrive à avoir la solution finale, ... mais seulement en arrêtant ma fonction avec un browser() et en affichant le résultat.
Seulement quand je fais continuer (ie c), la fonction me renvoie la grille de sudoku avec seulement, le premier pas de ma fonction récursive d'effectué.

Pourtant la solution finale est bien calculé dans la fonction, on peut l'afficher, je l'avais sous les yeux ! D’où mon agacement

Voici la partie recusive de mon algo :

Code :

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

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
 
 
 resolution<-function(mat,pos)
{
 
  if (pos>81){
 
    out<-list(0,0)     
    out$mat<-mat
    out$bool<-TRUE
    browser()      # ici au moment du stop, si je demande d'afficher 'mat', j'ai bien la grille de sudoku complète qui s'affiche
    return(out)
    }
  #else  {
        i=ceiling(pos/9)
        j=pos%%9
        if (j==0) {j=9}
 
        mat<-Simple(mat) #résoud toutes les solutions "simples" (ie sans double choix) de la grille de sudoku   
 
          if (mat[i,j]!=0){
            return(resolution(mat,pos+1))
            }
          #else{
            a<-CubeSol(mat)
            nbsol<-a$nb     #donne une matrice contenant le nombre de solution possible pour chaque case
            sol<-a$sol      # donne un tableau (3 dimensions) avec pour chaque case (i,j) un vecteur composé des solutions acceptables pour cette case
            if (nbsol[i,j]!=0){    
                for (k in (nbsol[i,j]:1)){     #toutes les solutions acceptables pour la case (i,j)
                  mat[i,j]=sol[i,j,k]          #remplissage de la case par la k-eme solution
                  if ((resolution(mat,pos+1))$bool==TRUE){   # si c'est OK au rang n+1 alors je renvoie TRUE
                    out<-list(0,0)
                    out$mat<-mat
                    out$bool<-TRUE
                    return(out)
                  }
                  mat[i,j]=0                   
            out<-list(0,0)
            out$mat<-mat
            out$bool<-FALSE
            return(out) 
                }
            }
 
 
          #else}
        #else}
 
 }

Des commentaires ou solution ?
Je débute avec ce langage, il se peut qu'il y ait donc de grossières erreurs...

Merci d'avance !

**Hadrien35** · 23/06/2011, 18h02

Là, comme ça, difficile de rentrer dans ton algo car je suis loin d'être un pro...
Mais juste une remarque, si ça se trouve c'est fait exprès mais bon, je te l'ai dit, je suis pas rentré dedans du tout,
c'est normal les # avant

Code :

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

#else}

?
Car R va prendre ça comme une ligne de commentaire et donc ne pas finir ta boucle de la manière prévue...

Et si ce n'est pas ça qui bloque, alors je m'excuse d'avance!

Hadrien

**Rproblème** · 23/06/2011, 18h09

Envoyé par Hadrien35

Là, comme ça, difficile de rentrer dans ton algo car je suis loin d'être un pro...
Mais juste une remarque, si ça se trouve c'est fait exprès mais bon, je te l'ai dit, je suis pas rentré dedans du tout,
c'est normal les # avant

Code :

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

#else}

?
Car R va prendre ça comme une ligne de commentaire et donc ne pas finir ta boucle de la manière prévue...

Et si ce n'est pas ça qui bloque, alors je m'excuse d'avance!

Hadrien

Oui c'est normal (fait exprès), en fait je crois que cela ne change rien car le code est lu ligne à ligne, donc commentaire ou non à priori c'est pareil.

**arm3366** · 23/06/2011, 19h49

je ne suis sur le fait que les # ne te pose pas des soucis.
Pour commencer, enleves d'abord les "else" s'ils ne sont pas utiles, ou revoies bien tes commentaires, histoire de rendre ton code plus claire

**Rproblème** · 24/06/2011, 09h56

Bonjour,

Je vous mets le code entier (pour qu'il soit possible de le tester). j'ai nettoyé les #else aussi !

Voici le code

:

Code :

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

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
164
165
166
## Le sudoku 
sudo<-matrix(c(
+ 9,0,0,1,0,0,0,0,5,
+ 0,0,5,0,9,0,2,0,1,
+ 8,0,0,0,4,0,0,0,0,
+ 0,0,0,0,8,0,0,0,0,
+ 0,0,0,7,0,0,0,0,0,
+ 0,0,0,4,2,6,0,0,9,
+ 0,5,0,8,0,0,0,0,3,
+ 2,0,0,3,0,0,0,0,6,
+ 0,0,0,2,0,0,9,0,0),
9,9)
 
Possible<-function(mat,i,j,k)               #Regarde si k est une valeur possible
{
  bool<-TRUE
      if (sum(mat[i,]==k)>0) bool<-FALSE      #check la ligne
      if (sum(mat[,j]==k)>0) bool<-FALSE      #check la colonne
    ii<-c((floor((i-1)/3)+floor((i-1)/3)*2+1):((((i-1)/3)+floor((i-1)/3)*2)+3))             #vecteur "ligne" du carré de la case (i,j)
    jj<-c((floor((j-1)/3)+floor((j-1)/3)*2+1):((((j-1)/3)+floor((j-1)/3)*2)+3)) 
      if (sum(mat[ii,jj]==k)>0) bool<-FALSE
  return(bool)
}
 
 
 
Seul<-function(mat,i,j)               #Regarde si mat[i,j] est une valeur OK
{
  bool<-TRUE
  k<-mat[i,j]
 
      if (sum(mat[i,]==k)>1) bool<-FALSE      #check la ligne
      if (sum(mat[,j]==k)>1) bool<-FALSE      #check la colonne
    ii<-c((((i-1)/3)+1+((i-1)/3)*2):((((i-1)/3)+1+((i-1)/3)*2)+2))               #vecteur "ligne" du carré de la case (i,j)
    jj<-c((((j-1)/3)+1+((j-1)/3)*2):((((j-1)/3)+1+((j-1)/3)*2)+2))               #vecteur "colonne" du carré de la case (i,j)
      if (sum(mat[ii,jj]==k)>1) bool<-FALSE   #check le "carré" de la case (i,j)
  return(bool)
}
 
 
 
Numdispo<-function(mat,i,j)
{
  dispo<-rep(0,9)
  nb<-0
 
  if (mat[i,j]==0){
    for (k in 1:9){
      if (Possible(mat,i,j,k)==TRUE) {
        nb <- nb+1
        dispo[nb]<-k
      }
    }
  }
sortie<-list(0,0)
sortie$nb<-nb
sortie$dispo<-dispo
return(sortie)
}
 
CubeSol<-function(mat)      #rempli sur chaque couche du cube (k € 1 à 9) si la sol k est possibles, 0 étant "pas de sol"
                            #rempli un carré du nombre de solution totale pour chaque case (i,j)
{
  sol<-array(0,c(9,9,9))
  nbsol<-matrix(0,9,9)
 
  for (i in 1:9) {
    for (j in 1:9) {
      a<-Numdispo(mat,i,j)
      sol[i,j,]<-a$dispo
      nbsol[i,j]<-a$nb
    }
  }
 
sortie<-list(0,0)
sortie$nb<-nbsol
sortie$sol<-sol
return(sortie)
}
 
Unique<-function(mat)     # remplace les 0 par la solution unique des cases (i,j) concernées
{                         
uni<-list(0,0)
bool<-FALSE
 
  p<-CubeSol(mat)
  first<-p$sol[,,1]
    for (i in 1:9) {
      for (j in 1:9) {
        if (p$nb[i,j]==1){
          mat[i,j]<-first[i,j]
          p<-CubeSol(mat)
          first<-p$sol[,,1]
          bool=TRUE
        }
      }
    }
uni$mat<-mat
uni$bool<-bool
return(uni)   
}
 
Simple<-function(mat)   # fait tourné le unique jusqu'a ce qu'il y ait que des solutions multilples ou que le grille soit remplie
{
bool<-TRUE
n<-sum(mat==0)
 
   while (bool==TRUE){  
      matuni<-Unique(mat)
      mat<- matuni$mat
      bool<- matuni$bool
    }
return(mat)
}      
###########################################################
##La fonction qui ne fonctionne pas correctement est ici ##
###########################################################
 
 resolution<-function(mat,pos)        # utilise le backtracking pour résoudre toutes les solutions
{
 
  if (pos>81){                        # fin de grille
    out<-list(0,0)
 
    out$mat<-mat
    out$bool<-TRUE
    browser()                         # ici au moment du stop, si je demande d'afficher 'mat', j'ai bien la grille de sudoku complète qui s'affiche
    return(out)
    }
 
    i=ceiling(pos/9)                  # donne en fct de la position la ligne de la case
    j=pos%%9                          # donne en fct de la position la colonne de la case
    if (j==0) {j=9}
 
    mat<-Simple(mat)                  #résoud toutes les solutions "simples" (ie sans double choix) de la grille de sudoku   
 
    if (mat[i,j]!=0){
     return(resolution(mat,pos+1))
    }
 
    a<-CubeSol(mat)
    nbsol<-a$nb                       #donne une matrice contenant le nombre de solution possible pour chaque case
    sol<-a$sol                        # donne un tableau (3 dimensions) avec pour chaque case (i,j) un vecteur composé des solutions acceptables pour cette case
    if (nbsol[i,j]!=0){    
      for (k in (nbsol[i,j]:1)){      #toutes les solutions acceptables pour la case (i,j)
          mat[i,j]=sol[i,j,k]         #remplissage de la case par la k-eme solution
            if ((resolution(mat,pos+1))$bool==TRUE){   # si c'est OK au rang n+1 alors je renvoie TRUE
            out<-list(0,0)
            out$mat<-mat
            out$bool<-TRUE
            return(out)
            }
        mat[i,j]=0                   
        out<-list(0,0)
        out$mat<-mat
        out$bool<-FALSE
        return(out) 
      }
    }          
 }  
 
######
#MAIN#
###### 
 
resolution(sudo,1)

Et les sorties :
- lors du browser() quand je tape "mat"

;
- le return de la fonction "resolution"

.

Code :

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

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
Browse[1]> mat
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,]    9    7    8    6    5    3    4    2    1
 [2,]    6    4    3    7    2    1    5    9    8
 [3,]    2    5    1    4    9    8    6    7    3
 [4,]    1    6    5    9    7    4    8    3    2
 [5,]    7    9    4    8    3    2    1    5    6
 [6,]    8    3    2    5    1    6    9    4    7
 [7,]    3    2    6    1    4    5    7    8    9
 [8,]    4    8    9    3    6    7    2    1    5
 [9,]    5    1    7    2    8    9    3    6    4
Browse[1]> c
[[1]]
[1] 0
 
[[2]]
[1] 0
 
$mat
      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
 [1,]    9    7    8    0    0    0    0    2    0
 [2,]    0    0    0    0    0    0    5    0    0
 [3,]    0    5    0    0    0    0    0    0    0
 [4,]    1    6    5    9    7    4    8    3    2
 [5,]    0    9    4    8    0    2    0    0    0
 [6,]    0    0    0    0    0    6    0    0    0
 [7,]    0    2    0    0    0    0    0    0    9
 [8,]    0    0    0    0    0    0    0    0    0
 [9,]    5    1    7    0    0    9    3    6    0
 
$bool
[1] TRUE

**vchouraki** · 24/06/2011, 16h40

Sinon il y a un package pour ça :

http://cran.r-project.org/web/packag...oku/index.html

Ça peut te donner des pistes. Après je comprends qu'on puisse faire un algo pour le plaisir de faire un algo...

++

Vincent

**Rproblème** · 24/06/2011, 16h51

Envoyé par vchouraki

Sinon il y a un package pour ça :

http://cran.r-project.org/web/packag...oku/index.html

Ça peut te donner des pistes. Après je comprends qu'on puisse faire un algo pour le plaisir de faire un algo...

++

Vincent

Merci, j'y avais déjà jeté un œil.
J'ai dans l'idée de tester et comparer plusieurs type de résolution, celle présenté ici étant la manière "bruteforce".

Je comprends vraiment pas pourquoi l'algo récursif "pile" bien mais après "dépile" tout le travail.
Une erreur d'algo ou alors de language R...

++

**Rproblème** · 28/06/2011, 15h18

Personne n'a trouvé de coquille ?

J'ai réussi à l'implémenter sans récursif, cependant j'aimerais comprendre où est mon erreur dans la fonction ci dessus ...

Fonction récursive en R, soucis !

R

Discussions similaires

Partager

Partager