Résolution de sudoku

[fatal_error]

bonjour,

bon, il est clair que la brute force c'est trivial, aucun intérêt pour imiter le comportement humain.
En premier lieu avant que j'oublie, ya un moment Doraki tu affirmes que tu peux résoudre le sudoku cash en un tour. J'aimerais bien savoir comment. Je crois que sur le site qu'a trouvé Ben314 ca annonce (au moins) un milliard de solutions. Donc la méthode de "dispatchage" avec des "classes" type de grille marche pas. (genre aiguiller vers un intervalle de solution en fonction de la grille présente). Aussi je veux bien savoir c'est quoi l'idée.

Sinon, là où c'est intéressant ( à part trouver des méthodes pour résoudre un sudoku ), c'est de confronter l'utilité des méthodes d'une part, et d'estimer la diffculté d'un sudoku d'autre part.

Pour la confrontation des méthodes une idée que j'ai ( je testerai peut etre a l'occase ), c'est de tester les différents algo betement les uns apres les autres. Je suis assez tenté pour dire que le meilleur algo est celui qui enlève le plus de candidats. Mais pe que ceux là marchent lorsque la grille est en stade final uniquement. ( basé sur l'expérience (en cours), vers la fin, ca va plus vite, alors qu'en milieu de sudoku faut plus cogiter).
Le motif de savoir lequel est le meilleur, c'est de faire une analyse de la grille en largeur pour "déblayer" un maximum de candidats, puis apres d'attaquer avec les algos plus fins pour les eliminations de candidats plus violentes.

En ce qui concerne la difficulté, je pense que l'on pourrait la coupler avec les diffcultés des algos. C'est a dire :
Supposons que l'on trie les algo : 1 celui qui élague le plus, 10 le dernier.
Bon, lorsqu'on utilise l'algo 1 et qu'on supprime n candidats, la difficulté(actuelle) vaut n
Lorsqu'on utilise l'algo 10 et qu'on supprime n candidats, la difficulté vaut 10*n

Bien sur, on peut ajuster le calcul effectué pour la difficulté (par autre chose qu'une multiplication). Il faut aussi s'assurer qu'en utilisant une autre méthode la difficulté ne varie pas énormément. De ce point de vue là, je miserais bien sur l'hypothèse suivante :

Plus on élague de candidats, et plus la résolution de la grille se fait facilement. Bien sûr, il y a des cases clés qui ne sont pe accessibles qu'avec des algos compliqués mais qui une fois modifiée permettent de simplifier grandement le sudoku.
1) l'oeil avertit ne les verras probablement pas.
2) il faudra quand même équilibrer les mesures de difficultés pour ces éliminations de candidats! Mais comment?

On peut aussi y coupler avec la profondeur cad le "nb d'étapes" de Ben314.
Ce ne sont que des idées. Par exemple :
a chaque nombre d'étape ( = reparcourt de la grille ), on attribue un coeff sur le nombre d'étape (qui augmente avec celui-ci). Cela implique que lors d'un cas comme celui du dessus,
Si on élague plein, puis précis dérriere,
La difficulté sera moindre que
Si on élague peu et qu'on fait un massacre derriere ( vu qu'on pondére par plus de candidats éliminés)

Bref, je suis preneur d'idées.

