ncoder
Messages postés244Date d'inscriptionvendredi 6 mai 2005StatutMembreDernière intervention 6 avril 2008
-
9 mars 2006 à 18:24
jvpic
Messages postés5Date d'inscriptiondimanche 4 juin 2006StatutMembreDernière intervention 3 août 2006
-
13 juil. 2006 à 07:38
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
jvpic
Messages postés5Date d'inscriptiondimanche 4 juin 2006StatutMembreDernière intervention 3 août 2006 13 juil. 2006 à 07:38
Bonjour,
Oui l'algorithme de Knuth est générique aux problèmes de couvertures complètes d'une surface avec des éléments et des contraintes. Problème des cartes politiques à 4 couleurs, mosaïques de pentaminos etc... Le Sudoku est un problème du mëme genre, il suffit en interface avec l'algo Dlx de préparer la matrice à résoudre avec les contraintes et les données.
Non Knuth n'est pas mort... Il doit avoir 60-65 ans...
Reste que le problème de l'évaluation reste entier. Je pense qu'il n'est pas indispensable de coder les simulations lorsque les méthodes logiques complètes n'arrivent pas à résoudre une grille dont on la déjà solutionpar Dlx, elle est nécessairement "diabolique" !
JP
cs_Kirua
Messages postés3006Date d'inscriptiondimanche 14 avril 2002StatutMembreDernière intervention31 décembre 2008 12 juil. 2006 à 15:20
Il me semble aussi qu'une simulation des méthodes manuelles (y compris les spéculations avec une profondeur limitée, typiquement 1 ou 2 niveaux max) est la seule façon d'objectiver un niveau de difficulté.
Quant à l'unicité, l'algo implémenté ici permet tout à fait, avec modifs sans doute, j'ai pas regardé, de générer toutes les solutions. Il suffit de vérifier qu'il n'y en a qu'une in fine. Aucun problème.
L'algo de Knuth comme tu dis, c'est un algo générique, ou Knuth s'est vrmnt intéressé aux sudokus?? Il est pas mort d'ailleurs? :p
jvpic
Messages postés5Date d'inscriptiondimanche 4 juin 2006StatutMembreDernière intervention 3 août 2006 12 juil. 2006 à 13:37
Le code source applique en réalité la force brutale par récursivité. Cette méthode présente deux handicaps :
1) Elle est relativement longue par rapport à l'algorithme de Knuth (Dlx)
2) De plus on s'arrête à la première szolution : on a aucune garantie sur l'unicité de la solution et donc de la correction de la grille générée.
Une autre critique concerne cet algorithme, mais aussi celui de Dlx :
Nous n'avons aucun critère objectif de classification de difficulté de la grille générée, en effet le nombre de caractère n'est pas un critère robuste. Le temps de résolution n'en est pas un non plus.
Après avoir codé moi-même un jeu de Sudoku, par les deux algorithmes, je m'arrête sur le choix Dlx (rapidité et complétude) et pour la gébération, j'y rajoute un module de résolution "manuelle" (candidat unique, jumeaux, X-Xing, swordfish etc...) pour avoir une évaluation convenable (mais pas absolue).
J'aimerai avoir des opinions concernant ce vrai problème : EVALUATION DE LA DIFFICULTE d'une grille.
Merci
JP
cs_Urgo
Messages postés780Date d'inscriptionlundi 16 décembre 2002StatutMembreDernière intervention16 avril 20091 17 mars 2006 à 13:42
Chaque VRAI sudoku a une et une seule solution.
Celui qui en a plusieurs c'est à envoyer à la poubelle.
masternico
Messages postés487Date d'inscriptiondimanche 5 octobre 2003StatutMembreDernière intervention 1 septembre 2011 14 mars 2006 à 13:04
Tout les sudoku ne sont pas forcément à solution unique?...
cs_Kirua
Messages postés3006Date d'inscriptiondimanche 14 avril 2002StatutMembreDernière intervention31 décembre 2008 11 mars 2006 à 00:36
Ton "IA" est vrmnt un algorithme qui fait des raisonnements déductifs certains, ou c'est une recherche en profondeur d'abord? (brute force amélioré, programmation par contrainte).
Sur le n-1 ème code de sudoku de cppfrance, on a eu une discu sur ce genre de choses, et je ne sais plus qui a pondu un code déductif avec DFS (depth first search) pour les cas difficiles (besoin de spéculer), et ça donnait des résultats bien plus rapides que simplement une DFS.
Aussi, on peut se contenter d'une DFS par opposition aux BFS puisque la solution DOIT être unique.
gagah1
Messages postés509Date d'inscriptionsamedi 28 juin 2003StatutMembreDernière intervention 3 août 2010 9 mars 2006 à 21:12
La fonction masquage(...) ne teste pas l'unicité de la solution. Donc dans cette sudoku, une grille donnée pourrait avoir plusieures solutions possibles.
24Karas
Messages postés233Date d'inscriptionjeudi 4 juillet 2002StatutMembreDernière intervention 5 juillet 2008 9 mars 2006 à 20:09
le Nème sudoku sur le site.
ncoder
Messages postés244Date d'inscriptionvendredi 6 mai 2005StatutMembreDernière intervention 6 avril 20081 9 mars 2006 à 18:24
Bien fait, mis à part des fautes d'orthographe et qu'il y ait déjà plusieurs programmes de ce type, juste une petite critique :
Si on pouvait déplacer le carré sur la grille avec les flèches haut/bas/gauche/droite (hook par exemple) le jeu en serait énormément facilité, car sinon il faut à chaque fois taper un nombre, reprendre la souris, reregarder, retaper un nombre puis rereprendre la souris... et ainsi de suite ça pousse pas à la concentration lol !
13 juil. 2006 à 07:38
Oui l'algorithme de Knuth est générique aux problèmes de couvertures complètes d'une surface avec des éléments et des contraintes. Problème des cartes politiques à 4 couleurs, mosaïques de pentaminos etc... Le Sudoku est un problème du mëme genre, il suffit en interface avec l'algo Dlx de préparer la matrice à résoudre avec les contraintes et les données.
Non Knuth n'est pas mort... Il doit avoir 60-65 ans...
Reste que le problème de l'évaluation reste entier. Je pense qu'il n'est pas indispensable de coder les simulations lorsque les méthodes logiques complètes n'arrivent pas à résoudre une grille dont on la déjà solutionpar Dlx, elle est nécessairement "diabolique" !
JP
12 juil. 2006 à 15:20
Quant à l'unicité, l'algo implémenté ici permet tout à fait, avec modifs sans doute, j'ai pas regardé, de générer toutes les solutions. Il suffit de vérifier qu'il n'y en a qu'une in fine. Aucun problème.
L'algo de Knuth comme tu dis, c'est un algo générique, ou Knuth s'est vrmnt intéressé aux sudokus?? Il est pas mort d'ailleurs? :p
12 juil. 2006 à 13:37
1) Elle est relativement longue par rapport à l'algorithme de Knuth (Dlx)
2) De plus on s'arrête à la première szolution : on a aucune garantie sur l'unicité de la solution et donc de la correction de la grille générée.
Une autre critique concerne cet algorithme, mais aussi celui de Dlx :
Nous n'avons aucun critère objectif de classification de difficulté de la grille générée, en effet le nombre de caractère n'est pas un critère robuste. Le temps de résolution n'en est pas un non plus.
Après avoir codé moi-même un jeu de Sudoku, par les deux algorithmes, je m'arrête sur le choix Dlx (rapidité et complétude) et pour la gébération, j'y rajoute un module de résolution "manuelle" (candidat unique, jumeaux, X-Xing, swordfish etc...) pour avoir une évaluation convenable (mais pas absolue).
J'aimerai avoir des opinions concernant ce vrai problème : EVALUATION DE LA DIFFICULTE d'une grille.
Merci
JP
17 mars 2006 à 13:42
Celui qui en a plusieurs c'est à envoyer à la poubelle.
14 mars 2006 à 13:04
11 mars 2006 à 00:36
Sur le n-1 ème code de sudoku de cppfrance, on a eu une discu sur ce genre de choses, et je ne sais plus qui a pondu un code déductif avec DFS (depth first search) pour les cas difficiles (besoin de spéculer), et ça donnait des résultats bien plus rapides que simplement une DFS.
Aussi, on peut se contenter d'une DFS par opposition aux BFS puisque la solution DOIT être unique.
9 mars 2006 à 21:12
9 mars 2006 à 20:09
9 mars 2006 à 18:24
Si on pouvait déplacer le carré sur la grille avec les flèches haut/bas/gauche/droite (hook par exemple) le jeu en serait énormément facilité, car sinon il faut à chaque fois taper un nombre, reprendre la souris, reregarder, retaper un nombre puis rereprendre la souris... et ainsi de suite ça pousse pas à la concentration lol !
Voilà voilà a+