SUDOKU
ncoder
Messages postés
244
Date d'inscription
vendredi 6 mai 2005
Statut
Membre
Dernière intervention
6 avril 2008
-
9 mars 2006 à 18:24
jvpic Messages postés 5 Date d'inscription dimanche 4 juin 2006 Statut Membre Dernière intervention 3 août 2006 - 13 juil. 2006 à 07:38
jvpic Messages postés 5 Date d'inscription dimanche 4 juin 2006 Statut Membre Derniè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.
https://codes-sources.commentcamarche.net/source/36457-sudoku
https://codes-sources.commentcamarche.net/source/36457-sudoku
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+