Automatiser la réponse au Sudoku

C'est vrai que le minimax n'est pas adapté dans ce cas, je n'y avais pas pensé - tu minimises puis maximises ta fonction de coût -, l'alpha-beta, je ne sais plus comment ça fonctionne exactement. Si c'est sur le même principe :|

Le truc que tu peux faire tout de même, c'est faire un parcours de l'arbre qui minimise la fonction de coût.

Aurais-tu un exemple sous la main ?
Dans mon cas le côut c'est quoi ? le chemin le plus court pour arriver à la solution finale ?

De fonction ? Regarde le post de random à ce sujet, son coût est lié au nombre de données restantes
De grille non solvable ? J'en ai fourni avec mon logiciel dispo sur free

Miles si je puis me permettre il n'y a pas de grille non solvable

Un problème de sudoku est nécessairement solvable, ce sont nos algos
qui péchent, ou alors le problème ne répond pas à la définition: "un sudoku possède une solution unique."

Ceci suppose que le poids des contraintes énoncées à la fois par les indices donnés et par la définition générale du problème soit suffisemment
fort.

Ceci posé, savoir si l'on est obligé une technique ou une autre, c'est
l'objet de ce post.

Je ne sais pas trop à qui tu réponds... :-)

Citation:

---

De fonction ? Regarde le post de random à ce sujet, son coût est lié au nombre de données restantes
De grille non solvable ? J'en ai fourni avec mon logiciel dispo sur free

---

Mais si c'est à moi, ne t'embête pas, mes questions faisaient allusion à mon jeu (ma réussite et ses histoires de coûts)... mais comme je suis un peu à côté de la plaque par rapport au sujet de départ "le sudoku", tu n'es pas obligé de me répondre :-)

Mais si ça t'intéresse, mon sujet est débattu ici :

http://www.developpez.net/forums/viewtopic.php?t=424003

a+

Citation:

---

Envoyé par random

Miles si je puis me permettre il n'y a pas de grille non solvable

Un problème de sudoku est nécessairement solvable, ce sont nos algos
qui péchent, ou alors le problème ne répond pas à la définition: "un sudoku possède une solution unique."

Ceci suppose que le poids des contraintes énoncées à la fois par les indices donnés et par la définition générale du problème soit suffisemment
fort.

Ceci posé, savoir si l'on est obligé une technique ou une autre, c'est
l'objet de ce post.

---

Pardon, effectivement, ce sont des grilles qui ne sont pas solvables avec nos 3 règles, à priori.

Bonjour,

je viens de terminer un Algorithmes en PHP pour résoudre les sudoku et un pour générer des grilles remplies entierement, voila j'aimerais maintenant arriver a générer des grilles pour jouer mais la je seche completement... et j'aime pas trop l'idée de retirer un chiffre et verifier que la grille et toujours correct.... mais bon peut etre que c la seul solution alors....

pas du tout
tu as une grille complète
un solveur avec sa grille de résolution

tu pars d'une grille temporaire vide
tu enchaines

faire
tirage au sort d'une case de la grille complète
ajout dans la grille temporaire
ajout dans la grille de résolution
appel solveur
tant que problème non résolu

quand le problème est résolu la grille temporaire est ta grille problème
et tu as comme toujours niveau problème=niveau solveur

Bonjour,

Je suis actuelement entrain de réaliser un générateur de grilles de sudoku, avec gestion des niveaux de difficultés.

J'aimerai savoir pour quel raison les cases "masquées" sont toujours symetriques par rapport au centre? Une facilité quelquonque?

J'aimerai egalement connaitre votre avis sur la gestion des niveaux de difficultés. Si vous avez des pistes je suis preneur... :)

~Peeroflo

pour le niveau de difficulté
on peut classer les algos par niveau croissant
voir l'excellent article
http://naxos.fr.free.fr/sudoku/hints.html
qui présente les algos dans un ordre proche (à mon avis) de la hiérarchie
croissante des difficultés
si tous les algos sont présents dans le solveur
on inhibe ceux de niveau supérieur à 2 (cellule verrouillée, candidat unique)
on fait tourner le solveur en entrant les chiffres un à un, pour les problèmes très faciles le solveur va trouver la solution sans utiliser tous les chiffres si nous notons 1 un problème résolu avec tous les chiffres nous noterons 0 un problème résolu avec tous les chiffres moins 1 et ainsi de suite
si tous les chiffres sont utilisés on notera le problème 1
on va activer isolément les algos par ordre croissant, d'abord bigramme nu puis trigramme nu, puis bi(tri)gramme caché en valorisant les algos, par exemple 1 pour bigrammes nus, 2 pour trigrammes nus, et bigrammes cachés,3 pour trigramme cachés, 4 pour formation en x, ou sword fish si l'une de ces techniques prises isolément permet de résoudre on notera 1 plus son poids, sinon on les lancera conjuguées et on notera leur check somme
si toutes ces techniques ne permettent pas l'atteinte du résultat on lancera l'essai erreur en ajoutant 1 point ou 2 par profondeur nécessaire
Attention une telle notation s'applique à la résolution informatique du problème, elle n'est pas nécessairement égale au niveau de difficulté perçu par un solveur humain
Quand à la question sur la place des cellules masquées par rapport au centre, il faut remarquer qu'il n'y a pas de raison à priori, on pourrait
tout aussi bien proposer un problème avec des places aléatoires, mais cela renforce la difficulté du problème pour un humain, et ne permet pas rapidement de placer un ou deux chiffres, par contre quand on génère une grille aléatoire il est plus facile (lorsque ne sont mis en oeuvre que des algos de niveau 1) d'arriver à une solution acceptable en placant ses chiffres aux quatre coins ce qui pourrait expliquer des problèmes ayant
plus souvent cette configuration

