Automatiser la réponse au Sudoku

Version imprimable

Voir 40 message(s) de cette discussion en une page

17/10/2005, 23h06
Matthieu Brucher

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 :D
17/10/2005, 23h47
Bloon

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 :fou:

Bloon
18/10/2005, 07h15
Matthieu Brucher

Normalement, à partir des règles qu'on a proposé ici, on arrive à résoudre toutes les grilles.
18/10/2005, 10h10
Bloon

Citation:

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
18/10/2005, 10h21
Matthieu Brucher

Tu peux développer ta pensée à ce sujet ? Je ne vois pas exactement comment ça peut planter, en fait :|
18/10/2005, 10h48
DrTopos

Citation:

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.
18/10/2005, 10h54
Matthieu Brucher

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 ;)
18/10/2005, 11h32
Bloon

Citation:

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 :wink:

Bloon
18/10/2005, 11h56
Bloon

Citation:

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
18/10/2005, 11h59
DrTopos

Citation:

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.
18/10/2005, 12h23
Bloon

Citation:

Envoyé par DrTopos

Citation:

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
18/10/2005, 13h20
Trap D

Citation:

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).
18/10/2005, 13h36
Matthieu Brucher

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.

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

18/10/2005, 15h49
Matthieu Brucher

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.
18/10/2005, 15h56
random

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
18/10/2005, 16h09
random

Citation:

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

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:

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

18/10/2005, 17h40
Matthieu Brucher

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 :( -
18/10/2005, 17h47
random

il serait souhaitable que vous ajoutiez une régle
un sudoku n'a qu'une solution
cela permettrait à mon sens de savoir de quoi on parle
18/10/2005, 18h14
Matthieu Brucher

Ca paraît évident ;)
18/10/2005, 18h37
Bloon

Citation:

Envoyé par random

je réfléchis d'ailleurs à une règle du trigramme qui serait une généralisation de celle du bigramme

A priori on peut la généraliser ainsi :

Dans un ensemble (ligne, colonne, carré) :

si on trouve un groupe de N cases différentes dont l'ensemble des valeurs possibles est composé de N valeurs distinctes, alors on peut retirer ces N valeurs de la liste des valeurs possibles des autres cases de l'ensemble. Exemple : (1,2) (3,4) (1,3) (2,4) : on a 4 cases, on peut retirer 1,2,3,4 des 5 autres cases.

Cette règle peut être très couteuse mais en étant appliquée à fond, elle permet peut-être de déterminer si un sudoku a une ou plusieurs solutions ?

Citation:

Envoyé par random

il serait souhaitable que vous ajoutiez une régle
un sudoku n'a qu'une solution
cela permettrait à mon sens de savoir de quoi on parle

Citation:

Envoyé par Miles

Ca paraît évident ;)

Oui, alors le problème n'est pas de trouver la solution d'un sudoku mais plutôt de savoir s'il y a 0, 1 ou + de solutions (le nombre exact de solutions n'a pas d'intérêt).

