Résolution de sudoku

[leon1789]

Bonjour

Sous le prétexte de résoudre le sudoku suivant (qui est pour moi le plus difficile que j'ai étudié), j'ouvre un topic parlant de résolution de sudoku, de méthodes "humaines" (i.e. sans backtracking), de programmes, etc.

Voici le tableau des candidats (j'espère que le système de coordonnées plaira à un maximum de gens)

Code: Tout sélectionner

Silver Plate (source http://www.sudoku.com/boards)

     1     2     3       4       5      6       7      8      9
+--------------------+---------------------+---------------------+
|      1   458  4689 |   3568  23589 35689 |    2349   239     7 | A
|    589     2   789 |      4 135789 35789 |     139     6   189 | B
|   4689   478     3 |   1678  12789  6789 |       5   129 12489 | C
+--------------------+---------------------+---------------------+
|  23568     9 12678 |  13578      4  3578 |   12367 12357  1256 | D
|    358 13578   178 |  13578      6     2 |    1379     4   159 | E
|  23456 13457 12467 |      9   1357   357 |       8 12357  1256 | F
+--------------------+---------------------+---------------------+
|   2489   148     5 |    678    789 46789 |  124679  1279     3 | G
|    349     6   149 |      2   3579 34579 |    1479     8  1459 | H
|      7   348  2489 |   3568   3589     1 |    2469   259 24569 | I
+--------------------+---------------------+---------------------+


Dans une autre discussion, Ben314 a dit qu'il avait un programme qui analyse les sudokus, en fabrique de nouveaux (la difficulté est à choisir) et qui aide à les résoudre. Fatal error est aussi intéressé... Bref.

Ta grille a bien une unique solution et il n'y a aucune case qu'un raisonnement "direct" permet de remplir (et il y a 15 raisonnement possibles conduisant à deux choix...)

Qu'entends-tu par "raisonnement direct" et par "raisonnement conduisant à deux choix" ? Est-ce possible de voir ces couples de choix ? ...et même les raisonnements qui aboutissent à ces choix ?

Par ailleurs, peux-tu nous expliquer rapidement dans les grandes lignes ce que ton programme recherche pour aider à la résolution ?

[Ben314]

Bon, est ce que cela fonctionne...
http://www.megaupload.com/?d=0977YK8B

Ca a l'air de marcher...
Le programme a été fait avec Borland C++ sur une machine ancienne donc, il risque de falloir mettre "simuler window ???" sur certaines machines rapides (je pense que Fatal Error sera plus précis que moi sur ce sujet...)
Quelque remarques :
Je n'ai jamais "complètement" fini le programme : j'avais en tête de pouvoir imprimmer les grilles (-> non implémenté) et de mettre un truc marrant lorsque l'on termine une grille avec comptabilisation du temp (-> implémenté) et du nombre de fois que l'on à triché avec le bouton SOS (-> non implémenté). Je me demande s'il n'y as pas un troisième truc que je n'ais pas fini...
Si il y en a qui veulent les sources, je le donne pareil, sauf que c'est nettement plus gros et que c'est tapé par un GROS BIDOUILLEUR (moi) donc pas forcément super lisible (c'était mon premier programme en C++, il y a environ 5 ans, et c'est le seul que j'ai fait : pas convaincu...)
Je me rappelle plus si y'a pas aussi une partie en assembleur (les sources sont sur ma vieille machine)

[Anonyme]

Je suis aussi intéressé par l'algorithme que tu as implémenté.

[bombastus]

Il a l'air de tourner sous XP.

Une petite question : quelle librairie as-tu utilisé pour l'interface?

[Doraki]

Comment as-tu éliminé la possibilité d'un 1 en E9 ? Ah ben ton sudoku a changé entre les sujets.

Mon solveur mets 2 secondes à résoudre ce sudoku, c'est beaucoup trop.

(aussi, comme il y a un nombre fini de sudokus de taille 9, mon solveur favori que je ne coderai jamais car il est trop long à écrire est capable de déterminer la solution directement après avoir lu le problème)

[leon1789]

Comment as-tu éliminé la possibilité d'un 1 en E9 ? Ah ben ton sudoku a changé entre les sujets.

Oui, dans le premier sujet, je me suis placé dans un contexte un poil simplifié pour illustrer ce que je voulais dire.

Mais ici, j'ai mis la grille d'origine (sans aucune simplification artificielle).

Mon solveur mets 2 secondes à résoudre ce sudoku, c'est beaucoup trop.

Ah toi aussi, comme Ben314, tu as un solveur.

Que veux-tu dire par "2 secondes, c'est beaucoup trop" ?

Quelle(s) méthode(s) est (sont) utilisée(s) dans ton programme ? Il y a-t-il du backtracking dedans ?

[leon1789]

Qu'entends-tu par "raisonnement direct" et par "raisonnement conduisant à deux choix" ? Est-ce possible de voir ces couples de choix ? ...et même les raisonnements qui aboutissent à ces choix ?

Ok, je crois comprendre que par "raisonnement direct", il s'agit de la règle de base : chaque chiffre apparaît une et une seule fois par ligne/colonne/bloc.

Pour les couples de choix, je vois aussi, les cases à seulement deux candidats (il n'y en a pas dans cette position de départ) ou un candidat sur uniquement deux cases :
a5=2 ou c5=2,
c9=4 ou a7=4,
b1=5 ou a2=5,
h1=3 ou j2=3,
b3=7 ou c2=7,
c1=6 ou a3=6,
e9=9 ou e7=9,
b9=8 ou c9=8,
h3=1 ou g2=1,
g1=2 ou j3=2,
g6=4 ou h6=4.

C'est tout. C'est effectivement peu.

EDIT : Je ne comprends pas en fait, car le programme de Ben314 indique 15 choix doubles. :briques: ah si, le programme de Ben314 doit compter avec multiplicité...

[leon1789]

L'algo de Ben314 fonctionne sous windows 7 également :zen:

[Ben314]

Face à une grille donné (vide, à moitié remplie ou presque pleine) mon "solveur" fait de type de "calcul" :
a) Pour chacune des 81 case, il regarde la liste des chiffres possible dans cette case en fonction de ceux déjà présents dans les trois zones (ligne, colonne et carré) dont fait partis la case
b) Pour chacune des 27 zones et chacun des chiffres non déjà présent dans la zone, il regarde quels sont les emplacements possibles pour ce chiffre dans la zone.

a') Une fois cela fait, si un certain nombre de ces raisonnement conduisent à une seule possibilité, il remplit la (les) case(s) correspondantes : c'est une "étape" de la résolution et la dificulté d'une grille est compté en "nombre d'étapes" pour trouver la solution. Les grilles de niveau faible et moyen que l'on trouve dans les bouquins ne demandent que des étapes de ce type.
b') Si aucun des raisonement ne conduit à l'unicité, il choisi la configuration dans laquelle il y a le moins de choix possible et les essaye les uns aprés les autres. Pour le calcul de dificulté, il fait la somme des étapes nécéssaires à chacun des "sous-calcul" : ici, il y a une certaine part aléatoire car le choix de l'endroit où on fait les essais risque de modifier considérablement le nombre d'étapes...

Le sous programme faisant ces calculs est extrêmement rapide (je pense de l'ordre du 10em de seconde pour trouver une soluce dans le pire des pire des cas) Lors de l'appel au sous programme, on peut spécifier un certain nombre de paramètres : recherche d'une solution et point barre ou comptage du nombre de soluce (pour vérifier qu'il n'y en a qu'une).
Une autre option utile est de demander au sous programme de tirer au hazard les valeurs lorsqu'il a le choix : ça le ralenti pas mal (générateur aléatoire) mais cela permet, si on lui demande de "résoudre" une grille vide, de fabriquer une grille pleine cohérente et aléatoire. C'est de là qu'il part pour fabriquer de nouvelles grilles. Il enlève ensuite des chiffres en vérifiant à chaque fois que la soluce reste unique (don en réappelant le sous programme) j'usqu'à ce que li niveau de difficulté demandé par l'utilisateur soit atteint...

Pour ce qui est des librairies utilisées, il y a celle livrées avec dans le .zip et, de mémoire, j'avais utilisé une bonne parties des librairies du BC++ mais seulement pour la partie interface et graphique que j'avais essayé de "chiadder"...

P.S. je vais récupérer les sources sur mon autre machine...

[leon1789]

Ok, si je comprends bien, ton programme fait du backtracking sur les choix doubles.

[Ben314]

Ok, si je comprends bien, ton programme fait du backtracking sur les choix doubles.

Tout à fait (modulo que je comprenne bien le sens de 'backtracking...)
Dan la pratique, il me semble me rapeller que les grilles les plus dures que j'ai trouvé (bouquin ou fabriquées par le programme) demandent au max trois/quatre essais, et en général chaque "essai" ne comporte que deux sous cas.
Si tu veut tester le programme, tu lui rentre une grille, puis à l'aide du bouton SOS (niveau 3 et niveau 5) tu lui demande quelles déductions il fait sur la grille.

Bon, sinon, j'ai fini par récupérer les sources du programme si ça interesse quelqu'un (si un vrai informaticien les regarde, il va hurler....) :
http://www.megaupload.com/?d=LZHXRQZ6
(Les calculs sont fait par sudo_calc.asm)

[Ben314]

EDIT : Je ne comprends pas en fait, car le programme de Ben314 indique 15 choix doubles. :briques: ah si, le programme de Ben314 doit compter avec multiplicité...

Mon programme donne aussi des "choix doubles" du type "dans le carré (a) (haut-gauche) le 5 doit être dans une des cases B1 A2(avec les notation du programme qui sont hélas l'inverse des tiennes...)
Dans le cas de "choix simple" cela peut conduire à quatre type de raisonnements conduisant à la même conclusion et dans ce cas, il compte '4' pour le nombre d'emplacement où il n'y a qu'un seul choix...

[leon1789]

Si je comprends bien, ton programme considère une fois le doublet 2 en A1-B2 car doublet dans le bloc carré,
mais deux fois le doublet 2 en A5 et C5 (avec mes notations) car c'est un doublet à la fois dans la colonne et dans le bloc carré.

[Ben314]

Si je comprends bien, ton programme considère une fois le doublet 2 en A1-B2 car doublet dans le bloc carré,
mais deux fois le doublet 2 en A5 et C5 (avec mes notations) car c'est un doublet à la fois dans la colonne et dans le bloc carré.

Pour ton premier exemple, je vois pas trop (tu parle toujours de ta grille ?)
Pour le second exemple, il considère effectivement qu'il y a deux "raisonnements" différents qui conduisent... au même résultat :
1) "Dans le carré (b) (haut-millieu) le chiffre 2 doit être dans l'une des cases A5 ou C5"
2) "Dans la colonne 5 le chiffre 2 doit être dans l'une des cases A5 ou C5"

Je sais pas si cela te parrait "bizare" comme façon de compter, mais vu l'algo. de recherche de solution, c'est comme ça qu'il 'raisonne' et, au fond, je trouvais que c'était pas si con que ça, car il me semble que ça veut dire "qu'à la main", tu risque de te rendre compte plus vite de ce "choix double" que d'un autre "choix double" qui ne s'obtient que par un seul type de raisonnement.

Temps que j'y pense, il n'y a (évidement) aucune "doc" livrée avec. J'espère que tout est assez "naturel" sauf peut-être quelques détails :
- On peut saisir les chiffres à la souris en "attrapant" la case et en faisant "défiler" un pavé numérique sous-jacent à la case.
- Les deux sous-fenètres contenant les boutons sont déplaçables.
- La "zone de texte" permet de rajouter un commentaire sur une case qui devrait apparaitre à chaque fois que la souris passe sur la case, l'idée est de mettre par exemple la liste des possibilités de la case...
- Les boutons colorés servent de même à aider à la résolution (points jaunes pour signifier le chiffre 7 et là ou là...)
- l'option Fichier-Impression n'est pas du tout implémanté...
- Toutes les "indics" (SOS et intégrée) son affichés dans la ligne du bas de la fenètre, mais si on est en 1920x1200, c'est... tout petit !

[leon1789]

Pour ton premier exemple, je vois pas trop (tu parle toujours de ta grille ?)
Pour le second exemple, il considère effectivement qu'il y a deux "raisonnements" différents qui conduisent... au même résultat :
1) "Dans le carré (b) (haut-millieu) le chiffre 2 doit être dans l'une des cases A5 ou C5"
2) "Dans la colonne 5 le chiffre 2 doit être dans l'une des cases A5 ou C5"

