Télécharger le zip
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+
le Nème sudoku sur le site.
La fonction masquage(...) ne teste pas l'unicité de la solution. Donc dans cette sudoku, une grille donnée pourrait avoir plusieures solutions possibles.
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.
Tout les sudoku ne sont pas forcément à solution unique?...
Chaque VRAI sudoku a une et une seule solution. Celui qui en a plusieurs c'est à envoyer à la poubelle.
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
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
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
Se souvenir du profil
Mot de passe oublié ? / Activation de compteCréer un compte