Automatiser la réponse au Sudoku

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

-

**random** · 18/10/2005, 17h47

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

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

Ca paraît évident

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

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 ?

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

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

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

Ah, voici une version plus générale de la règle, et c'est sans doute largement plus clair

**random** · 19/10/2005, 08h47

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

**Matthieu Brucher** · 19/10/2005, 09h20

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

**Matthieu Brucher** · 19/10/2005, 15h07

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/

**random** · 19/10/2005, 17h07

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

**Matthieu Brucher** · 19/10/2005, 17h15

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.

**random** · 19/10/2005, 18h38

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

**Matthieu Brucher** · 19/10/2005, 18h53

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 ?

**vmolines** · 20/10/2005, 15h41

J'en ai vu un sur une page d'un magazine de sudoku de ma cop. Je vais essayer de faire passer.

**Matthieu Brucher** · 20/10/2005, 16h21

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

**Bloon** · 26/10/2005, 01h45

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.

Les sources Delphi

L'exe

Bloon

**Matthieu Brucher** · 26/10/2005, 07h10

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

**random** · 26/10/2005, 09h35

pourrais tu nous donner une de ces trois grilles stp

**Matthieu Brucher** · 26/10/2005, 10h10

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

-

**monstroplante** · 06/11/2005, 05h08

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 :

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