PS : j'ai essayé de lire ton code Ben314, mais je me suis perdu entre l'interface graphique, les fichiers de borderLand et les algo vraiment utiles. Je vais essayer de voir ca calmement (les lendemains de soirée c'est jamais évident, ni les soirs de DS... :marteau: )

[Doraki]

un intérêt pour imiter le comportement humain.
En premier lieu avant que j'oublie, ya un moment Doraki tu affirmes que tu peux résoudre le sudoku cash en un tour.

J'ai pas dit que c'était pratique ni qu'on avait assez de place ou de temps dans l'univers pour l'écrire.

Je dirais que la difficulté d'une grille est liée soit à la complexité des méthodes de déduction nécessaires pour la compléter (dans la limite du raisonnable, les déductions);
Soit au nombre de choix à faire pour y arriver (encore une fois ça dépend des méthodes de déductions qu'on est prêt à utiliser)

[leon1789]

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=

Effectivement, le 5 est le seul candidat en F6, puis le 8 seul candidat en D6, ok.
Ensuite, il y a le 7 en B3 : B3 est la seule position possible pour le 7 en ligne B.

Il y a deux règles de base :
(R1) chaque case contient un chiffre,
(R2) chaque chiffre est dans une case.

Ci-dessus, le 5 et le 8 sont placés par la règle R1, le 7 est placé par la règle R2.

Visiblement, ton programme ne contient que la règle R1.

[leon1789]

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/

Oui.
Les techniques amusantes exposées sur ce site sont suffisantes pour résoudre les sudokus "diaboliques" que l'on voit dans les journaux.
Mais ces techniques ne donnent rien pour la grille silver plate. :triste:

[Doraki]

Ah en effet. Le programme faisait des trucs compliqués mais pas ça x).
Avec les deux, il déduit bien le reste de la grille (yay).
Faut que je l'intègre convenablement, et puis je re-regarderai si l'arbre des choix n'est pas trop trop gros.

(y'a une grille gold plate ?)

[leon1789]

y'a une grille gold plate ?

:we:
Pas de gold plate à ma connaissance, mais il y a une grille golden nugget (venant toujours de http://www.sudoku.com/boards )

Code: Tout sélectionner

+---------------------+--------------------+---------------------+
|  25678 14568 124567 |    268  2467  4678 |    1247     3     9 |
|  26789  4689   2467 |  23689 23467     1 |     247  2467     5 |
|   2679  1469      3 |    269     5  4679 |       8 12467  1247 |
+---------------------+--------------------+---------------------+
|    235   345      8 |    135     9   357 |  123457  1247     6 |
|   3569     7    456 |  13568   136     2 |   13459  1489  1348 |
|      1  3569    256 |      4   367 35678 |   23579  2789  2378 |
+---------------------+--------------------+---------------------+
|    367   136      9 |   1236     8   346 |   12347     5 12347 |
|   3578     2    157 |   1359   134  3459 |       6 14789 13478 |
|      4 13568    156 |      7  1236  3569 |    1239  1289  1238 |
+---------------------+--------------------+---------------------+


Elle est aussi ignoble que l'autre. :mur: :mur:

[Ben314]

Pour fatal_error : l'algo de résolution est entièrement dans "sudo_calc.asm"
Tout le reste n'est que l'enrobage graphique.

Pour Doraki (et léon ?) la grille "silver plate" est considéré comme de "niveau max" par mon programme (255) et la grille modifiée B6=3 et F5=7 comme façile (13) : il la résoud avec les étapes suivantes :
I) Seul chiffre possible en F6 =5 ; Seule poss. pour le 7 sur la ligne B = B3
II) Seul chiffre possible en D6 =8 ; Seule poss. pour le 7 sur la colonne 2 = E2
III) Seule poss. pour le 5 sur la colonne 2 = A2
IV) Seule poss. pour le 5 sur la colonne 4 = I4 ; Seule poss. pour le 5 sur la ligne B = B5
.
.
.
et il lui faut 13 étapes.

Pour Léon : où a tu trouvé la grille "silver plate" et quel test faire pour voir si une grille est "trés dure" (j'aimerais savoir si ma façon de calculer le niveau d'une grille est cohérente par rapport à ce qui ce fait...)

[leon1789]

Pour Léon : où a tu trouvé la grille "silver plate" et quel test faire pour voir si une grille est "trés dure" (j'aimerais savoir si ma façon de calculer le niveau d'une grille est cohérente par rapport à ce qui ce fait...)

Je suis allé sur http://www.sudoku.com/boards
Par exemple (on a même des classements) :
http://www.sudoku.com/boards/viewtopic.php?t=5336&postdays=0&postorder=asc&start=43
http://www.sudoku.com/boards/viewtopic.php?t=6539
http://www.sudoku.com/boards/viewtopic.php?t=4212&start=587
http://www.sudoku.com/boards/viewtopic.php?p=83887&sid=7d2f1a90ae3ccd903d608c0463652cab#83887

