Automatiser la réponse au Sudoku

**Matthieu Brucher** · 17/10/2005, 23h06

Ta deuxième partie est en force brute tout de même, puisque tu testes les possibilités jusqu'à trouver la bonne valeur.
Ent out cas, les tests automatiques m'ont déjà aidé à trouver pas mal d'erreurs

chez moi

**Bloon** · 17/10/2005, 23h47

Oui... et non :-)

A partir du moment où tu es dans une situation où il ne reste que des cases ayant plusieurs valeurs possibles, il faut bien essayer ces valeurs.

Là ou je pourrais affiner mon algo c'est en implémentant plus de règles afin que cette situation apparaisse le plus tard possible.

Mais mon algo est déjà performant car en partant d'une grille totalement vide, il me génère une solution en moins d'une seconde. J'ai juste un petit bug à corriger car de temps en temps, il me trouve des solutions qui sont fausses

Bloon

**Matthieu Brucher** · 18/10/2005, 07h15

Normalement, à partir des règles qu'on a proposé ici, on arrive à résoudre toutes les grilles.

**Bloon** · 18/10/2005, 10h10

Envoyé par Miles

Normalement, à partir des règles qu'on a proposé ici, on arrive à résoudre toutes les grilles.

Oui mais j'ai mal implémenté certaines règles, donc certaines grilles plantent.

Par exemple, lorsque je supprime une valeur de la liste des valeurs possibles d'une case, s'il ne reste qu'une valeur possible pour la case je l'affecte immédiatement. C'est vrai, mais il faut d'abord que je termine d'enlever cette valeur des autres cases de l'ensemble sinon je peux me retrouver dans une situation incohérente.

De plus l'utilisation de la récursivité risque de poser problème sur des grilles de taille 4,5 ou plus.

Bloon

**Matthieu Brucher** · 18/10/2005, 10h21

Tu peux développer ta pensée à ce sujet ? Je ne vois pas exactement comment ça peut planter, en fait

**DrTopos** · 18/10/2005, 10h48

Envoyé par Miles

Normalement, à partir des règles qu'on a proposé ici, on arrive à résoudre toutes les grilles.

As-tu quelques arguments pour étayer cette affirmation, ou est-ce seulement expérimental ? Il serait intéressant que tu puisses la démontrer formellement.

**Matthieu Brucher** · 18/10/2005, 10h54

Il fallait se douter que ça tomberait, cette question

C'est plus expérimental qu'autre chose...
Enfin, je vais essayer d'aimplémenter les 2 dernières variantes de la règle 3 pour voir si j'arrive à résoudre ton premier Sodoku, le seul qui me résiste pour l'instant

**Bloon** · 18/10/2005, 11h32

Envoyé par Miles

Tu peux développer ta pensée à ce sujet ? Je ne vois pas exactement comment ça peut planter, en fait

Supposons qu'à un instant T je sois dans la situation suivante :

Un carré contient les 3 cases suivantes ayant chacune 2 possibilités :

1 ou 7
1 ou 9
1 ou 4

(les 6 autres cases ne nous intéressent pas)

On considère également la ligne Y, qui contient la dernière case (1 ou 4) et qui n'a plus que 2 cases inconnues : (1 ou 4) et une autre case d'un autre carré que nous appellerons (4 ou 1)

T1 : je mets 1 dans la case (1 ou 7)
Il faut donc que j'enlève le 1 des 2 autres

T2 : j'enlève le 1 dans la case (1 ou 9)
je détecte que cette case n'a plus que le 9, je mets donc 9 dans cette case, avant même d'avoir enlevé le 1 de la case (1 ou 4) et c'est là l'erreur.

T3 : je mets 9 dans la case (1 ou 9)
Supposons que ceci provoque le remplissage de la case (4 ou 1) de la ligne Y avec la valeur 4.

T4 : je mets 4 dans la case (4 ou 1) de la ligne Y
Dans Y, il ne reste plus qu'une case à renseigner avec la valeur 1 et c'est ma case (1 ou 4). Comme je n'ai pas enlevé le 1 des valeurs possibles de la case (cf ce que je dis à T2), je mets 1 dans cette case et je me retrouve avec 2 cases 1 dans mon carré.

Donc, quand je pars dans une mauvaise direction, je peux me retrouver dans une situation incohérente à cause de ce bug.

C'est un problème de programmation, je vais corriger mais il faut aussi que je bosse un peu

Bloon

**Bloon** · 18/10/2005, 11h56

