Automatiser la réponse au Sudoku

**sovitec** · 08/12/2006, 11h05

Envoyé par méphistopheles

J'ai également essayer de générer de cette manière tous les sudokus possible: comme la barre de progression n'avait pas bougé au bout de 24h (et 450 000 solutions trouvées) j'ai décidé d'aretter là.

Le sudoku possède beaucoup de permutations/symétries possibles (au moins 52254720 si le rapide calcul que je viens de faire est bon). Tu pourrais déjà t'économiser pas mal d'énergie en partant d'une première ligne remplie (123456789 par exemple) et en multipliant ton résultat par les 9! permutations possibles.

**Matthieu Brucher** · 08/12/2006, 11h11

Envoyé par méphistopheles

rJ'ai également essayer de générer de cette manière tous les sudokus possible: comme la barre de progression n'avait pas bougé au bout de 24h (et 450 000 solutions trouvées) j'ai décidé d'aretter là.

Il y a une publication à ce sujet, ne t'embêtes pas à calculer ça toi-même ! C'est LARGEMENT supérieur à tes 450000 solutions.

**méphistopheles** · 08/12/2006, 14h31

je suis au courant, j'ai étudié mon logiciel pour. (il monte jusqu'au 10^27 solutions en mémoire, même si je ne pense pas que quelqu'un s'amuse à les chercher avec ce genre de logiciel.

**Sivrît** · 24/02/2006, 13h21

Envoyé par Tellmarch

je vais finir par te faire un dessin pour que tu comprennes

Moi je veux bien !

J'ai beau essayer j'arrive pas à voir les deux procédés comme équivalents. Que leurs complexités le soit me semble même normal, mais avoir la même complexité ne rend pas deux algorythmes identiques.

Envoyé par Tellmarch

en bref tu as une seule regle, qui dit "ça doit etre la meme chose que ce que trouverait une recherche exhaustive"

Ben ça vaudrait mieux. Si le résultat n'est pas le même ça va être sacrément mauvais signe pour notre raisonnement !

En tout cas une règle peut tout à fait faire abstraction de la taille du problème. Par exemple :
"Si N valeurs ne peuvent être prises que par N cases d'un groupe, alors ces cases ne peuvent prendre aucune autre valeur"
Manifestement ce n'est pas une règle facile à implémenter (de ce point de vue je préfère largement implémenter un algo récursif) ni facile à appliquer. Par contre je la trouve conceptuellement plus élégante que de tester brutalement toutes les combinaisons jusqu'à trouver la bonne. L'idée est d'améliorer sa compréhension du jeu, pas de tout déléguer à une machine et de compter sur ses méga hertz.

Même si ça ne va pas plus vite il y a une application. C'est peut-être juste moi

mais je suis incapable d'enchainer toutes les possibilités par essai/erreur. Pour un humain c'est juste impraticable. Par contre repérer des schémas et des groupements pour y appliquer des règles m'est naturel.

Tellmarch> Je viens juste de me dire que dans l'idée, les règles permettent de limiter l'ensemble possibilités par déduction... alors qu'une recherche les élimine une par une à chaque contradiction trouvée. C'est l'équivalence dont tu parles ?

**Tellmarch** · 24/02/2006, 13h54

en gros, le groupement sur une case correspondra exactement à une recherche de profondeur 1, sur 2 cases à une recherche de profondeur 2, etc...

bon je vais essayer de formaliser un algo pour que ça soit plus clair :

Soit C l'ensemble des contraintes du probleme.
Dans notre cas, C = D + E + F + G, ou :
D = {Dij : les nombres restants sur la case i,j}
E = {Gij : les places possibles pour le nombre j dans la ligne i}
F = {Gij : les places possibles pour le nombre j dans la colonne i}
G = {Gij : les places possibles pour le nombre j dans le carré i}

L'algorithme générique de parcours est alors le suivant (j'ai pas mal simplifié pour insister sur les elements essentiels de l'algo)

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
 
Fonction résoudre :
 
  Pour i allant de 1 à l'infini
 
     Parcours( à la profondeur i)
 
 
 
 