En ce qui concerne un calcul de niveau de difficulté, je pense qu'il n'existe pas de méthode objective d'évaluation de grilles. Il y a plein de manières d'évaluer des grilles en mesurant quelque chose de précis... mais tout en oubliant plein d'autres critères intéressant également.
Cela étant, je pense que toutes les méthodes d'évaluation sensées suivent globalement le même mouvement.

[leon1789]

Je pense (j'espère ! je ne sais même pas si cela va aller loin...) que pour faire des éliminations "non-récursives" de candidat dans silver plate, il va falloir procéder comme ça...

Code: Tout sélectionner

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


En utilisant les deux règles de base, on voit que,
quel que soit le candidat n de E7, l'hypothèse B3 = 8 conduit à une impossibilité.
Conclusion : B3 n'est pas 8.

De même,
quel que soit le candidat n de G8, l'hypothèse G7 = 4 conduit à une impossibilité.
Conclusion : G7 n'est pas 4.

[Ben314]

J'ai essayé avec ça :
http://diuf.unifr.ch/people/juillera/Sudoku/Sudoku.html
qui est un solveur "sans brute force".
Sa "déduction" n'est pas vraiment triviale...
Partant de l'hypothèse "B3=8" il déduit que
1) "E4=7" (77 étapes...)
2) "E4 différent de 7" (75 étapes...)

Deux remarques :
1) La méthode s'apelle "Contradiction Forcing Chain" et, perso., je trouve que ça commence à ressembler à de la "brute force"...
2) Ces notation de cases sont les mêmes que les miennes (nic nac nouche...)

P.S. : je trouve que ton raisonnement ressemble aussi beaucoup à "j'essaye B3=8" ce qui est plus ou moins... de la "brute force"...

Cest deux remarques me conduisent à la question :
Interdire la 'brute force', au fond ça veut dire PRECISEMENT quoi ?

[fatal_error]

re,

de maniere generale, on teste plein de possibilités (toutes).
le plus classique, c'est ya un code a 4 chiffres, ben on fait les 10000 possibilités, alors que par exemple, on aurait pu utiliser que les touches les plus effacées (car utilisées)

dans ce cas la, faire une brute force c'est : tester tous les candidats (car tous sont potentiellement amenant a la solution) jusqu'a ce que ca soit satisfaisant. C'est satisfaisant lorsque les candidats qu'on a supprimés amenent bien a une solution du probleme (ou n'amenent pas ca dépend comment on interprete). Comme on sait "a priori" pas prédire si le sudoku est solvable et a une unique solution sans tenter de le résoudre, alors la brute force consiste a pour les candidats potentiels tester chacun d'eux et tenter de voir si on a trouvé la solution.

[Ben314]

Ce qu'est la "brute force" dans l'absolu, je comprend,
Ma question c'est de savoir si la méthode de Léon :
"J'essaye B3=8, je fait tout les essais possible sur E7 => pas de solution"
Ne commence quand même pas à être proche de la "brute force" ?

Plus précisément, si on dit qu'on interdit la "brute force", quels sont précisément les raisonnement que l'on accepte et lesquels on refuse ?

Si tu veux, en étant complètement borné, "interdire la brute force" pourait se traduire par le fait d'interdire tout raisonnement contenant une hypothèse dont on n'est pas sure car celà constitue un "essai" et que l'on considère que les "essais" sont interdits et que seules les preuve totalement directes sont acceptables (i.e. "je sais que ... donc ..." )

[leon1789]

J'ai essayé avec ça :
http://diuf.unifr.ch/people/juillera/Sudoku/Sudoku.html
qui est un solveur "sans brute force".
Sa "déduction" n'est pas vraiment triviale...

C'est un programme effectivement très intéressant.

Partant de l'hypothèse "B3=8" il déduit que
1) "E4=7" (77 étapes...)
2) "E4 différent de 7" (75 étapes...)

Deux remarques :
1) La méthode s'apelle "Contradiction Forcing Chain" et, perso., je trouve que ça commence à ressembler à de la "brute force"...