Envoyé par Miles

Normalement, à partir des règles qu'on a proposé ici, on arrive à résoudre toutes les grilles.

Au fait qu'entends-tu par là ? Tu veux dire qu'on peut résoudre toutes les grilles sans avoir jamais besoin de faire des hypothèses ? Que si on implémente toutes ces règles, on ne se retrouve jamais dans une situation ou il reste des cases à plusieurs possibilités ?

Il faudrait définir ce qu'est une grille : une grille vide est-elle une grille sudoku ?

Bloon

**DrTopos** · 18/10/2005, 11h59

Envoyé par Bloon

Il faudrait définir ce qu'est une grille : une grille vide est-elle une grille sudoku ?

Excellente question. Officiellement, une grille sudoku correcte ne doit avoir qu'une seule solution. Mais ce n'est peut être pas la bonne définition pour programmer.

**Bloon** · 18/10/2005, 12h23

Envoyé par DrTopos

Envoyé par Bloon

Il faudrait définir ce qu'est une grille : une grille vide est-elle une grille sudoku ?

Excellente question. Officiellement, une grille sudoku correcte ne doit avoir qu'une seule solution. Mais ce n'est peut être pas la bonne définition pour programmer.

Ca dépend de ce qu'on programme : si on programme la résolution d'une grille, ça n'a pas d'importance : Soit il n'y a qu'une solution et on la trouve. Soit il y en a plusieurs et on en trouve une.

Par contre si on veut programmer la génération d'une grille de départ n'ayant qu'une solution...

Faut-il tester toutes les possibilités et s'arrêter lorsque l'on a résolu la grille avec 2 résultats différents ? Y a-t-il des règles à implémenter permettant de limiter le nombre de tentatives ?

Bloon

**Trap D** · 18/10/2005, 13h20

Envoyé par Bloon

Par contre si on veut programmer la génération d'une grille de départ n'ayant qu'une solution...

J'ai fais des essais avec des "fonds de grilles symétriques.
Pour les grilles avec de "nombreuses" case exposées ça marche bien la génération prend moins de 1 minute (tirage aléatoire des premières cases exposées puis quand la moitié des cases sont remplies recherche de solution) mais c'est beaucoup plus long (et même interminable plus de 1/2 g parfois) quand il y a peu de cases exposées, (style les grilles de DrTopos).

**Matthieu Brucher** · 18/10/2005, 13h36

L'avantage de se servir uniquement de règles de résolution claires comme celles données - en fait, je n'ai pas encore eu à utiliser de règle plus complexe que celles-ci, donc je suppose que c'est relativement possible qu'avec ces 3 ou 4 règles, on puisse résoudre tout jeu -, c'est que si on ne peut pas résoudre une grille, elle n'est sans doute pas valable.
Ce qui fait que par exemple, pour générer une nouvelle grille, on remplit la grille, puis on enlève aléatoirement un nombre jusqu'à ce que le solver ne réussisse plus à la reconstituer - on fait de la compression de données

-, et pour qualifier la complexité de la grille, il suffit de donner plusieurs modes au solver, facile quand on utilise juste les 2 premières règles, moyen pour les 3 premières et difficile pour les 4 règles.

**random** · 18/10/2005, 15h41

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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
 
Option Explicit
 
Dim nbmodif As Integer
Dim nbpassage As Integer
Sub complete()
Dim boucle As Variant
Range("a1:i9").Select
For Each boucle In Selection
If IsEmpty(boucle) Then boucle.Formula = "123456789"
Next boucle
End Sub
 
Sub evanbcar()
Dim tot As Integer
Dim x As Variant
Worksheets("sudo").Range("a1:i9").Select
For Each x In Selection
tot = tot + 9 - Len(x.Value)
Next x
Worksheets("sudo").Cells(2, 10).Select
Selection.Value = (9 * 9 * 9) - tot
End Sub
 
Sub modcarre(carre As Integer, valeur As Variant)
Dim ligne As Integer
Dim colonne As Integer
Dim carcours As Integer
For ligne = 1 To 9
For colonne = 1 To 9
carcours = (Int((colonne - 1) / 3) + 1) + ((Int((ligne - 1) / 3)) * 3)
If carcours = carre Then
Worksheets("sudo").Cells(ligne, colonne).Select
If Len(Selection) <> 1 Then
Selection.Formula = raye(Selection.Value, valeur)
End If
End If
Next colonne
Next ligne
End Sub
 
 
 