Fonction Parcours (int p : profondeur)
 
   Si il y a une contradiction Alors retour
 
   soit c la contrainte de cardinal minimal,
 
   Pour tous les choix possibles dûs à c, faire
 
      jouer le coup, mettre à jour la liste des contraintes;
 
      Parcours (à la profondeur p-1)
 
  Fin Pour

Prenons alors les regles de Miles, et regardons ce que ça donne.
L'existence d'un sous groupe restreignant le choix de k valeurs correspond exactement à l'appel à notre procedure de recherche, à la profondeur k, avec la meme complexité.

Au début Miles parlait de 3 regles, elles sont toutes contenues dans ce processus essai/erreur, avec la meme complexité.
Maintenant il semble qu'il soit revenu à l'idée d'une seule regle, mais cette regle est exactement :
"quelque soit k, l'algo de recherche à la profondeur k fixerait ces valeurs"
Donc sa regle c'est simplement d'appliquer le parcours...

Un tel algorithme générique de backtrack appliqué au sudoku se code en moins d'une vingtaine de lignes, et personnellement je trouve ça plus élégant que :

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
 
  bool SolverCore::solve()
  {
    do
    {
      do
      {
        do
        {
          do
          {
            do
            {
              do
              {
                popImpossibleValues();
              }while(applyRule0());
            }while(applyRule1());
          }while(applyRule2());
        }while(applyRule3());
      }while(applyRule4());
    }while(applyRule5());

sachant que toutes les regles sont contenues dans le backtrack, je trouve ça assez inutile

**Matthieu Brucher** · 24/02/2006, 15h15

Envoyé par Tellmarch

ce que toi tu comprends pas, c'est que ce que fait cette regle c'est exactement équivalent à une recherche en profondeur, ça a la meme complexité, ça trouve les memes choses...
Chercher tous les sous groupes de taille de plus en plus grande, c'est juste une dérecursification du parcours...
en bref tu as une seule regle, qui dit "ça doit etre la meme chose que ce que trouverait une recherche exhaustive"

je vais finir par te faire un dessin pour que tu comprennes

Faux, c'est une des règles les plus élémentaires et elle ne résoud pas tout, TRES loin de là. Tu devrais te renseigner un peu.

graphito > une grille de Sudoku a une seule solution, c'est une règle de base.

**Tellmarch** · 24/02/2006, 15h21

Bon comme tu n'arretes pas de changer d'avis, j'aimerais bien que tu me dises de quoi tu parles exactement...
- Tu as combien de regles?
- Lesquelles précisement?

**Matthieu Brucher** · 24/02/2006, 15h23

Tellmarch, ce que tu ne comprends pas, c'est que c'est facile de faire un algo dans ton genre, ça prend 3 secondes, c'est pas optimisé, c'est de la force brute et c'est tout. Si tu veux être plus élégant, déjà, tu appliques les règles élémentaires disant que tu ne peux avoir unevaleur qu'une seule fois par ligne colonne et carré. Après, tu n'appliques ta récursion que sur les cases ayant peu de valeurs restantes.
De plus, un algo tel que celui-ci ne t'indiquera jamais si une grille est valide donc tu ne pourras pas générer de nouvelles grilles valides.
Allez, je continue. L'ensemble des jeux solvables par force brute n'est pas l'ensemble des jeux, ni l'ensemble des jeux solvables par connaissance. Il est plus intéressant de connaître quelles sont les techniques à appliquer pour résoudre un jeu par connaissance que de donner la solution bêtement.

Si tu veux citer mon code, pense à prendre une version à jour et non pas une version datée de 4-5 semaines. Et regarde aussi ce qu'il fait que ton code ne peux pas faire - pardon, c'est pas du code... -

**Matthieu Brucher** · 24/02/2006, 15h28

Envoyé par Tellmarch

Bon comme tu n'arretes pas de changer d'avis, j'aimerais bien que tu me dises de quoi tu parles exactement...
- Tu as combien de regles?
- Lesquelles précisement?

Je t'ai proposé une règle. Je n'ai jamais dit qu'il n'y en avait qu'une, d'ailleurs toi qui a vu mon code, tu as bien constaté qu'il y en avait plusieurs, non ? J'ai même participé ici à une discussion sur le nombre de règles.
Allez, on fait le tour :
- unique visible ou invisible
- sous-groupes visibles
- intersection
- sous-groupes invisibles - plus difficiles à détecter -
- Burma - X-Wing, Swordfish, ... -
- ...
- Chaînes d'implication

**Tellmarch** · 24/02/2006, 15h31

bon donne moi préciment tes regles
[edit : tu les as données le temps que je rédige ce message, je vais me pencher dessus.]

Toutes celles que tu as dit jusqu'à présent sont strictement incluse dans mon algo, avec la meme complexité, en bref elles n'apportent strictement rien.
Alors peut etre que tu as inventé de nouvelles regles depuis, mais tu ne les as pas encore données.

Pour ce qui est de ton code, j'ai pris la version sourceforge, je sais pas si elle est à jour ou pas, c'est toi qui gere ça... mais ce que je voulais montrer n'est pas spécifique à ton code, c'est simplement qu'appliquer 3 regles qui correspondent à Parcours(1), Parcours(2) et Parcours(3) codées séparement, c'est pas une marque d'élégance, bien au contraire.

Enfin pour ta remarque sur les jeux solvables par force brute, je travaille sur des jeux ou l'ordinateur actuel ne bat meme pas un humain presque débutant, donc merci, mais je le savais deja...

**Tellmarch** · 24/02/2006, 15h37

Envoyé par Miles

Envoyé par Tellmarch

Bon comme tu n'arretes pas de changer d'avis, j'aimerais bien que tu me dises de quoi tu parles exactement...
- Tu as combien de regles?
- Lesquelles précisement?

Je t'ai proposé une règle. Je n'ai jamais dit qu'il n'y en avait qu'une, d'ailleurs toi qui a vu mon code, tu as bien constaté qu'il y en avait plusieurs, non ? J'ai même participé ici à une discussion sur le nombre de règles.
Allez, on fait le tour :
- unique visible ou invisible
- sous-groupes visibles
- intersection
- sous-groupes invisibles - plus difficiles à détecter -
- Burma - X-Wing, Swordfish, ... -
- ...
- Chaînes d'implication

Bon comme tu l'as dit, je n'ai pas la derniere version de ton code, et aucune envie de déchiffrer des milliers de ligne de code d'un langage que je connais pas.
Quelles sont les regles que tu juges nécessaires et suffisantes?
[edit]Enfin plus précisement, quelles sont les regles qui ne sont pas exactement équivalents à des appels à un parcours à une profondeur donnée?

**Tellmarch** · 24/02/2006, 15h57

Bien.
Je vais arreter cette discussion ici Miles, j'ai l'impression que tu ne comprendras jamais.

J'ai relu attentivement le sujet depuis le début.
- Au bout de 2 pages, tu affirmais que tu avais trouvé 2 regles qui résolvaient tous les sudoku sans exception.
- Une page plus loin tu as dit qu'il en fallait une supplémentaire finalement, et encore une fois que tous les sudokus étaient résolus.
- Un peu plus loin seulement tu te rends compte que des grilles résistent à ton algorithme, et tu rajoutes encore des regles.

En bref depuis le début tu te contentes de crier "ça marche ça résoud tout", sans aucune preuve.
Je t'ai prouvé le contraire, tu continue dans ton erreur.

Je t'ai donné un algo de backtrack qui recouvrait exactement toutes les regles que tu as donné depuis le début de ce post, et manifestement tu n'arrives meme pas à le comprendre, ou alors tu ne veux pas le comprendre.

J'en ai marre d'essayer de te convaincre alors que tu manifestement c'est sans espoir, donc j'arrete là...
Continues à cracher tes milliers de lignes de code inutiles si ça t'amuse, il y a des solveurs bien plus performant en une vingtaine de lignes.

++

**Steki-kun** · 24/02/2006, 19h50

Je confirme, ca prend 10 minutes et 25 lignes de Prolog; et ca solve un sudoku minimal en < 10ms. Y'a des gens qui aiment de torturer.

**pcaboche** · 28/02/2006, 19h23

Il s'en est écrit beaucoup de choses depuis la dernière fois que je suis venu ici (3 pages). Je vais juste répondre à quelques remarques:

Envoyé par random

prolog c'est bien beau mais c'est déléguer la résolution du problème à un logiciel qui grosso modo fait bêtement de l'exploration et élagage du champ du possible

Prolog ne fait pas "bêtement" du générer/tester de solutions. A chaque nouvelle contrainte, tu as une propagation des contraintes par consistance d'arc, c'est-à-dire que les domaines des variables sont réduits (en tenant compte des contraintes précédentes). Tout ceci se fait de manière complètement automatique.

Même lors du labelling, la consistance d'arc s'applique. Au final, c'est extrêmement performant (en plus d'être extrêmement simple)