Oui, je te comprends. Mais il ne faut pas se leurrer : avec ce genre de grille, toute résolution contient un "noyau brutal"...

2) Ces notation de cases sont les mêmes que les miennes (nic nac nouche...)

exact :hum:

P.S. : je trouve que ton raisonnement ressemble aussi beaucoup à "j'essaye B3=8" ce qui est plus ou moins... de la "brute force"...

Oui, je suis d'accord avec toi, mais c'est assez difficile de trouver des choses à dire sur cette grille. Pour positiver un peu sur les deux éliminations que je propose :
-- il y a beaucoup d'étapes, mais chaque étape est élémentaire ;
-- il est facile de faire comprendre le raisonnement global :
>
>

Ces deux remarques me conduisent à la question :
Interdire la 'brute force', au fond ça veut dire PRECISEMENT quoi ?

Je ne sais pas, c'est très subjectif : être en force brute ou pas. Quand il y a 10 appels récursifs, oui, c'est de la force brute. 9 appels, aussi... 8... 3, 2 , 1 ?

Personnellement, je voudrais "seulement" une solution non récursive, où il ne faut pas emboîter hypothèse dans hypothèse. Pour les deux éliminations que j'ai proposées, il est vrai qu'il faut faire deux hypothèses à chaque fois : B3=8 et E7=n pour le premier exemple (G7=4 et G8=n pour le second exemple)... Deux hypothèses, c'est déjà beaucoup, j'en conviens.
Mais comment faire autrement ?! :briques:

[leon1789]

Ce qu'est la "brute force" dans l'absolu, je comprend,
Ma question c'est de savoir si la méthode de Léon :
"J'essaye B3=8, je fait tout les essais possible sur E7 => pas de solution"
Ne commence quand même pas à être proche de la "brute force" ?

Plus précisément, si on dit qu'on interdit la "brute force", quels sont précisément les raisonnement que l'on accepte et lesquels on refuse ?

Disons qu'on accepte les raisonnements les moins "hypothétiques" parmi ceux qui permettent de conclure quelque chose. Ok, ce que j'écris est complètement vague. :ptdr:

Si tu veux, en étant complètement borné, "interdire la brute force" pourait se traduire par le fait d'interdire tout raisonnement contenant une hypothèse dont on n'est pas sure car celà constitue un "essai" et que l'on considère que les "essais" sont interdits et que seules les preuve totalement directes sont acceptables (i.e. "je sais que ... donc ..." )

Heu... Une hypothèse dont on est sûr, n'est plus une hypothèse. :zen:


A vrai dire, je crois que ce n'est pas évident de définir ce que "(ne pas) faire une hypothèse", "(ne pas) faire un essai" signifient vraiment. Rares sont les situations où on ne fait pas quelques (voire de nombreux) essais infructeux avant de tomber sur un essai concluant (comme sur un exo de math...)

Je prends plutôt le parti de me poser un question du genre :
Q(N) >
La réponse à Q(0) est positive pour les grilles faciles : par exemple silver plate avec B6=3 et F5=7.
La réponse à Q(1) est positive pour la plupart des grilles difficiles, mais fausse pour les grilles exceptionnellement difficiles.
Est-ce que Q(2) est vraie pour silver plate ???

[fatal_error]

jreviens.

Quand on a plein de possibilités, par exemple 9 candidats dans une case. Et qu'on les teste toutes parce qu'on veut la solution, c'est brute force!

Lorsque tu teste 1 candidat pour voir s'il amene a une contradiction, j'estime que c'est pas de la brute force.
Bien sur, si apres tu dis hop ca marche pas, je marrete, je passe au suivant, c'est faire brute force. Apres avoir supprimé le candidat, il faut voir si ca debloque les choses, pour adopter un comportement différent (de tester le suivant).

Donc lorsque le gars il fait un test guess (ou je sais plus trop quoi), c'est plutot pas mal proche puisqu'au final on fait un test sans pouvoir affirmer s'il est correct. C'est cque leon veut eviter : pas de recursivité.
Faire un test (récursif), c'est plus fin qued la brute force, mais c'est cqu'on veut eviter