Un sudoku résolu en appliquant les règles a une solution unique (puisque l'on n'a pas besoin de faire d'hypothèse)

Mais peut-on dire qu'un sudoku qui n'est pas résolu lorsque qu'on a appliqué toutes les règles a plusieurs solutions ? Il faudrait être sûr que nos règles sont exhaustives.

Bloon
18/10/2005, 18h47
Matthieu Brucher

Ah, voici une version plus générale de la règle, et c'est sans doute largement plus clair :)
19/10/2005, 08h47
random

il faudrait reformuler la règle
un sudoku a une solution unique
ceci permet d'utiliser des hypothèses à condition d'éliminer les autres
soit une grille non résolue dans laquelle il reste par exemple deux bigrammes indépendants et plusieurs chaînes de rang plus élevé
cela me laisse quatre possibilités de résolution de mes bigrammes
j'ai le droit d'en valider une à condition de prouver que les trois autres
conduisent à des conclusions qui ne respectent pas les règles.

quand on travaille sur la génération automatique des grilles ces mécanismes entrenten jeu et la génération peut s'analyser comme la suppression d'hypothèses non valides
c'est pourquoi, à mon avis, les stratégies de générations aléatoires que j'ai explorées indépendemment du solveur se sont montrées inopérantes
19/10/2005, 09h20
Matthieu Brucher

J'ai trouvé une petite publi où on parlait de Sudoku. Bon, c'est pas super parce qu'ils ne donnent pas leurs règles et tout et tout, mais il y a des points intéressants, comme par exemple la description du jeu par des contraintes : http://citeseer.ist.psu.edu/cache/papers/cs/29794/http:zSzzSzwww.cos.ufrj.brzSz~ineszSzpaperszSzciclops01.pdf/arc-consistency-algorithms-on.pdf
19/10/2005, 15h07
Matthieu Brucher

Pour la génération de grilles, on peut se baser sur la recherche de grilles existantes qui a été faite ici : http://www.shef.ac.uk/~pm1afj/sudoku/
19/10/2005, 17h07
random

????? on pourrait peut être ??????? appliquer au sudoku les algos
du rubiscube (orthographe ?)
après tout on doit pouvoir considérer un hyper cube à neuf faces
dont la permutation est liée avec celui des autres dans un espace
à trois dimensions (ligne colonne carré)
19/10/2005, 17h15
Matthieu Brucher

C'est ce qui est utilisé dans la mini publi du lien que j'ai donné, ils ont cherché en grande partie les grilles équivalentes à une transformation près.
19/10/2005, 18h38
random

cela prouve
1 que j'aurais du éplucher le lien
j'avais prévu de le faire dès que j'aurais un moment
2 que je devrais me discipliner un peu

mais ce problème me tient et je suis si content d'avoir trouvé
moyen d'en parler...

je te prie de m'excuser et je vais essayer d'être plus correct à l'avenir
19/10/2005, 18h53
Matthieu Brucher

C'est pas grave, je fais la même chose à tout bout de champ ;)
Bon, je vais essayer d'améliorer mon solveur un peu plus pour le rendre indépendant de la dimension.
Y'a qqn qui a des puzzles de taille supérieure à 9 ?
20/10/2005, 15h41
vmolines

J'en ai vu un sur une page d'un magazine de sudoku de ma cop. Je vais essayer de faire passer.
20/10/2005, 16h21
Matthieu Brucher

J'ai trouvé des puzzles bien difficiles sur le site des Sudokus du Daily Telegraph, mon prog arrive à en résoudre certains, pas encore les autres. Ils développent des techniques de pointe :)
26/10/2005, 01h45
Bloon

bon finalement j'ai abandonné l'approche récursive. Ca fonctionnait bien dans la majorité des cas mais certaines grilles provoquaient des situations inextricables rendant les résultats incohérents, voire plantant carrément l'appli (quand un programme récursif part en sucette, les plantages peuvent être violents).

Donc maintenant, j'ai ajouté la notion de règle et quand je veux résoudre une grille, je lui indique les règles que je souhaite utiliser.

Pour l'instant je n'ai fait que 2 règles :

1 : lorsqu'il n'y a plus qu'une seule valeur possible dans une case, la case prend cette valeur

2 : dans un ensemble, lorsqu'une valeur n'est présente que dans les valeurs possibles d'une case, cette case prend la valeur

Ainsi qu'une troisième, qui est la règle "en force" :

3 : on prend la case ayant le moins de valeurs possibles et on essaye. si ça plante, on essaye autre chose.

Mon objectif est maintenant d'implémenter suffisament de règles afin que la n°3 ne serve jamais.

Cette approche permet de plus d'évaluer la difficulté d'une grille : si on n'utilise que les règles 1 et 2, la grille est facile, s'il faut utiliser les règles suivantes, c'est plus difficile.

:arrow: Les sources Delphi
:arrow: L'exe

Bloon
26/10/2005, 07h10
Matthieu Brucher

Tout à fait d'accord avec toi.
Je vais bientôt mettre à jour ma version sur le net, j'ajouterai 3 grilles qulifiées d'infaisable sans essai/erreur...
26/10/2005, 09h35
random

pourrais tu nous donner une de ces trois grilles stp
26/10/2005, 10h10
Matthieu Brucher

Les grilles sont dispos avec mon solveur : http://matthieu.brucher.free.fr/Setup.msi ou sur le site internet du sudoku, mais pas celui du Times - faire une recherche avec sudoku et bifurcation -
Mon format de fichier est basé sur XML, c'est facile à décrypter, je pense, et au pire, il y a la grille sur le site Internet ;)
J'ai aussi les sources pour les utilisateurs de Linux - d'ailleurs tout est en GPL, c'est pas encore indiqué, mais ça l'est ;) -

Salut tt le monde !
Je programme moi aussi un solveur.
J'ai volontairement évité de lire ce topic ou d'y participer pour ne pas etre influencé et de perdre mon raisonement personel.

Je viens, finalement de parcorir le topic et vous fait part de mes choix :

Langage : Delphi6

représentation de la grille:
Tableau (9x9) de variables de type ensemble ([1..9]) placées dans un"record" au cas ou j'aurait besoin d'ajouter des infos par la suite.
pour chaque résolution, je charge la grille "utilisateur" dans la grille "traitement" puis, apres resolution, operation inverse. Cela me permet de faire des modifs manuellement sur la grille puis de relancer mon algorithe.
Je part de toutes les possibilitées pour les cases inconnues et élimine les possibilitées au fur et a mesure. Une case éllucidée est une case pour laquel l'enssemble associé ne comporte qu'un seul élément.
L'utilisation de variables de type ensemble simplifie beaucoup les calculs.

Multiples solutions pour une grille :
Je ne shaite pas que mon algorithme fasse de choix. Il ne doit donc pas etre capable de résoudre les grilles à plusieurs solutions. Mais je peux moi meme modifier la grille manuellement si elle n'est pas résolue.
Il est facile de verifier qu'une grille n'a qu'une seule solution. Si la grille n'est pas resolue, je choisi une case pour laquelle il n'y à que peut de possibilité, fait un choix et relance mon algorithme. Si il se rend compte que la grille est invalide (certaines case n'ont plus de possibilités) c'est que ce choix n'etait pas correcte. En continuant ainssi, on peut vite verifier si une grille à une solution unique.