Envoyé par Tellmarch

la méthode essai erreur est parfaitement adaptée à la résolution de ce type de probleme, et prolog le fait tres bien, c'est optimisé pour ça.

En fait, ce n'est pas une méthode essai/erreur (sauf à la toute fin, lors du labelling, après que l'on a réduit les domaines des variables et même à ce moment là on continue à faire de la consistance d'arc)

**progfou** · 22/05/2006, 15h38

Une évolution, avec l'Hexadoku ?

**Matthieu Brucher** · 22/05/2006, 15h54

Pas super facile à entrer dans un programme, on ne voit pas les blocs

En tout cas, c'est une évolution en soi, ça fait trè-s longtemps que ça existe et qu'on en fait, c'est juste plus complexe.

**alamanya** · 28/05/2006, 10h36

Bonjour, j'ai écrit en Maple un programme de résolution de Sudoku basé sur un algorithme de retour arrière (backtracking). Il fonctionne correctement et est facilement transposable dans d'autres langages.
A consulter ici: http://alamanya.free.fr/themes/sudoku.htm

Je suis preneur pour le code (dans n'importe quel langage) d'un générateur de grilles de Sudoku,c'est à dire d'un algorithme donnant une solution unique à partir des chiffres initialement disposés dans la grille.

Voici le code du solveur en espérant qu'il sera utile à plusieurs sur ce forum:

sudoku:=array(0..80,[
3, 0, 0, 1, 0, 0, 0, 0, 0,
0, 5, 7, 0, 0, 3, 1, 0, 0,
9, 0, 6, 0, 5, 0, 0, 0, 8,
4, 0, 0, 6, 0, 0, 9, 5, 1,
0, 0, 5, 8, 0, 0, 0, 0, 6,
0, 0, 0, 0, 0, 7, 0, 0, 0,
8, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 4, 2,
0, 0, 0, 0, 7, 1, 0, 0, 0
]):

1° afficher affiche la grille de Sudoku correspondant au tableau T des 81 nombres:
with(plots):

afficher:=proc(T::array)
local L,e,texte,lig,col;
L:=NULL: texte:=NULL:
for lig from 0 to 9 do
if (lig mod 3=0) then e:=5 else e:=1 end if;
L:=L,plot([t,9-lig,t=0..9],thickness=e);
for col from 0 to 9 do
if (col mod 3=0) then e:=5 else e:=1 end if;
L:=L,plot([col,t,t=-0.05..9.05],thickness=e):
if lig<9 and col<9 and T[9*lig+col]>0 then texte:=texte,textplot([col+0.5,9-lig-0.5,T[9*lig+col]],font=[HELVETICA,BOLD,32]) end if;
end do;
end do:
display([L,texte],axes=none)
end proc:

afficher(sudoku);

2°a) index_debut_ligne(i) donne pour résultat l'index de la case située au début de la ligne à laquelle appartient la case d'index i:

index_debut_ligne:=proc(i::nonnegint)
9*iquo(i,9)
end proc:

2°b) index_debut_colonne(i) donne pour résultat l'index de la case située au début de la colonne à laquelle appartient la case d'index i:

index_debut_colonne:=proc(i::nonnegint)
irem(i,9)
end proc:

2°c) ligne(i) donne pour résultat le numéro de la ligne à laquelle appartient la case d'index i:

ligne:=proc(i::nonnegint)
iquo(i,9)
end proc:

2°d) colonne(i) donne pour résultat le numéro de la colonne à laquelle appartient la case d'index i (identique à index_debut_colonne (i)):

colonne:=proc(i::nonnegint)
irem(i,9) # identique à index_debut_colonne(i)
end proc:

2°e) index_debut_bloc(i) donne pour résultat l'index de la première case du bloc 3x3 auquel appartient la case d'index i:

index_debut_bloc:=proc(i::nonnegint)
27*iquo(ligne(i),3)+3*iquo(colonne(i),3)
end proc:

3°a) OK_ligne(T::array,v::posint,i::nonnegint) donne pour résultat une valeur booléenne true ou false selon que le chiffre v figure déjà ou non sur la ligne de la case d'index i du tableau T.

OK_ligne:=proc(T::array,v::posint,i::nonnegint)
local id,x;
id:=index_debut_ligne(i):
for x from id to id+8 do
if T[x]=v then return false end if
end do:
true
end proc:

OK_ligne(sudoku,7,32),OK_ligne(sudoku,5,32);

3°b) OK_colonne[/FONT](T::array,v::posint,i::nonnegint) donne pour résultat une valeur booléenne true ou false selon que le chiffre v figure déjà ou non sur la colonne de la case d'index i du tableau T.

OK_colonne:=proc(T::array,v::posint,i::nonnegint)
local id,x;
id:=index_debut_colonne(i):
for x from id to id+72 by 9 do
if T[x]=v then return false end if
end do:
true
end proc:

OK_colonne(sudoku,5,32),OK_colonne(sudoku,1,32);

3°c) OK_bloc(T::array,v::posint,i::nonnegint) donne pour résultat une valeur booléenne true ou false selon que le chiffre v figure déjà ou non dans le bloc de la case d'index i du tableau T.

OK_bloc:=proc(T::array,v::posint,i::nonnegint)
local id,x,y;
id:=index_debut_bloc(i):
for x from 0 to 2 do
for y from 0 to 2 do
if T[id+9*x+y]=v then return false end if
end do
end do:
true
end proc:

OK_bloc(sudoku,3,32),OK_bloc(sudoku,8,32);

3°d) OK(T::array,v::posint,i::nonnegint) donne pour résultat false si i=81 et sinon donne pour résultat une valeur booléenne true ou false selon que le chiffre v peut être placé ou non dans la case d'index i du tableau T, conformément à la règle du jeu de Sudoku

OK:=proc(T::array,v::posint,i::nonnegint)
if i=81 then return false
else OK_ligne(T,v,i) and OK_colonne(T,v,i) and OK_bloc(T,v,i) end if
end proc:

OK(sudoku,2,32),OK(sudoku,4,32);

4° suivant(T::array,i::nonnegint) donne pour résultat:
i si la case d'index i du tableau T contient 0, ou sinon l'index de la prochaine case modifiable suivant la case d'index i du tableau

suivant:=proc(T::array,i::nonnegint)
local id;
id:=i;
while T[id]<>0 do
if id<80 then id:=id+1 else return 81 end if
end do:
id
end proc:

5° index_fixes(T) donne pour résultat la liste des index des cases fixées du tableau T:

index_fixes:=proc(T::array)
local k,f;
f:=NULL;
for k from 0 to 80 do
if T[k]>0 then f:=f,k end if
end do;
[f]
end proc:

index_fixes(sudoku);

6° solution(T) donne pour résultat la solution du sudoku T ; la procédure fonctionne sur un algorithme de retour arrière (backtracking) :

solution:=proc(T::array)
local index,valeur,fixes;

index:=0: valeur:=0: fixes:=index_fixes(T):
while index<81 do
index:=suivant(T,index):
valeur:=valeur+1:
if OK(T,valeur,index) then
T[index]:=valeur: valeur:=0:
else
if valeur=9 then
valeur:=0:
do
T[index]:=0:
index:=index-1:
while member(index,fixes) do
index:=index-1
end do:
if index<0 then
error "Pas de solution trouvée pour ce sudoku."
end if;
if T[index]<9 then
valeur:=T[index]: T[index]:=0:
break
end if:
end do
end if
end if:
end do:
eval(T)
end proc:

afficher(solution(sudoku));

**méphistopheles** · 28/05/2006, 11h30

est-ce que ceci t'irais comme type de génération (j'ai deux methodes. regarde le prog et dis moi ce que t'en pense.

salut

**dongnold** · 03/03/2006, 17h44

Je suis en train de faire un jeu de SUDOKU. Au niveau d'algorithme, je ne sais pas comment générer un grid de SUDOKU en fontion du niveau de difficulté. Quelqu'un a des infos là-dessus ?