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) |
