Il y a une preuve quelque part?Envoyé par 2Eurocents
Non ! Si l'on a un choix à faire, c'est qu'il y a une règle qui n'a pas été appliquée.
Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Il y a une preuve quelque part?Non ! Si l'on a un choix à faire, c'est qu'il y a une règle qui n'a pas été appliquée.
Je n'en ai pas.Il y a une preuve quelque part?Non ! Si l'on a un choix à faire, c'est qu'il y a une règle qui n'a pas été appliquée.
Toutefois, si l'on doit faire une supposition, il faut pouvoir revenir en arrière dans la résolution, en cas d'erreur. Or au moyen des règles, il me semble qu'il est possible de résoudre toutes les grilles valides dans ce retour arrière - sans backtrack.
C'est sur cette absence de retour en arrière que repose mon affirmation, péremptoire s'il en est !
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, ... -
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
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.
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?)
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)
"On en a vu poser les armes avant de se tirer une balle dans le pied..."
-- pydévelop
Derniers articles:
(SQL Server) Introduction à la gestion des droits
(UML) Souplesse et modularité grâce aux Design Patterns
(UML) Le Pattern Etat
Autres articles...
Il y a aussi des solver en python assez facille a comprendre:
Sudoku Solver
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
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
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.
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.)
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.
:
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...)
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....
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...
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 facileDe 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...
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/erreurtu 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.
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.
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...
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
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.
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)
"La haine seule fait des choix" - Koan Zen
"Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
"Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
Faites du Prolog, ça vous changera les idées !
Ma page Prolog
Mes codes sources commentés
Mon avatar : La Madeleine à la veilleuse de Georges de La Tour
Répondre avec citation
Partager