[Ben314]

Heu... Une hypothèse dont on est sûr, n'est plus une hypothèse. :zen:

J'ai du mal à nier........ :doh:
Sauf que, si j'avais écrit
"...d'interdire tout raisonnement contenant une affirmation dont on n'est pas sure..."
On aurait tout aussi bien pu me rétorquer que, tant qu'on est pas sûr, ce n'est pas une affirmation...... :mur:

Bon, d'accord, c'était un pléonase, mais dans le contexte, c'était pour INSISTER (il me semble que dans ce cas, on a le droit... :zen:)

Pour le logiciel, je suis en train de le regarder et il n'a l'air de faire que des "hypothèses simples", mais je te dit pas la longueur des déductions...

[leon1789]

J'ai essayé avec ça :
http://diuf.unifr.ch/people/juillera/Sudoku/Sudoku.html
qui est un solveur "sans brute force".
Sa "déduction" n'est pas vraiment triviale...
Partant de l'hypothèse "B3=8" il déduit que
1) "E4=7" (77 étapes...)
2) "E4 différent de 7" (75 étapes...)

Deux remarques :
1) La méthode s'apelle "Contradiction Forcing Chain" et, perso., je trouve que ça commence à ressembler à de la "brute force"...

Dans les déductions de son forcing chain, le programme utilise une hypothèse (B3=8) mais d'autres principes de déduction que les deux règles élémentaires.
Est-ce que c'est mieux que deux hypothèses utilisant seulement les règles élémentaires ? Que peut-on répondre ?


Par ailleurs, le programme ne trouve pas de moyen pour éliminer G7=4.

[leon1789]

Quand on a plein de possibilités, par exemple 9 candidats dans une case. Et qu'on les teste toutes parce qu'on veut la solution, c'est brute force!

Lorsque tu teste 1 candidat pour voir s'il amene a une contradiction, j'estime que c'est pas de la brute force.

En justifiant que B3 n'est pas 8 par : pour tout n, [ E7=n (tous les candidats) => impossibilité ] >>
est-ce brute force ou pas ?

Je pense que tu diras "oui", non ?

[leon1789]

J'ai du mal à nier........ :doh:
Sauf que, si j'avais écrit
"...d'interdire tout raisonnement contenant une affirmation dont on n'est pas sure..."
On aurait tout aussi bien pu me rétorquer que, tant qu'on est pas sûr, ce n'est pas une affirmation...... :mur:

Bon, d'accord, c'était un pléonase, mais dans le contexte, c'était pour INSISTER (il me semble que dans ce cas, on a le droit... :zen:)

c'était pour te charrier :zen:

Pour le logiciel, je suis en train de le regarder et il n'a l'air de faire que des "hypothèses simples", mais je te dit pas la longueur des déductions...

oui, une seule hypothèse à la fois, mais ses déductions sur cette hypothèses sont parfois très compliquées... à tel point qu'on peut se demander s'il n'y a pas en réalité des hypothèses faites pendant ces déductions sur la première hypothèse... Et du coup, je trouve que ce n'est pas mieux que ce que je propose.

Mais cela se discute.

[leon1789]

oui, une seule hypothèse à la fois, mais ses déductions sur cette hypothèses sont parfois très compliquées... à tel point qu'on peut se demander s'il n'y a pas en réalité des hypothèses faites pendant ces déductions sur la première hypothèse... Et du coup, je trouve que ce n'est pas mieux que ce que je propose.

Effectivement, pour prouver B3 différent de 8, le programme fait l'hypothèse B3=8, puis utilise non seulement les règles de base, mais aussi des règles genre "Hidden pair", "Pointing cells", etc.

Une fois le 8 effacé de B3, il propose encore des éliminations. Chacune de ces éliminations est obtenue via un forcing chain contenant des forcing chains... C'est donc de la récursivité.

Conclusion : avec une seule hypothèse, sans récursivité, en utilisant des règles pas seulement de base, le programme n'élimine que le 8 en B3. Aucun autre candidat.