Discussion :

[Matthieu Brucher]

Apparemment, certaines personnes pensent qu'à cause du côté NP-complet du problème, on n'aura jamais toutes les règles.
Je m'intéresse en ce moment au XY-Wing et ses généralisations - Medusa, Nishio, chaînes, ... -

[random]

il est certain que tous les problèmes ne peuvent être résolus à
partir de régle
il existe des positions non solubles sans essai erreur

par ailleurs en termes d'efficacité un essai erreur voire 2
(deux bigrammes non corrélés) est très payant

[tiboleo]

Bonjour,

Je n'ai pas lu l'intégralité des 10 pages de réponses à ce post.
Voici une version intéressante. J'espère juste ne pas faire doublon.

Elle apporte une solution et présente "Choco", un framework de programmation par contrainte

Génération de Sudoku
Choco

J'en profite pour passer un message.
Si quelqu'un sait utiliser la programmation par contrainte pour faire de la planification de ressources (humaines), je suis preneur...

Thierry.

[pcaboche]

Bonjour tout le monde,

Je suis tombé sur ce sujet par hasard et même s'il commence à dater, il me parait interessant (même si, moi non plus, je n'ai pas lu l'intégralité des 10 pages).

Tout d'abord, je ne savais pas qu'il y avait autant de gens qui s'interessaient à la résolution de sudoku. J'ai écrit un article (qui j'espère sera prochainement officiellement annoncé) sur la Programmation Logique avec Contraintes, que j'illustre justement avec un programme de résolution de sudoku:

http://pcaboche.developpez.com/artic...og/clp/sudoku/

Le programme est écrit en Prolog (langage servant à faire de la PROgrammation LOGique). Ce programme a été écrit en 1/2 journée, le jour où j'ai découvert le sudoku. J'ai choisi Prolog car il permettait de représenter ce problème de manière extrêment simple et efficace (la consistance d'arc est faite directement par la bibliothèque permettant la PLC).

Prolog s'interface de manière très simple avec d'autres langages (C++, Java) ce qui permet, par exemple, de programmer l'interface graphique en C++ alors que la résolution se fera en Prolog (il faudra d'ailleurs que j'écrive un article sur le sujet).

Pour découvrir le langage Prolog, c'est ici :
http://pcaboche.developpez.com/artic.../presentation/

(oui oui, je me fais ma petite pub au passage, j'ai le droit, non? )

J'en profite pour passer un message.
Si quelqu'un sait utiliser la programmation par contrainte pour faire de la planification de ressources (humaines), je suis preneur...

Thierry.

Cher Thierry,

Je pense qu'il est tout à fait possible de représenter ce problème en PLC, reste à l'exprimer à l'aide de variables et de contraintes...

Sinon, il est tout à fait possible de résoudre ce type de problème avec du Prolog "de base" (différents prédicats exprimant les contraintes, recherche de solutions + backtracking si une contrainte n'est pas respectée).

L'avantage du Prolog, c'est que:
- il permet d'exprimer ce genre de problèmes de manière simple
- il peut s'interfacer les langages les plus courants

De cette manière, tu ne te pose plus la question: "est-ce que j'écris mon programme en Java, comme ça je pourrai utiliser Choco?". A la place, tu te concentres sur la résolution de ton problème en Prolog (parce que c'est un langage adapté à ce type de problèmes). Pour l'interface graphique, tu verras plus tard... (personnellement, ça me parait plus logique comme manière de faire: quand on choisit une voiture, on commence rarement par la couleur)

[mathk]

Il y a aussi des solver en python assez facille a comprendre:
Sudoku Solver

[Matthieu Brucher]

Il y a pleins de gens qui font de la résolution, de la création de grilles, ...
Mon solveur a maintenant un solveur en ligne de commande et indiquant le niveau de difficulté, même si je compte encore un peu l'améliorer à ce niveau

[random]

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

c'est camoufler une méthode essai-erreur derrière un paravent

j'aimerais voir la performance de prolog face à un problème avec une grille de 100x100

[Tellmarch]

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.

[Teuchteu]

Moi ce que je viens de comprendre c'est que soit tu connais pas trop bien le jeu et tu fais des essais/erreurs, soit tu le maitrises et tu automatises les reflexions que tu fais quand tu joues. Ca doit finallement être applicable pour beaucoup de jeux (donc pour coder l'IA d'un jeu, il faut d'abord y jouer comme un malade )

P.S.: J'ai déjà résolu des grilles difficiles à la main, et sans avoir à un seul endroit fait un choix (ou alors je ne m'en suis pas apperçu et je le c_l bordé de nouilles ), ce qui me conforte dans l'idée qu'une recherche par essais n'est pas la seule solution valable. En revanche je ne me suis jamais attaqué au niveau du dessus. :

[Tellmarch]

en pratique il n'est pas possible d'éviter completement un algo de parcours en profondeur, ce qui correspond à un alog essai erreur.

Meme un humain fonctionne ainsi pour résoudre une grille difficile, à une certaine echelle.

Il en va de meme pour les autres jeux en général (echecs, go, awele, etc...)

[Teuchteu]

Je t'assure que des grilles difficiles (bon je ne dirai pas toutes les grilles, puisque je suis loin d'avoir parcouru toutes les possibilités) peuvent se faire sans essai, par simple déduction logique.
J'entend par essai le fait de partir sur au moins 2 actions possibles et d'en observé les conséquences.
Je ne me suis pas lancé sur le niveau très difficile, donc je ne serai pas aussi catégorique pour celle là.

La difficulté est de coder dans l'algo le raisonnement que l'on a pour avancer, alors que l'algo est bloqué (je suis en train, moi aussi, de faire un petit solveur en C sans passer par un arbre de possibilité).

Enfin ce qui me fascine le plus c'est le boum qu'a fait ce jeu.Tout le monde en parle et y joue. Tout le monde? Presque, car il reste un petit village d'irréductibles....

[Tellmarch]

tu peux toujours élaborer des stratégies complexes qui vont éviter certains essais/erreurs, mais en fin de compte on peut toujours trouver des grilles dans lesquelles ces stratégies ne fonctionneront pas.

donc si tu veux faire un solveur universel tu devras toujours implémenter cette méthode.

De plus en pratique l'arbre de recherche est tres rapide, donc il n'y a pas de raison de coder des cas particuliers avant d'appliquer le cas général...

[Teuchteu]

De plus en pratique l'arbre de recherche est tres rapide, donc il n'y a pas de raison de coder des cas particuliers avant d'appliquer le cas général...

Si la seule raison c'est de reproduire le raisonnement humain, dans un but ludique. C'est sur que ça n'a pas beaucoup d'interet quand un bon arbre de possibilité règle le problème. Mais pouvoir coder son raisonnement pour qu'un programme puisse le faire est tout de même satisfaisant (oui monsieur je suis très satisfait, même si mon prog ne résoud pour l'instant que du niveau facile ).

tu peux toujours élaborer des stratégies complexes qui vont éviter certains essais/erreurs, mais en fin de compte on peut toujours trouver des grilles dans lesquelles ces stratégies ne fonctionneront pas.

Est-ce vrai? Je suis dubitatif... Le prinicpe du Sudoku ne serait-il pas de permettre la résolution d'une grille sans faire d'essai/erreur :

[Matthieu Brucher]

en pratique il n'est pas possible d'éviter completement un algo de parcours en profondeur, ce qui correspond à un alog essai erreur.

Meme un humain fonctionne ainsi pour résoudre une grille difficile, à une certaine echelle.

Il en va de meme pour les autres jeux en général (echecs, go, awele, etc...)

Faux. L'humain recourt à ces techniques car les techniques à utiliser sont très difficiles à mettre en place. Je pense en particulier aux chaînes d'implication, ...
Par exemple, la grille la plus difficile connue se résoud SANS devinette.

[Tellmarch]

dans beaucoup de grilles, on commence par essayer de placer un nombre, ça force le remplissage de plusieurs autres cases, et on arrive à une contradiction.

C'est ce processus qui est effectué naturellement par l'etre humain.

simplement quand on effectue ceci cela s'apparente à l'application d'une "regle", spécifique à la situation, donc on n'a pas forcement conscience qu'on vient d'essayer une méthode essai/erreur dans sa tete, à une profondeur limitée.

simplement le nombre de telles regles serait presque infini, et elles sont toutes recouvertes par une méthode essai/erreur...

[Teuchteu]

dans beaucoup de grilles, on commence par essayer de placer un nombre, ça force le remplissage de plusieurs autres cases, et on arrive à une contradiction.

On ne joue peut-être pas de la même façon. Je ne fais jamais une hypothèse pour ensuite arriver à une contradiction. Quand je remplis une case de la grille, je suis sur de ce que j'y mets, sauf quand je me trompe

La méthode par essai/erreur marche, ça personne ne le contredit, mais est-ce vraiment la seule utilisable pour le sudoku, telle est la question :

[Tellmarch]

Bon j'ai vu beaucoup de grilles ou pour remplir une case, ce qu'il fallait utiliser c'est du genre :
(je donne juste un exemple, tres simple, pour montrer le genre de raisonnement qu'on fait)

Il y a forcement 2 ou 3 sur cette case (sinon on aboutit à une contradiction directe).
Si y avait 3 alors sur la case d'à coté y aurait un 2, et ça marcherait pas.
Donc c'est un 2 qu'il faut mettre sur la case.
Et on remplit la case, en étant sur que c'est un 2 qu'il faut y mettre, comme tu le dis.

Mais meme si ce raisonnement a été effectué dans la tete, et qu'on ne s'en rend pas compte, il s'agit bien d'un raisonnement par essai/erreur.

et l'ordinateur peut tres bien et tres facilement automatiser ça dans le cas général.

[Trap D]

Pour en résoudre beaucoup, même les plus difficiles, c'est TOUJOURS par un raisonnement logique et sans suppositions qu'on peut trouver les nombres à trouver (j'inclus dans ce raisonnement logique ce que vient d'écrire Tellmarch, ce n'est pas un raisonnement essai/erreupour moi)

[goomy]

Bonjour

Je ne suis pas informaticien, mais juste joueur de sudoku.

Pour tenter de résumer ma méthode en la rendant "logique" :
-> remplir les cases vides avec les différentes possiblités en prenant appui sur la colonne, la ligne et le carré 3x3 de la case en question.
-> remplir les cases qui ne comportent qu'une seule valeur
-> trouver les paires (comparer 2 à 2 les cases) d'une ligne, d'une colonne et d'un carré 3x3 et gommer en conséquence les valeurs de la paire sur la ligne correspondante, sur la colonne ou dans le carré.
-> regarder à nouveau s'il y a des valeurs seules. Si oui les inscrire et refaire l'analyse des paires, sinon on passe au triplet.
-> trouver les triplets d'une ligne, colonne ou carré et gommer en conséquence.
-> regarder à nouveau s'il y a des valeurs seules, puis de nouvelles paires, puis de nouveaux triplets.
-> trouver les quadruplets d'une ligne, colonne ou carré et gommer en conséquence.
-> regarder à nouveau s'il y a des valeurs seules, puis de nouvelles paires, puis de nouveaux triplets, puis de nouveaux quadruplets.
-> trouver les quintuplets d'une ligne, colonne ou carré et gomme en conséquence.
-> regarder à nouveau s'il y a des valeurs seules.
-> Quand j'ai fini de faire ces différentes analyses, soit le jeu est rempli, soit il reste des solutions et il faut faire une étape de testing, à partir d'une paire faire un choix et soit on complète le grille soit il y a une contradiction et c'est l'autre valeur qu'il faut mettre ((en général les grilles les plus difficiles que j'ai faites comportait une étape de testing avec peu de chiffres inscrit mais une seule étape était nécessaire).

Pour des grilles difficiles, je vous conseille ce petit recueil qui propose vraiment des grilles difficiles (les ceintures noires demandent vraiment du temps et de la réflexion). Si vos programmes résolvent ces grilles alors c'est qu'ils sont sans doute performants.

[Tellmarch]

Pour en résoudre beaucoup, même les plus difficiles, c'est TOUJOURS par un raisonnement logique et sans suppositions qu'on peut trouver les nombres à trouver (j'inclus dans ce raisonnement logique ce que vient d'écrire Tellmarch, ce n'est pas un raisonnement essai/erreupour moi)

Alors on n'a pas la meme définition d'un raisonnement essai/erreur
pour moi, tous les raisonnements que l'on peut appliquer dans le sudoku sont basés sur l'essai/erreur.

Par exemple si l'on a une colonne remplie à 8 cases, pour la derniere case, on peut trouver la bonne valeur. Pourquoi? parceque toutes les autres valeurs donneraient une erreur immédiate.

Un programme informatique basé sur l'essai/erreur, ce qui correspond à un parcour de l'arbre des possibilité, ferait exactement la meme chose :
pour les 8 branches correspondant aux 8 numéros deja pris, il aboutirait à une contradiction directe, remonterait dans l'arbre, et trouverait ainsi la bonne valeur immédiatement.


Apres, il est bien sur possible de rajouter des "regles" artificielles pour oublier ce qui est à la base du raisonnement, l'essai/erreur.
par exemple la regle "si l'on a 8 cases remplies dans une colonne, alors la 9eme est la valeur qui n'était pas dans la colonne".
Mais toutes ces regles ne sont que des conséquences directe de l'essai/erreur, et un simple programme qui se contente de faire un parcours les retrouverait trivialement.

De plus un programme doit nécessairement implémenter l'algorithme général de recherche, car quelque soit l'ensemble de regles que l'on donne, on pourra toujours trouver une grille de sudoku particuliere dans laquelle aucune de ces regles ne s'appliquera, et où il faudrait inventer une nouvelle regle spécifique, qui découlerait encore une fois du principe d'essai/erreur, qui permettrait de résoudre la grille.

C'est pour ça que je pense qu'il n'est pas nécessaire d'implementer une bibliotheque de regles spécifiques à appliquer dans un solveur de sudoku, alors qu'elles découleront toutes naturellement de l'algorithme général d'essai/erreurs.