Automatiser la réponse au Sudoku

**Matthieu Brucher** · 30/11/2005, 09h06

Dabs le cas ici, déjà tu fais un parcours en profondeur, le truc pour faire de l'alpha-beta ou du minimax, c'est réussir à mettre une fonction de coût, tu peux utiliser le coût qui a été présenté ici, mais je ne suis pas sûr que ce soit efficace.

**cedico** · 30/11/2005, 09h27

Le soucis est que mon jeu ce joue seul, il n'y a pas d'opposant...
Et quelqu'un du forum m'a expliqué hier que ces 2 méthodes étaient surtout utilisées lorsqu'il y avait un opposant dont on évalue la réaction probable...
Alors j'ai l'impression que dans mon cas, ça ne sera pas vraiment adapté...
Concernant le coût, merci pour l'idée, peut-être que je peux améliorer mon algo avec une notion de côut...

**Matthieu Brucher** · 30/11/2005, 09h31

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.

**cedico** · 30/11/2005, 13h39

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 ?

**Matthieu Brucher** · 30/11/2005, 16h39

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

**random** · 30/11/2005, 17h52

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.

**cedico** · 01/12/2005, 10h31

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

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+

**Matthieu Brucher** · 01/12/2005, 11h24

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.

**lbone** · 08/12/2005, 06h06

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....

**random** · 08/12/2005, 11h00

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

**Peerofloo** · 08/12/2005, 20h16

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

**random** · 09/12/2005, 08h45

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

**Matthieu Brucher** · 09/12/2005, 10h30

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.

**random** · 09/12/2005, 11h20

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

**Matthieu Brucher** · 09/12/2005, 14h34

Ah, OK, comme ce à quoi je pensais aussi

Faut juste choisir une grille au départ

**Matthieu Brucher** · 21/12/2005, 08h46

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

-

**sbadecoder** · 30/12/2005, 01h20

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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!

**Jedai** · 30/12/2005, 13h44

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ï