Bonjour à tous,

Les grilles de Sudoku sont élaborées par des algorithmes, il me semble. Je me demande si certaines de ces grilles ont une solution qui puisse être trouvée par raisonnement, par raisonnement j'entends une autre méthode que l'énumération de différentes possibilités.

En effet, dans certain cas, il se peut que je n'aie pas vu clair, possible, mais après avoir vraiment fouillé plusieurs jours d'affilée, j'ai l'impression que la seule issue devient de faire un "pari" sur certaines cases dont on a restreint les choix possibles.

Dans les autres cas, le raisonnement, et l'anticipation à 1, 2 ou 3 coups d'avance, permet de deviner le contenu d'une case, mais parfois, on ne peut pas aller plus loin que 2 possibilité par case, à partir de là, ca devient de l'énumération, on en teste une au hasard, et on regarde si ça aboutit, ou si ca conduit à une contradiction.

En savez-vous plus sur le sujet ? Parce que c'est assez chiant d'être bloqué et de ne pas savoir si c'est parce qu'on manque un truc ou si c'est parce que le seul moyen de progresser c'est de tester manuellement 2 sous-problèmes...

Tu peux toujours trouver la solution d'un sudoku par raisonnement, même si lorsque tu fais des sudoku super difficile, tu peux mettre du temps à faire ce raisonnement. Une solution, lorsque tu as un nombre restreint de possibilités pour une case (2 ou 3), c'est de tester mentalement chaque solution jusqu'à aboutir à des contradictions, et donc en déduire la seule solution possible.

ça, c'est un topic Interessant !

