Discussion :

[Matthieu Brucher]

Deux questions :

Combien existe-t-il de grilles complètes valides au Sudoku ?
Combien existe-t-il de grilles incomplètes donnant une et une seule solution ?

Sur wikipedia, il y a le nombre de grilles uniques, c'est assez énorme. Ensuite le nombre de grilles avec solution unique... il y en a pas mal, au moins autant que de grilles uniques par un coefficient important.

[Médiat]

Merci du renseignement.
Nombre de grilles complètes aux symétries près : 5 472 730 538, ce n'est pas tant que cela.

Pas de réponse à la deuxième question

[Matthieu Brucher]

Un début de réponse, il faut au moins 8 cases à placer sur la grille, puis il faut pouvoir la résoudre - point à éclaircir -. De plus, il faut au moins 1 case par sous ensemble qui soit placée, mais cela ne permet pas de déterminer de manière unique la grille à utiliser - il y a 387420489 solutions pour placer un nombre par carré par exemple, sachant que certaines grilles se résolvent sans élément dans certains carrés -, il faut encore au moins 2 cases à placer.
Le nombre minimum de cases déjà placées est de 17 ou 18 sur le net, donc il reste encore les autres cases à placer, sachant que chacune de ces grilles résultantes est une grille de Sudoku valide.

[random]

a remarquer que lorsque tu as rempli un carré
tu véhicules pour les cellules des lignes dont il font partie 3
information pour six cellules sur 3 lignes
et autant en colonne
=3*6*3*2=144
j'ai coutume de noter le degré de résolution d'une grille
d'après la somme des possibilités
pour une grille vierge je note une cellule non renseignée
"123456789" et son poids vaut nombre de caractères de
"123456789"=9 j'ai donc un poids de départ de 729 (9*9*9)
et un poids d'arrivée de 81 le poids d'un sudoku vierge est ainsi
de 729-81= 648 et le poids après un carré rempli est de 468 c'est dire que
un carré =1/9 (11%) des informations directe donne 27.77% de l'information totale
pour deux carrés en diagonale 22% directe 53% totale
pour deux carrés contigus 22%directe 47% totale

si on rentre les chiffres comme des dames non en prise

en cherchant à chaque fois le minimum d'interaction au début
l'information véhiculée ne donne pas grand chose et semble
se propager par mode mode additif décroissant
puis survient un seuil où l'information se propage sur le mode multiplicatif croissant

en fait on peut aussi considérer deux événements
diminution de l'incertitude
certitude
la diminution de l'incertitude ne pèse guère plus que son poids
si j'ai une case notée "123456789" et si je décide qu'elle ne peut
contenir de trois je gagne 1/9 de son information et je ne transmets probablement rien sauf si la ligne (ou la colonne ou le carré) contenant la cellule présentait deux opprtunités pour le 3
par contre la certitude que dans cette cellule se trouve un 2 me permet de gagner 8/9 de son poids et transmet dans les cellules en relation un poids de 1 (absence de 2)

le seuil de résolution doit se produire quand la diminution de
l'incertitude est égale à la certitude, à partir de ce moment on arrive
à des conséquences de niveau 2, qui peuvent entrainer des conséquences de niveau supérieur

quand on résoud un problème le solver pour la dernière certitude apportée
résoud toute la grille avec des poids qui font couremment 200 ou 300 dans ma notation

[Matthieu Brucher]

Intéressant comme notation
Une grille dite de niveau facile a combien avec ta notation ?

[2Eurocents]

Pour revenir à un point du début ... j'ai moi aussi écrit mon petit solveur de sudoku ( en Perl ), avec une méthode sans hypothèse (et donc sans backtrack).

Il me satisfait dans la plupart des cas, mais bloque sur une grille, de niveau "diabolique", que j'ai pu, par contre, résoudre à la main. Je n'arrive pas à remettre le doigt sur l'élément qui m'a permis de le résoudre ... probablement une hypothèse, justement, que je tente d'éviter dans mon programme.

Ceux qui ont des solveurs sans backtrack peuvent ils me dirent s'ils trouvent la solution de :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
. . 8 2 . . 9 . .
. 9 7 3 . . 2 4 .
3 . . . . . . . .
. . 3 . 8 5 6 . 1
. . . . . . . . .
7 . . 1 3 . 8 . .
. . . . . . . . 8
. 4 6 . . 3 7 2 .
. . 9 . . 2 4 . .

Mon solveur reste obstinément bloqué à :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
4 . 8 2 . . 9 . .
. 9 7 3 . 8 2 4 .
3 . 2 . . . . 8 .
9 2 3 4 8 5 6 7 1
. . . . 2 . . . 4
7 . 4 1 3 . 8 . 2
2 . . . . . . . 8
. 4 6 . . 3 7 2 9
. . 9 . . 2 4 . .

Ou si vous préférez, je peux vous copier la sortie de mon script sur la dernière itération, avec les possibilités restantes de chaque case.