C'est bien ça, on est d'accord.

Je sais pas si cela te parrait "bizare" comme façon de compter, mais vu l'algo. de recherche de solution, c'est comme ça qu'il 'raisonne' et, au fond, je trouvais que c'était pas si con que ça, car il me semble que ça veut dire "qu'à la main", tu risque de te rendre compte plus vite de ce "choix double" que d'un autre "choix double" qui ne s'obtient que par un seul type de raisonnement.

Oui, pourquoi pas :id:

[leon1789]

Je suis preneur d'idées (en dehors de la récursivité) qui permetraient d'éliminer des candidats. :hein:

[Doraki]

Que veux-tu dire par "2 secondes, c'est beaucoup trop" ?

Ca veut dire qu'il est effectivement dur par rapport à ceux que je lui ai donnés à l'époque.

C'est un vieux programme incompréhensible que j'ai écrit il y a des années je sais plus comment il fait ses déductions.
Il résout ta grille en faisant 10 bons choix consécutifs (mais il cherche pas à faire des petits choix comme le programme de Ben, il prend la 1ère case non déterminée et il met un numéro dedans, sans regarder les autres).

Tout à l'heure j'ai voulu regarder l'arbre des possibilités qu'il faisait en partant de ta grille pour jauger la difficulté du sudoku (et la prouesse de déduction de mon programme) mais après quelques heures et 30000 grilles il m'a fait un stack overflow =[.