Citation:

---

Envoyé par random

pas du tout
tu as une grille complète
un solveur avec sa grille de résolution

tu pars d'une grille temporaire vide
tu enchaines

faire
tirage au sort d'une case de la grille complète
ajout dans la grille temporaire
ajout dans la grille de résolution
appel solveur
tant que problème non résolu

quand le problème est résolu la grille temporaire est ta grille problème
et tu as comme toujours niveau problème=niveau solveur

---

Il faut juste tirer une nombre dans la liste des possibles d'une case, sans quoi c'est bof :| Pour ça, il faut avoir un solveur de toutes les grilles, mais ne reconstruire effectivement qu'avec un certain nombre de règles.
J'ai l'impressionq ue le niveau facile est composé des règles 0 et 1, le niveau moyen est avec la règle 3, puis le difficile/diabolique avec la règle 2 - celle qui cherche les doubles, triples, ... -
On pourrait rajouter la règle des doubles/... implicites.

je me suis mal exprimé

quant tu dis miles

Il faut juste tirer une nombre dans la liste des possibles d'une case, sans quoi c'est bof

en fait tu pars d'une grille résolue, quant tu tires une case tu ne tires pas son contenu, qui est figé, tu tires la position de la case

Ah, OK, comme ce à quoi je pensais aussi ;)
Faut juste choisir une grille au départ :|

J'ai mis à jour ma version du sudoku, vous pouvez la récupérer par CVS sur sourceforge : http://sourceforge.net/projects/sodoku
J'ai ajouté une possibilité de résolution "à la main", il suffit de rentrer la grille, faire solve->init, puis de sélectionner ce qu'on veut dans les menus et la grille est complétée sous vos yeux ;)
Ce qui m'a permis de constater que la première grille de DrTopos est une grille moyenne, je dirai - j'ai juste eu à chercher des doublets, triplets ou plus dans une ligne -.
En ce moment, je suis intéressé par les doublets, triplets, ... cachés, ça peut peut-être permettre de résoudre plus de grilles insolvables pour l'instant !
Et aussi faire des griles de grilles, ... - voir Pour la science sur l'imagerie médicale, il y a un petit article à ce sujet ;) -

Salut à tous,

Et bien moi aussi, j'ai ecris un petit soft qui permet de résoudre toute grille de sudoku (enfin à ce jour, y compris celles citées plus haut).

Mon soft fonctionne ainsi:

Je définis :
- un tableau de 9x9 pouvant prendre les valeurs 0 à 9 (0=inconnu),
- un tableau de 9x9 boolean (true = case connue dès le départ et donc ok, a priori!),


Mon algo fait ceci:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

Etape 0: - initialisation de la grille à 0 - mise à jour de grille avec les cases connues au départ - initialisation de x et y à 1 pour balayage de la grille - initialisation de Recherche1ereGrille à true   Etape 1: - tant que valeur de la case[x,y] connue => si Recherche1ereGrille => passer à la case suivante => sinon => passer à la case précédente   - si case[x,y]=9 => mettre 0 dans case[x,y] et passer à la case précédente non connue! - sinon => incrémenter la valeur de la case[x,y] (si 0 mettre 1, si 2 mettre 3, ..., si 8 mettre 9; et c tout!) => si AllOk(*) => passer à la case suivante   - si "pas d'autre solution" => aller à Etape 4 - si "pas encore résolu" => aller à Etape 1   Etape 2: - initialisation Recherche1ereGrille à false - Afficher la grille   Etape 3: - Si bouton solution pressé à nouveau => initialisation de x et y à 9 => aller à Etape 1   Etape 4: - Fin     AllOk(*) ce sont les règles que je teste après avoir incrémenté la valeur de la case en cours: renvoie true si: - valeur de la case[x,y] n'existe pas ailleurs dans la ligne y ET - valeur de la case[x,y] n'existe pas ailleurs dans la colonne x ET - valeur de la case[x,y] n'existe pas ailleurs dans le carré (3x3) contenant la case[x,y]

---

Et voila!

sbadecoder : Ton algorithme n'a aucun intérêt puisqu'il s'agit juste d'un algo par essai de toutes les valeurs possibles dans une case... Avec cette méthode tu ne vérifie même pas si la grille a bien une seule solution, juste qu'elle en a une.
Les algorithmes discutés ici sont des algorithmes à base de règles, qui ne font pas de suppositions et donc qui ne trouvent une solution que si il y en a une, et une seule possible.

--
Jedaï

N'empêche que comme ça il est pas bloqué son algo... souvent au Sudoku tu dois à un moment ou un autre faire des choix

Citation:

---

Envoyé par @drien

N'empêche que comme ça il est pas bloqué son algo... souvent au Sudoku tu dois à un moment ou un autre faire des choix

---

Non ! Si l'on a un choix à faire, c'est qu'il y a une règle qui n'a pas été appliquée.

Citation:

---

Envoyé par 2Eurocents

Citation:

---

Envoyé par @drien

N'empêche que comme ça il est pas bloqué son algo... souvent au Sudoku tu dois à un moment ou un autre faire des choix

---

Non ! Si l'on a un choix à faire, c'est qu'il y a une règle qui n'a pas été appliquée.

---

Il y a une preuve quelque part?

Citation:

---

Envoyé par Jean-Marc.Bourguet

Citation:

---

Envoyé par 2Eurocents

Citation:

---

Envoyé par @drien

N'empêche que comme ça il est pas bloqué son algo... souvent au Sudoku tu dois à un moment ou un autre faire des choix

---

Non ! Si l'on a un choix à faire, c'est qu'il y a une règle qui n'a pas été appliquée.

---

Il y a une preuve quelque part?

---

Je n'en ai pas.

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 !