Sub unicol()
Dim nb As Variant
Dim colonne As Integer
Dim ligne As Integer
Dim occur As Integer
For nb = 1 To 9
For colonne = 1 To 9
occur = 0
For ligne = 1 To 9
Worksheets("sudo").Cells(ligne, colonne).Select
If Selection.Value = nb Then
occur = 0
Exit For
End If
If InStr(1, Selection.Value, nb, 1) <> 0 Then occur = occur + 1
Next ligne
    If occur = 1 Then
    For ligne = 1 To 9
    Worksheets("sudo").Cells(ligne, colonne).Select
    If InStr(1, Selection.Value, nb, 1) <> 0 Then
    Selection.Value = nb
    nbmodif = nbmodif + 1
        End If
        Next ligne
    End If
evanbcar
Next colonne
Next nb
End Sub
 
Sub uniligne()
Dim nb As Variant
Dim colonne As Integer
Dim ligne As Integer
Dim occur As Integer
For nb = 1 To 9
For ligne = 1 To 9
occur = 0
For colonne = 1 To 9
Worksheets("sudo").Cells(ligne, colonne).Select
If Selection.Value = nb Then
occur = 0
Exit For
End If
If InStr(1, Selection.Value, nb, 1) <> 0 Then occur = occur + 1
Next colonne
    If occur = 1 Then
    For colonne = 1 To 9
    Worksheets("sudo").Cells(ligne, colonne).Select
        If Len(Selection.Value) <> 1 And InStr(1, Selection.Value, nb, 1) <> 0 Then
 
    Selection.Value = nb
    nbmodif = nbmodif + 1
 
    End If
 
    Next colonne
    End If
Next ligne
Next nb
End Sub
 
Sub unicarr()
Dim enc As Variant
Dim nb As Variant
Dim colonne As Integer
Dim ligne As Integer
Dim occur As Integer
For ligne = 1 To 7 Step 3
For colonne = 1 To 7 Step 3
For nb = 1 To 9
occur = 0
Worksheets("sudo").Range(Cells(ligne, colonne), Cells(ligne + 2, colonne + 2)).Select
For Each enc In Selection
If enc.Value = nb Then
occur = 0
Exit For
End If
If InStr(1, enc.Value, nb, 1) <> 0 Then occur = occur + 1
Next enc
If occur = 1 Then
For Each enc In Selection
If InStr(1, enc.Value, nb, 1) <> 0 Then
enc.Value = nb
nbmodif = nbmodif + 1
End If
Next enc
End If
Next nb
evanbcar
Next colonne
Next ligne
 
End Sub
'
'
Sub verifb()
Dim ligne As Integer
Dim colonne As Integer
Dim valeur As Variant
Dim carre As Integer
nbpassage = nbpassage + 1
nbmodif = 0
Call unicol
Call uniligne
Call unicarr
For ligne = 1 To 9
For colonne = 1 To 9
Worksheets("sudo").Cells(ligne, colonne).Select
valeur = Selection.Value
If Len(valeur) = 1 Then
carre = (Int((colonne - 1) / 3) + 1) + ((Int((ligne - 1) / 3)) * 3)
Call modligne(ligne, valeur)
Call modcol(colonne, valeur)
Call modcarre(carre, valeur)
evanbcar
End If
Next colonne
Next ligne
If nbmodif <> 0 Then
MsgBox ("modifications à ce passage: " & nbmodif)
Call verifb
Else
MsgBox ("solution trouvée en " & nbpassage)
End If
End Sub
 
Sub modligne(ligne As Integer, valeur)
Dim colonne As Integer
For colonne = 1 To 9
Worksheets("sudo").Cells(ligne, colonne).Select
If Len(Selection) <> 1 Then
Selection.Formula = raye(Selection.Value, valeur)
End If
Next colonne
End Sub
 
Sub modcol(colonne As Integer, valeur)
Dim ligne As Integer
For ligne = 1 To 9
Worksheets("sudo").Cells(ligne, colonne).Select
If Len(Selection) <> 1 Then
Selection.Formula = raye(Selection.Value, valeur)
End If
Next ligne
End Sub
 
Function raye(dans As String, quoi As Variant) As Variant
Dim posi As Integer
posi = InStr(1, dans, quoi)
If posi <> 0 Then
raye = Left(dans, posi - 1) & Right(dans, Len(dans) - posi)
nbmodif = nbmodif + 1
Else
raye = dans
End If
End Function

voici ma solution qui règle pas mal de choses écrite pour excel en vba

ce qui reste à faire