Sinon j'crois qu'on avait déjà un sujet sur les sudokus y'a longtemps.

[leon1789]

Ca veut dire qu'il est effectivement dur par rapport à ceux que je lui ai donnés à l'époque.

C'est un vieux programme incompréhensible que j'ai écrit il y a des années je sais plus comment il fait ses déductions.
Il résout ta grille en faisant 10 bons choix consécutifs (mais il cherche pas à faire des petits choix comme le programme de Ben, il prend la 1ère case non déterminée et il met un numéro dedans, sans regarder les autres).

Tout à l'heure j'ai voulu regarder l'arbre des possibilités qu'il faisait en partant de ta grille pour jauger la difficulté du sudoku (et la prouesse de déduction de mon programme) mais après quelques heures et 30000 grilles il m'a fait un stack overflow =[.

:ptdr:

ok.

On peut faire moins de "bons choix" pour arriver à une solution facile : en posant (par exemple) B6=3 et F5=7, on obtient une grille d'un niveau banal.
Je sais qu'une seule devinette ne suffit pas pour cette grille, et que deux est bien le minimum. Cela étant, pour que je sois complètement satisfait, il faudrait prouver que B6=3 et F5=7 avant de terminer la grille... un peu comme si on voulait prouver l'unicité du résultat.

Sinon j'crois qu'on avait déjà un sujet sur les sudokus y'a longtemps.

Peut-être veux-tu parler de celui-ci http://www.maths-forum.com/showthread.php?t=79408 ?

Le problème que je me pose, c'est de pouvoir résoudre cette grille sans récursivité, en établissant des propriétés établies sur la grille initiale (en essayant telle hypothèse raisonnable) et d'agiter ces propriétés pour en faire sortir des éliminations de candidats... un truc comme ça. :hein:

[Doraki]

On peut faire moins de "bons choix" pour arriver à une solution facile : en posant (par exemple) B6=3 et F5=7, on obtient une grille d'un niveau banal.

Avec ça tout ce qu'il me trouve c'est le 5 et le 8 dans le carré du milieu, mon programme doit pas faire des raisonnements suffisamment sophistiqués. D=

[Ben314]

Je suis preneur d'idées (en dehors de la récursivité) qui permetraient d'éliminer des candidats. :hein:

J'ai trouvé ce site qui propose plusieurs types de raisonnements ainsi qu'un programme appliquant certain de ces raisonnements...
http://www.mots-croises.ch/Manuels/Sudoku/