Automatiser la réponse au Sudoku

Ca paraît évident ;)

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

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

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

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

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/

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

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.

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

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 ?

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

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

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

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

pourrais tu nous donner une de ces trois grilles stp

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]

Hello.

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

Merci.

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

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.