Discussion :

[Matthieu Brucher]

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]

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]

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]

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]

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]

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]

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:

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)

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)

[dongnold]

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 ?

[Tellmarch]

oui il y a déja eu un débat la dessus, tu peux regarde le post http://www.developpez.net/forums/viewtopic.php?t=399772[/url]

[reggae]

Cherches sur Codes-Sources par exemple, ou sur le net, prends deux minutes pour trouver des infos intéressantes.
Ensuite le lien proposé te permettra d'améliorer ton algo.

Voici un début de réponse:
http://fr.wikipedia.org/wiki/Sudoku

[progfou]

Une évolution, avec l'Hexadoku ?

[Matthieu Brucher]

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]

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]

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

[alamanya]

Oui, peux tu donner ici ton code pour le générateur?

[méphistopheles]

Envoie-moi un mail ou contacte moi par msn. Je préfere expliquer le principe que donner un code tout fait ce qui est inutile.

[Bavimo]

Bonjour;
Si cela peux t'aider j'ai fait 2 programmes en c pour résoudre les sudoku :
- Un code "brut" qui utilise seulement une méthode récursive.
- Un code qui imite une manière humaine de résoudre sur le papier :
Méthodes : Inclusive , Exclusive et Multi-choix
Ces deux logiciels sont courts et en mode commannde.
je mets à disposition les sources et les exécutables à http://www.i2i.fr
Toutes les grilles sont résolubles quelle que soit leur niveau.
Si quelqu'un à un autre concept que les trois cités ci dessus je suis preneur.
Christian
Je recherche des énoncés de grille de 25 sur 25.... pouvant résoudre ceux ci.

[gargle]

salut

j'ai trouvé ce site et cette méthode super, je ne sais pas si c'est un repost, mais ca vaut le coup d'oeil :

ICI

PS : c'est en anglais.
@++

[Kyara]

Bonjour !! J'aimerais également faire un programme qui résout n'importe quel sudoku, le seul hic, c'est que je sui débutante en prog (3 mois )et que je ne connais uniquement le langage ADA, donc en gros je ne comprend rien à ce que vous avez pu écrire avant ? Quelqu'un aurait une version algorithmique très détaillée ? voir un langage qui se rapporche d'ADA, ou alors un tuteur perso qui pourrait m'expliquer en français ?
Merci de votre aide

[random]

Bonjour,

Dire qu'une grille de SUDOKU a une seule solution est simplement absurde. Le nombre de solutions dépend du nombre de chifres connus au départ

Avec un bémol les règles prévoient que les chiffres connus au départ n'autorisent qu'une solution

D'ailleurs quand la solution est publiée elle ne comporte qu'une réponse.

Un problème de Sudoku qui autorise plusieurs réponses n'est pas un problème de Sudoku

une grille vierge autorise un grand nombre de problèmes mais ce n'est pas un
problème de Sudoku

ce que tu nous proposes c'est un problème d'échec avec l'échiquier mais sans les pièces.