Le principe de mon algorithme :
Pour l'instant, je me contente de résoudre les enssemble de 9 cases indépendament les uns des autres.
La regle : Pour chaque groupe de 9 cases, je recherche toutes les combinaisons de cases(case1,case1+case2,case1+case2+case3.....) et additionne l'ensemble de leur possibilités dans l'enssemble "Esomme". Si le nombre d'elements de Esomme est = au nombre de case de la combinaison de cases, alors les éléments de Esomme sont supprimés de l'ensemble de possibilités de chaque case du groupe ne fesant pas parti de la combinaison.
Pour résumer : si x cases partagent x possibilitées alors ces x possibilitées sont forcement réservées par ces cases.
Quelques exemples :
-Une case sure revient à 1 possibilité pour 1 case (nombre de cases=nombre de possibilités) donc cette possibilité est forcement dans cette case et peut donc etre supprimée des autres.
- Pour 3 cases ayant les possibilités : 12,13,123
nous avons 3 cases qui partages 3 possibilités
-pour finir : quand nous avons une possibilité qui n'est present que dans une case d'une ligne, cela veux dire que les 8 cases restantes ne peuvent se partager que 8 possibilités. Mon algo résoud donc ce cas aussi...

Je pense qu'avec cet algo, je resoud tout ce qu'il est possible de resoudre dans un ensemble de 9 cases. Il faudrait, maitenant que j'etudie l'interaction des ensembles entre eux.

Je vous dépose une partie de mon code si ca vous interesse (c'est du Delphi6) :
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 //Declaration de mes types personels : type Tpo = 1..9; Tpos = set of Tpo; Tcase = {packed} record //Le record ne me sert a rien pour l'instant mais c'est au cas ou... pos:Tpos; end; Tjob=array [1..9] of ^Tcase; //tableau de pointeurs vers des Tcases //Declaration de mon tableau : var tab:array[1..9,1..9] of Tcase; //Cette procedure se charge d'envoyer tous les groupes de 9 cases a la fonction qui élimine les hipotheses : procedure TForm1.Button1Click(Sender: TObject); var x,y,x_bloc,y_bloc:integer; job:Tjob; begin if not loadgrid then exit; //charge la grille "utilisateur" //resoud les lignes for x:=1 to 9 do begin for y:=1 to 9 do job[y]:=@Tab[x,y]; Resolve(job,1,[]); end; //resoud les colones for y:=1 to 9 do begin for x:=1 to 9 do job[x]:=@Tab[x,y]; Resolve(job,1,[]); end; //resoud les blocs for X_bloc:=0 to 2 do for Y_bloc:=0 to 2 do begin for x:=(X_bloc*3+1) to (X_bloc*3+3) do for y:=(Y_bloc*3+1) to (Y_bloc*3+3) do job[3*(x-3*X_bloc)+y-3*Y_Bloc-3]:=@Tab[x,y]; Resolve(job,1,[]); end; drawtab;//Affiche la table modifiée end; //Voici la procedure recursive qui analyse toutes les combinaisons de cases et suprime les hypothese. function TForm1.resolve(job:TJob; min:integer; combi_ec:Tpos):integer; var i,m:byte; ESomme,combi:Tpos; begin // pour m de min(recursif) à nombre de cases du tableau de pointeurs. for m:=min to High(job) do begin Combi:=Combi_ec+[m]; //sort si le nombre d'élements de combi est égal au nombre de cases de job if countpos(Combi)=High(job) then exit; resolve(job,m+1,Combi); //debut:code pour chaque combinaison (combi:Tpos) //recupere le nombre de possibilités Esomme:=[]; for i:=1 to High(job) do if i in combi then Esomme:=Esomme+job[i].pos; if countpos(Esomme)=countpos(combi) then begin //suppression des possibilités for i:=1 to High(job) do if not (i in combi) then job[i].pos:=job[i].pos-ESomme; end; //fin:code pour chaque combinaison (combi:Tpos) end; end; //me permet de recuperer le nombre d'element d'un ensemble de possibilités. function Tform1.CountPos(E:Tpos):byte; var i:integer; begin result:=0; for i:=1 to 9 do if i in E then inc(result); end;
Et, pour finir une capture décran de ma grille "utilisateur" qui permet d'afficher/modifier les données.
http://www.arcanesansnom.com/test/sudoku.jpg[/b]

11/11/2005, 17h45
vincent0

Sudoku

Hello.

Comment feriez-vous un algorithme qui résoud les grilles des Sudokus ?

Merci.
11/11/2005, 17h47
plegat

Salut,

Il y a un post sur ce sujet en cours... là: http://www.developpez.net/forums/viewtopic.php?t=399772

Si ça peut te donner des idées...
12/11/2005, 16h18
vincent0

Hello.

J'ai très bien compris comment on résolvait une grille de sudoku avec un algo mais comment feriez-vous pour générer une grille de sudoku qui n'aurait qu'une et une seul solution ?

Merci.

Voir 40 message(s) de cette discussion en une page