Alors a priori, oui, il existe des sudoku a hypothese (ou tu dois faire un choix et avancer jusqu'a tomber sur une contradiction)
J'ai d'ailleurs un programme qui peut détecter cela (mais je pense lui rajouter d'autres algos)
Je m'explique :
Voila ma page de programmes :

http://perso.numericable.e.fr/fvirtman/progs/index.html

En bas, tu trouveras un résolveur de sudoku cognitif :
C'est a dire qu'il essaiera de raisonner comme un etre humain pour trouver le chiffre suivant, et, s'il en trouve un, te montrera comment il a trouvé.
Tu recopies le sudoku, avec les chiffres que tu as déja et il cherche un prochain chiffre sans ambiguité.
Essaie le programme, tu verras tout de suite si un nombre pouvait etre trouvé, mais que tu ne l'avais pas vu !

Actuellement, j'ai mis en place que 2 algos :

- soit il existe une ligne, une colonne, ou un carré dont il ne manque qu'un chiffre -> résolution immédiate
- sinon, 2e algo, qui marche dans énormément de cas, je regarde chaque ligne, chaque colonne, chaque carré, et, pour chaque chiffre, j'essaie de voir dans combien de cases il peut rentrer (dans la ligne, colonne, carre considéré).
S'il ne peut rentrer que dans une case, alors je le valide.
L'algo, quand il a trouvé, te montre par des segments dans quelle ligne-colonne-carré, il est, te montre le chiffre ajouté en couleur, et te montre les autres chiffres responsables du fait qu'on n'aurait pas pu le mettre ailleurs.

Si ces 2 algos échouent, je finis en brute-force : c'est a dire que je fais calculer a l'ordi toutes les possibilités jusqu'a ce qu'il trouve (non cognitif)

Je réfléchis a d'autres algos.

1. Aldebran Voir le profil de Aldebran
2. Posté le 07 février 2008 à 22:54:22 Avertir un modérateur

Une solution, lorsque tu as un nombre restreint de possibilités pour une case (2 ou 3), c'est de tester mentalement chaque solution jusqu'à aboutir à des contradictions, et donc en déduire la seule solution possible.

Oui ok, mais c'est ce qui fait la différence entre le raisonnement humain, et le simple algorithme qui énumère. Si pour trouver une case, il faut diviser sa feuille en 2, puis tester chaque possibilité pour découvrir une demi-heure plus tard qu'elle est une impasse, ça ne présente plus grand interêt.

Fvirtman: de mes vagues souvenirs de cours d'algorithmique, c'est des méthodes dites "Branch & bound", qui en gros explorent des possibilités de solutions, en éliminent d'autres, etc.
Mais encore une fois, il n'y a plus d'interêt "intellectuel" à jouer au jeu si sa résoluion demande de dérouler des énumérations possibles pour chaque case.

Fvirman > Je viens de tester ton programme, et je dois reconnaître qu'il est vraiment très bon !

Pour les plusieurs grilles ou j'étais bloqué, c'est à peu prés ce que je pensais, parce qu'exactement au même moment que moi, il passe en "brute-force"... et ne trouve pas !

Je ne sais pas si tu as réussi à "évaluer" la difficulté de chaque case, pour ensuite essayer de brute-forcer la plus petite d'entre elle... Ca doit être faisable, parce que dans les magazines, les grilles sont classées par ordre de difficulté, c'est donc que l'algorithme qui génère les grilles trouve un moyen d'évaluer la difficulté de cette grille...
Par contre par quel procédé...

Je crois que la difficulté des sudokus qu'on trouve dans les magazines est simplement due au nombre de chiffres donnés au départ.
Enfin ch'uis pas un pro du sudoku mais de c'que j'ai vu et expérimenté ça semblait logique et crédible.
________________________________________________
C'est en buvant une goutte d'eau que l'on se rend compte de sa soif.
"L'homme choisit, l'esclave obéit." (Andrew Ryan)

1. _Azerty777 Voir le profil de _Azerty777
2. Posté le 08 février 2008 à 14:47:51 Avertir un modérateur
3. Je crois que la difficulté des sudokus qu'on trouve dans les magazines est simplement due au nombre de chiffres donnés au départ.

Enfin ch'uis pas un pro du sudoku mais de c'que j'ai vu et expérimenté ça semblait logique et crédible.

M'étonnerait fort: pour la simple raison qu'il existe des tonnes de grille qu'on peut commencer assez facilement, et puis après quelques cases remplies, on bloque carrément. La grille est donc plus dure après qu'au départ.

cependant, il y a d'autre raisonement que ceux implanté par fvirtman.
on peux dans certains cas avoir des informations en couplant les trois listes de 1à 9
je m'explique.
tu sais qu'il y a un '1' dans la colonne un, mais il y a deja un '1' dans le carré du bas donc, il y a de facon certaine un '1' dans la colonne de gauche du carré du milieu ou du haut.

ou encore, tu ne sais pas si le '1' est en bas a gauche ou en bas au milieu mais savoir qu'il est en bas te donne des informations sur les carré voisins.

Pour répondre a la question sur l'algorithme. C'est n'est pas un branch and bound, mais un algorithme diviser pour regner. En effet, branch and bound sert a chercher la meilleur solution d'un probleme d'optimisation en découpant l'espace des solutions en sous probleme. On n'explore pas certaine branche en estimant la meilleur solution d'un ensemble a l'aide d'un algorithme de relaxation (de facon classique, on relache la contrainte d'integrite d'un programme lineaire en nombre entier). L'algorithme de relaxation peut alors nous informer qu'il n'y a pas de solutions qui nous interesse dans l'ensemble que l'on considere.

Au niveau du passage en brute force de l'algo de fvirtman et de son optimisation, il faudrait voir quel partie considerer en premier. Il serait catastrophique d'avoir a enchainer les hypothese. Il est probablement judicieux de commencer a explorer la voie qui rajoute le plus de contrainte. Cependant, commencer avec l'arité la plus faible possible est aussi probablement utile. Il faudrait estimer chacune des possibilité de branchement...
Comme d'habitude avec les techniques brute-force, on finit par faire de la cuisine!

Finalement, il pourrait etre interessant d'écrire sudoku dans un moteur de programmation par contrainte. histoire de voir s'il trouve des arguments que l'on ne connait pas

"Beaucoup de gens délaissent les mots croisés pour ce jeux où la réflexion est simpliste et qui leur fait croire qu'il s'agit d'un jeu mathématique."

Boarf, ceux qui faisaient des mots croisés ne les ont pas délaissés, et ceux qui ne faisait jamais les jeux dans les magazines et les journaux se sont mis à faire des sudokus. En plus, l'effort intellectuel peut être intense quand on fait un sudoku, notamment lorsque ce sont des sudoku à hypothèses (ça fait pas travailler le calcul, mais la mémoire c'est certain).

"Finalement, il pourrait etre interessant d'écrire sudoku dans un moteur de programmation par contrainte"

Mieux que la programmation par contraite, la programmation déclarative :
http://chneukirchen.org/repos/blogcode/sudoku.pl

Mais il n'est pas très beau, j'ai déjà vu un autre solveur écrit en prolog qui tenait dans 15 lignes. mais je ne le retrouve pas.

Et un solveur en OCaml que j'ai écrit il y a un certain temps : http://repository.kende.fr/Caml/sudoku.ml il n'est pas très beau et je ne me souviens pas des heuristique qu'il utilise.

Je n'ai pas lu toutes les réponses, donc excusez-moi si je suis HORS-SUJET...

J'ai réalisé l'an dernier un programme en C++ qui résout une grille de Sudoku.

Je peux vous le filer si ca intéresse quelqu'un ...

"Tout au plus la mémoire immédiate qui n'a pas vraiment besoin d'être travaillée et ça n'a quasiment pas d'incidence sur la mémoire."

En fait, je pensais à la même mémoire que lorsqu'on fait du calcul mental, je suppose que c'est la mémoire immédiate. Personnellement je ne note jamais les solutions possibles, je fait tout de tête, et lorsqu'il faut retenir 3 possibilités de solutions pour 4-5 cases différentes afin de résoudre le sudoku, ça demande quand même un certain effort.

Ca fait rien travailler du tout, c'est juste fun, ça occupe, et c'est bien comme ça.

J'ai pas eu le courage de tout lire, peut être que vous l'avez déjà dit, si c'est le cas excusez-moi...

Mais moin il y a des nombres plus c'est dur
essayez de remplir un su-do-ku vide, c'est pas si simple
alors qu'un su-do-ku auquel il ne manque qu'un chiffre^^

Tu as tout faux et j'ai déjà expliqué pourquoi...

Ton raisonnement, s'il était vrai, signifierait que le Sudoku est plus dur au début que par la suite. Or il y a des tonnes de grilles faciles au début, puis d'un coup très dures.

Ben j'aimerais bien un exemple, tu as surement raison, mais je comprends pas comment...
Des tas de grilles que j'ai faites, prouvaient mon raisonnement

Ou alors ma théorie n'est pas absolue, mais marche dans la plupart des cas

Tu es d'accord que quand on a plus qu'un chiffre à mettre c'est plus facile que quand on en est au début

"Ou alors ma théorie n'est pas absolue, mais marche dans la plupart des cas"

Ta théorie est vrai dans la plupart des cas, mais en général, une grille est dure lorsqu'il n'y a qu'un seul nombre qu'il est possible de trouver et qu'il y a peu de cases remplies.

sonkey==>Ouais nan mais je pense que c'est par rapport au nombre de cases vides de départ. S'il y a la moitié des carrés remplis à 66%, ce sera très probablement beaucoup plus facile que si y'a que deux chiffres par carré...
________________________________________________
C'est en buvant une goutte d'eau que l'on se rend compte de sa soif.
"L'homme choisit, l'esclave obéit." (Andrew Ryan)

1. Jo-7 Voir le profil de Jo-7
2. Posté le 16 février 2008 à 23:27:22 Avertir un modérateur
3. Ben j'aimerais bien un exemple, tu as surement raison, mais je comprends pas comment...

Des tas de grilles que j'ai faites, prouvaient mon raisonnement

Ou alors ma théorie n'est pas absolue, mais marche dans la plupart des cas

Tu es d'accord que quand on a plus qu'un chiffre à mettre c'est plus facile que quand on en est au début

Et bien, on est d'accord que souvent, les premieres cases sont relativement facile, par contre après on peut avoir des gros points de blocage plus tard dans le jeu.

Tu peux l'illustrer en téléchargeant le logiciels qu'on m'a recommandé, et tu prends une grille difficile: au début, le logiciel trouvera avec un raisonnement humain, et puis à un moment il passera en brute force, autrement dit, le jeu s'écoule, et arrive un moment ou ca devient bourrin (alors qu'il y a théoriquement moins de case à trouver).

Ouais je suis d'accord, j'ai compris