[Matthieu Brucher]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
4 1 8 2 6 7 9 5 3
5 9 7 3 1 8 2 4 6
3 6 2 5 9 4 1 8 7
9 2 3 4 8 5 6 7 1
6 8 1 7 2 9 5 3 4
7 5 4 1 3 6 8 9 2
2 7 5 9 4 1 3 6 8
1 4 6 8 5 3 7 2 9
8 3 9 6 7 2 4 1 5

[random]

si j'inhibe le backtrack je reste bloqué
je vais essayer de travailler à partir de ce blocage
pour une évaluation sans essai

[2Eurocents]

si j'inhibe le backtrack je reste bloqué

C'est ce que je craignais ... Tu en restes au même point de blocage que moi ?

La solution donnée par Miles est celle que j'ai obtenu à la main, mais j'ai dû passer par une hypothèse pour y arriver.

je vais essayer de travailler à partir de ce blocage
pour une évaluation sans essai

Moi aussi ... mais c'est peut être ce qui fait l'aspect "diabolique" de la grille.

[gaetanc15]

Bonjour a tous
j'ai pas lu tout le sujet
je sais pas si vous avez intergré ces regles http://naxos.fr.free.fr/sudoku/hints.html
dans vos algos.
J'y travaille en Vb (connais rien d'autre) chaud pour mon niveau.
J'en suis juste a respecter les regles de base pour l'instant ca marche.
J'intergre les autres regles si j'y arrive.

Sinon ma methode de départ: on rempli toutes les cases par 123456789
et on enlève ce qui va pas.

Bonne continuation

[Matthieu Brucher]

La solution donnée par Miles est celle que j'ai obtenu à la main, mais j'ai dû passer par une hypothèse pour y arriver.

Je ne fais pas d'hypothèse dans mon programme, il n'y a que l'implémentation des 3 règles précédentes...

[random]

miles pour la règle des bi(tri, tétra,quinqua)grammes

tu l'as bloquée à 2 ou tu la laisses se dérouler ?

[Matthieu Brucher]

Je la fais tourner jusque la partie entière du nombre d'élément dans un regroupement divisé par 2, soit donc 4 pour le jeu 9*9

[cedico]

Salut,

Je rattrape cette conversation avec un peu de retard... Juste pour vous dire qu'il y a 3 mois, j'ai fait un programme en Delphi qui permet de résoudre le Sudoku.
Lorsque je vois certains messages sur le temps de réponse, je suis quand même étonné car mon programme sait résoudre tous les problèmes difficiles / expert en 1 seconde (environ).

Mon programme traite 2 méthodes au choix : (désolé je ne suis pas expert en maths, je n'aurais donc pas d'explication à vous donner sous forme de formules :-)

- 1 : qui consiste à faire réfléchir le programme comme la méthode conseillé dans les bouquins sudoku, (a savoir par groupe de 3 carrés)

-2 : qui consiste bêtement à résoudre le sudoku de manière récursive.
je place le 1er chiffre possible dans la case 1, puis je teste toutes les combinaisons possibles dans les autres cases de manière récursive. Dés qu'un niveau est en échec, je remonte au niveau précédent pour tenter une nouvelle combinaison.
Je ne sais pas si c'est super optimisé mais en tous les cas, ça fonctionne à tous les coups en 1 seconde.

[Matthieu Brucher]

C'est ce qu'on trouve dans la littérature sur le net, le jeu peut être résolu très rapidement, même par récursion.
J'ai pas trop vu de messages où la résolution était longue ???

[cedico]

Bah..., je faisais surtout allusion au 1er message :

Hélas mon algorithme n'est pas assez performant, en effet il trouve la solution des niveaux facile et moyen, quelques difficiles mais aucun diabolique.

Mais bon c'est pas très grave...

Vu qu'il y a des pros de l'agorithmie, j'ai posté un message dans la section algos sur ce forum, peut-être auras-tu de bonnes idées à me conseiller ? :-)

a+
Cédric

[Matthieu Brucher]

A part les 3 règles, il faudrait voir pour implémenter la formation en X ou l'espadon - swordfish -, mais c'est anecdotique.
Il faudrait voir sur les exemples non solvables ce qu'on doit faire à la main pour y arriver.

[cedico]

En fait je faisais allusion à mon sujet posté tout à l'heure :

"Arbre de recherche : quel algo conseiller ?" ici : http://www.developpez.net/forums/viewtopic.php?t=424003

J'ai besoin de conseils pour optimiser un arbre de recherche...


Cédric

[Matthieu Brucher]

Dabs le cas ici, déjà tu fais un parcours en profondeur, le truc pour faire de l'alpha-beta ou du minimax, c'est réussir à mettre une fonction de coût, tu peux utiliser le coût qui a été présenté ici, mais je ne suis pas sûr que ce soit efficace.

[cedico]

Le soucis est que mon jeu ce joue seul, il n'y a pas d'opposant...
Et quelqu'un du forum m'a expliqué hier que ces 2 méthodes étaient surtout utilisées lorsqu'il y avait un opposant dont on évalue la réaction probable...
Alors j'ai l'impression que dans mon cas, ça ne sera pas vraiment adapté...
Concernant le coût, merci pour l'idée, peut-être que je peux améliorer mon algo avec une notion de côut...