SUDOKU

Messages postés
244
Date d'inscription
vendredi 6 mai 2005
Statut
Membre
Dernière intervention
6 avril 2008
- - Dernière réponse : 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

Afficher la suite 
jvpic
Messages postés
5
Date d'inscription
dimanche 4 juin 2006
Statut
Membre
Dernière intervention
3 août 2006
-
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és
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
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és
5
Date d'inscription
dimanche 4 juin 2006
Statut
Membre
Dernière intervention
3 août 2006
-
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és
780
Date d'inscription
lundi 16 décembre 2002
Statut
Membre
Dernière intervention
16 avril 2009
1 -
Chaque VRAI sudoku a une et une seule solution.
Celui qui en a plusieurs c'est à envoyer à la poubelle.
masternico
Messages postés
494
Date d'inscription
dimanche 5 octobre 2003
Statut
Membre
Dernière intervention
1 septembre 2011
-
Tout les sudoku ne sont pas forcément à solution unique?...
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
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és
509
Date d'inscription
samedi 28 juin 2003
Statut
Membre
Dernière intervention
3 août 2010
-
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és
233
Date d'inscription
jeudi 4 juillet 2002
Statut
Membre
Dernière intervention
5 juillet 2008
-
le Nème sudoku sur le site.
ncoder
Messages postés
244
Date d'inscription
vendredi 6 mai 2005
Statut
Membre
Dernière intervention
6 avril 2008
1 -
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 !

Voilà voilà a+