1 sortir d'excel et écrire une interface
2 généraliser le problème aux tailles 15*15 et autres, ce qui suppose de remplacer les chiffres de traitement par des lettres après 9
3 généraliser les fonctions de recherche pour les bigrammes uniques
je m'explique s'il me reste pour une colonne 3 possibiltés codées
"123" "12" "12" je peux retirer "12" de "123"
quand on traite manu les bigrammes très peu de problèmes restent non résolus
4 écrire une procédure heuristique de finalisation
pour se faire quand on a tout essayé
passer la matrice à une matrice tempo
tester une hypothèses c'est à dire faire un choix pour le premier bigramme trouvé appliquer ses conséquences et la vérifier somme toute ligne toute colonne
=45
si la matrice est vérifiée et terminée on arrête là
sinon on explore les autres branches

en exploitant mon programme + manuellement les bigrammes et éventuellement deux niveau d'hypothèse j'ai 100 % de réussite

**Matthieu Brucher** · 18/10/2005, 15h49

La règle des bigramme, c'est notre règle n°2 dans le résumé de Toppos, elle a l'air quand même importante

C'est pour ta phrase " quand on traite manu les bigrammes très peu de problèmes restent non résolus " que je pense qu'avec les règles qu'on a, on peut sans doute tout résoudre.

**random** · 18/10/2005, 15h56

ps pour la génération de grille j'ai aussi écrit un générateur
ce générateur place (presque au hasard) des nombres et recalcule
dynamiquement la solution au fur et à mesure jusqu'a solution complète
on obtient deux matrices une matrice solution une matrice problème
cela fonctionne parfaitement et garantit l'unicité de la réponse
on peut moduler le problème en rajoutant des données dans la matrice solution
la plupart des jeux faciles sont solvables par ma programmation avec
parfois 4 ou 5 chiffres de moins
par contre ceci n'est pas garant de l'intérêt du problème pour un humain

ps j'ai essayé des méthodes de solveur mais c'est long et compliqué le corps des contraintes est fastidieux et cette voie ne m'a pas semblé
plus prometteuse

**random** · 18/10/2005, 16h09

Envoyé par Miles

La règle des bigramme, c'est notre règle n°2 dans le résumé de Toppos, elle a l'air quand même importante

C'est pour ta phrase " quand on traite manu les bigrammes très peu de problèmes restent non résolus " que je pense qu'avec les règles qu'on a, on peut sans doute tout résoudre.

bien sûr que c'est important mon programme ne traite pas tous les cas de figures parcequ'il ne l'intègre pas encore

en fait dans ma démarche j'entre les chiffre un à un sur tableau excel
et je lance l'algo de solution
j'obtiens en réponse un tableau des possibiltés que je peux modifier
manu
cela me permet de mesurer l'efficacité des différentes stratègies
le bigramme est indispensable
je réfléchis d'ailleurs à une règle du trigramme qui serait une généralisation de celle du bigramme
mais ce qui m'importe aujourdhui c'est le nombre de tentatives et je veux
optimiser ma stratègie je ne suis pas certain que cela soit payant

**Bloon** · 18/10/2005, 17h33

Dans le même ordre d'idée, il peut être intéressant d'exploiter le fait qu'un carré a plusieurs cases en commun avec les autres ensembles (lignes et colonnes), créant ainsi 6 sous-ensembles (3 lignes et 3 colonnes) à partir desquels on peut déduire des choses. Par exemple :

Code :

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

1
2
3
4
5
  ---------------------------
A | (1,2,3) (1,2,3) (1,2,3,5) | (autres cases ligne A ...)
B | (4)     (3,5)   (6)       | (autres cases ligne B ...)
C | (7)     (8)     (9)       | (autres cases ligne C ...)
  ---------------------------

-> on peut retirer 1 et 2 des valeurs possibles des 6 cases restantes de la ligne A car elles figurent dans un seul sous-ensemble de lignes du carré. En revanche, 3 et 5 figurent dans 2 sous-ensembles de lignes différents (lignes A et B), on ne peut rien déduire quant au reste des lignes A et B.

Bloon

**Matthieu Brucher** · 18/10/2005, 17h40

Ca s'appelle la règle 3

C'est une des 4 variantes, on analyse un carré et on enlève sur une ligne.
Mon programme a réussi à finir la grille 1 de Topos avec la règle 2 implémentée et 2 sur 4 variantes de la règle 3 - avec les 4, ça plantait, il va falloir que je revois mes tests

-