Discussion :

[DrTopos]

La chose importante est d'abord de représenter la grille de telle façon que chaque case puisse contenir tous les chiffres 'candidats'. On peut par exemple réserver un tableau de 81 entiers de 16 bits. Sur ces 16 bits on en utilise 9 pour indiquer les chiffres candidats: le bit 0 pour le chiffre 1 etc.... le bit 8 pour le chiffre 9. Les 7 bits restants peuvent servir de flags pour diverses optimisations. Pour l'instant je n'en voie qu'une, qui est mettre l'un de ces bits à 1 quand la case est résolue (i.e. ne contient qu'un seul candidat), car tester qu'un groupe de 9 bits contient exactement 1 bit à 1 est une opération plus complexe que tester un flag.

Commencer par remplir la grille de la façon suivante:

1. si la case est préremplie, la marquer résolue et mettre à 1 le bit du chiffre qu'elle contient,
2. si la case n'est pas préremplie mettre le flag 'résolue' à 0 et marquer tous les chiffres comme candidats.

Ensuite appliquer les méthodes suivantes. Ces méthodes sont classées selon un ordre de priorité, la priorité 0 étant la première à mettre en oeuvre. On passe à la priorité suivante quand on ne peut plus appliquer les règles d'un niveau de priorité. On revient au niveau de priorité 0 chaque fois qu'on résoud une case, ou quand on ne peut plus appliquer les règles du dernier niveau.


priorité 0: (à appliquer à toutes les cases résolues) effacer (mettre le bit à 0) le candidat correspondant à la valeur de la case résolue dans toutes les cases de la même ligne/colonne/carré que la case résolue.

priorité 1: (suggérée par Miles) rechercher dans chaque ligne/colonne/carré les chiffres que ne sont candidat que dans une seule des 9 cases, et effacer les autres candidats de cette case.

priorité 2: (suggérée par Miles) rechercher dans chaque ligne/colonne/carré les couples de chiffres qui sont candidats ensembles dans les deux mêmes cases et seulement ces deux cases, et effacer dans ces deux cases les autres candidats. Même chose pour trois chiffres candidats dans trois cases et ces trois cases seulement, etc jusqu'au nombre maximal de candidats par case (9 mais éventuellement moins si on fait un petit comptage du max après avoir appliqué les priorités 1 et 2).

priorité 3: (très imortant je crois, car sans cette règle je n'aurais clairement pas pu résoudre la grille que j'ai proposée) rechercher dans chaque carré si un chiffre n'est candidat que dans une ligne (au plus 3 cases) ou une colonne (au plus 3 cases) de ce carré. Effacer alors ce candidat dans les 6 autres cases de la ligne ou de la colonne.


Je ne sais pas si cette méthode permet de résoudre les grilles 'diaboliques', mais elle m'a permis de résoudre celle que j'ai donné en exemple.

P.S. 1 Je ne pense pas qu'il soit utile de mettre tes 770 lignes de code dans un post. A la limite il vaudrait mieux faire un petit résumé de ta méthode.

P.S. 2 Si Trap D veut bien nous expliquer comment il fait ce serait sympa.

[Trap D]

J'ai utilisé un algo avec backtrak.

J'ai un tableau 9 X 9 représentant le sudoku, les cases exposées (comme on dit paraît-il dans la littérature) contenant la valeur assignée, les autres contenant zéro.

J'ai créé une structure pour les cases du sudoku contenant
le nombre de valeurs possibles
le tableau des valeurs possibles
la valeur en cours du tableau des valeurs possibles sélectionnée dans le Sudoku
J'utilise un tableau 9 X 9 de cette structure

J'initialise le tableau de structure, et dans cette phase, si je rencontre une case non exposée avec une seule possibilité je la recopie dans le sudoku et je recommence l'initalisation en tenant compte de cette nouvelle case

A la fin de la phase d'initialisation si le sudoku n'est pas terminé (ce qui arrive parfois), je commence le backtrak proprement dit, c'est-à-dire j'essaye successivement toutes les possibilités et dès que j'échoue j'essaye la prochaine valeur acceptable si possible sinon je reviens à la case précédente pour essayer la prochaine valeur possible etc, etc.

Ce n'est pas optimisé, il faut faire attention dans les opérations de retour arrière, mais ça tourne correctement.

[DrTopos]

Merci Trap D pour tes explications.

En principe, en utilisant du backtrack, on fait des essais exhaustifs, et donc on est sûr de trouver la solution (si elle existe). L'inconvénient c'est qu'on risque de refaire souvent les mêmes calculs (c'est un phénomène bien connu en PROLOG par exemple).

Je viens de retester (toujours à la main, car je n'ai rien programmé) la méthode que j'ai indiquée sur la grille suivante, elle aussi annoncée comme 'Hard':

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
x 7 x   x 1 x   x 9 x
9 x x   8 x x   x x 7
x x 3   x x x   x x 6
 
x 4 x   x x 1   5 x x 
x 3 x   x x x   x 1 x
x x 2   7 x x   x 6 x 
 
5 x x   x x x   6 x x
6 x x   x x 5   x x 2
x 8 x   x 2 x   x 7 x

et ça a marché à nouveau.

Je crois que l'avantage de ma méthode sur celle de Trap D est justement l'absence de backtrack. C'est le fait qu'on conserve à tout moment les candidats possibles dans chaque case, qui fait qu'on n'oublie jamais le résultat d'un calcul, ce qui n'est pas le cas avec le backtrack. En fait, on traite toutes les possibilités en parallèle. Ce qui m'etonne d'ailleurs, c'est que d'après tes explications, tu conserves autant d'informations que moi. Ton tableau des valeurs possibles est l'ensemble de mes candidats. Donc je crois que tu as besoin du backtrack parce que tu tiens absolument à résoudre des cases, alors que mon seul soucis est de réduire le nombre de candidats dans chaque case.

Je me suis aperçu que la règle que j'ai appelée priorité 3 peut (et sans doute doit) être perfectionnée comme ceci (bien que ceci n'ait pas été utile pour les deux exemples que j'ai traité):

si les éléments d'un ensemble de 1, 2 ou 3 chiffres ne sont candidats que dans une ligne ou une colonne d'un carré, effacer ces éléments des six cases de la ligne ou de la colonne qui ne sont pas dans le carré.

Le lien carré/ligne ou carré/colonne est plus fort que le lien ligne/colonne car il concerne 3 cases au lieu d'une seule. C'est ça qui fait l'efficacité de la règle priorité 3.

Maintenant, ce qui serait intéressant serait d'avoir un algo de génération de grilles bien posées (i.e. avec une seule solution). Quelqu'un a-t-il réfléchi à cela ?

[FrancisSourd]

Maintenant, ce qui serait intéressant serait d'avoir un algo de génération de grilles bien posées (i.e. avec une seule solution). Quelqu'un a-t-il réfléchi à cela ?

Comme suggéré dans le wikipedia anglais, on part d'une case vide et on rajoute des cases. Plus précisément:
Après chaque case rajoutée (au hasard), on appelle le solveur.
S'il y a plus d'une solution, on continue à rajouter une case.
S'il y a une seule solution, on arête.
S'il n'y a pas de solution, on enlève une case au hasard.

La difficulté du sudoku s'évalue en fonction des règles qu'il faut mettre en oeuvre pour le résoudre. On peut aussi se dire que si à certaines étapes, on ne peut faire qu'un raisonnement le sudoku est plus dur que si on a le choix entre plein de déductions possibles à chaque étape.

[FrancisSourd]

Je crois que l'avantage de ma méthode sur celle de Trap D est justement l'absence de backtrack.

Sans backtrack, il y a des grilles qui résisteront très vraisemblablement. (Le problème nxn est NP complet, les règles sont polynomiales). C'est une idée, pas une preuve: comme on travaille sur un problème 9x9, le problème est de taille fini (donc tout énumérer prend un temps constant)

En pratique, j'ai dû moi-même backtracker sur certaines grilles même si je connais les règles que tu utilises (encore une fois cela ne veut pas dire que l'algo exécuté par une machine n'aurait pas trouvé: c'est l'algo exécuté par moi qui n'a pas trouvé!) Mais bon, c'est aussi arrivé à des collègues plus exercés que moi à la résolution de sudokus.

[Trap D]

Créer une grille est facile. La difficulté est évidemment de trouver les cases à exposer.
J'y suis allé de manière empirique, (en fait c'est la méthode de Wilkipédia) en tirant des cases au hasard, au départ 3 dans chaque carré, mais celà ne donne pas des résultats très satisfaisants, en général celà donne des Sudokus assez faciles à résoudre.
J'essayerai cette après-midi en partant avec 2 cases par carré pour voir.
Le backtrak a l'avantage de trouver toutes les solutions, c'est utile quand on essaye de créer les grilles.

[FrancisSourd]

J'ai donc écrit comme promis un petit papier sur le calcul dans les corps GF(2^n) (aussi notés F(2^n)). Il se trouve ici. Il a une portée plus générale que le problème posé dans ce fil. Bonne lecture et n'hésitez pas à critiquer.

Même si F(2^n) ne semble plus à la mode dans ce sujet, j'ai lu ton petit papier que j'ai bien apprécié et qui m'a permis de me sentir moins ignorant (je ne suis sans doute pas un lecteur objectif).
Si tu as l'optique de diffuser le papier, cela serait bien si tu pouvais illustrer une application pour les informaticiens.

[DrTopos]

Si tu as l'optique de diffuser le papier, cela serait bien si tu pouvais illustrer une application pour les informaticiens.

Effectivement, ça serait bien. Je vais y penser (je suis un peu débordé en ce moment). Ce sera sans doute une application en crypto. Je mettrai alors un lien sur ma page enseignement, ou peut être qu'on pourrait mettre le papier sur Developpez.com, dans les tutoriels.

Pour revenir au backtrack, il est en fait lui aussi parallélisable (c'est à dire éliminable). En pratique, sauf si on utilise des machines fonctionnant vraiment en parallèle, ce ne sera pas avantageux. Dans le cas du Sudoku, on peut faire comme ceci. Quand plus aucune règle ne s'applique, on choisit une case contenant 2 candidats (s'il y en a une), on duplique la grille complète (en conservant les candidats trouvés), et dans la case choisie on met l'un des candidats dans une grille, l'autre candidats dans l'autre. On traite alors les deux grilles en parallèle. L'une d'entre elles va aboutir à un échec (il faudrait d'alleurs préciser comment on détecte cet échec, j'espère que c'est pas une violation des règles du jeu, du genre deux cases résolues avec le même chiffre dans une même ligne, mais ce n'est pas du tout certain), l'autre va donner la solution. On peut faire la même chose avec une case contenant 3 candidats, en faisant trois copies de la grille etc... Bien entendu, en cas de nouveau bloquage on peut dupliquer à nouveau.

[DrTopos]

Après chaque case rajoutée (au hasard), on appelle le solveur.

C'est une méthode un peu brutale. J'avais pensé qu'on aurait peut-être un algo plus direct. En fait, la méthode consistant à appeler le solveur est celle qui est utilisée pour engendrer les grilles de Sokoban (Un autre jeu Japonais, qui a fait fureur il y a quelques années. Au département de maths de P7, il y a eu une vague de folie Sokoban, plus grand monde faisait des maths).

La difficulté du sudoku s'évalue en fonction des règles qu'il faut mettre en oeuvre pour le résoudre. On peut aussi se dire que si à certaines étapes, on ne peut faire qu'un raisonnement le sudoku est plus dur que si on a le choix entre plein de déductions possibles à chaque étape.

Je ne comprends pas très bien ce que tu veux dire (où alors je le comprends de travers). Il me semble au contraire que la difficulté de la recherche d'une solution d'un problème réside dans les étapes où on a un choix à faire, car si on fait un choix qui n'est pas bon, on va passer beaucoup de temps à s'en apercevoir pour finalement revenir (backtrack) essayer le choix suivant. D'où l'intérêt des méthodes sans choix, qu'on obtient en 'parallélisant', c'est à dire en faisant en sorte de traiter tous les choix simultanément, ce qui implique évidemment une méthode plus ou moins symbolique (par exemple, dans le cas du Sudoku, de changer le type des cases de 'chiffre' à 'ensemble de chiffres'). C'est d'ailleurs une méthode analogue qui est utilisée dans le théorème de Moore pour transformer un automate non déterministe en automate déterministe, ou dans l'algorithme de Knuth utilisé par BISON/YACC, pour établir l'automate à partir de la grammaire (chaque état traite des règles de grammaires 'candidates' en parallèle). Il me semble d'ailleurs d'après ce que j'ai lu dans les articles de 'Constraint Programming' que tu as cité que cette idée de traitement en parallèle est centrale. On peut interpréter une famille de candidats pour un poste unique comme une contrainte sur le contenu final du poste.

[FrancisSourd]

Après chaque case rajoutée (au hasard), on appelle le solveur.

C'est une méthode un peu brutale.

Effectivement;-)

La difficulté du sudoku s'évalue en fonction des règles qu'il faut mettre en oeuvre pour le résoudre. On peut aussi se dire que si à certaines étapes, on ne peut faire qu'un raisonnement le sudoku est plus dur que si on a le choix entre plein de déductions possibles à chaque étape.

Je ne comprends pas très bien ce que tu veux dire (où alors je le comprends de travers).

Ce que je voulais dire, c'est que c'est plus facile si, à tout moment de la progression dans le jeu, il y a plusieurs cases qui peuvent être complétées sans backtrack. Autrement dit, s'il n'y a qu'une case qui peut être remplie à chaque étape, c'est plus difficile de progresser dans le jeu que si, à chaque étape, on peut remplir dix cases.

[Matthieu Brucher]

La règle priorité 3 est très intéressante, j'en avais pas encore eu besoin explicitement, je crois, même pour des hards...

Modification de la règle 2 : pour les groupes de 3 chiffres, si on a un groupe de 3 chiffres dans une case et que des duos de ce groupe se retrouvent dans les cases d'un regroupement associé, on élimine ce groupe des autres cases. JE ne sais pas si je suis clair

En tout cas, ce problème me plaît de plus en plus je voulais faire un solveur un jour, mais là, je crois qu'il sera fini avant que je ne commence à coder

[DrTopos]

JE ne sais pas si je suis clair

non, pas vraiment... pourrais-tu donner des précisions, voire un exemple ?

[Matthieu Brucher]

Par exemple, si on a le triplet(1, 2, 3) et 2 autres couples (1, 2) et (2, 3) dans le même regroupement, on peut ôter 1, 2, 3 de tous les autres groupes de ce regroupement.

[schuler]

Bonjour

Je ne suis pas programmeur, mais "résolveur" de sudokus, et je cherche un algorithme performant : comment limiter le nombre d'explorations inutiles (ce qui a peu d'intéret si l'on programme)

En d'autres termes, une fois écrites les solutions "banales" qui apparaissent en croisant lignes et colonnes, comment aborder la suite ?

Suggestions :

- Ligne, colonne ou petit carré contenant le plus de chiffres ?

- S'intéresser au chiffre le plus fréquent dans la grille ?

Toute autre idée est la bienvenue, merci.

[Matthieu Brucher]

On a donné plusieurs règles pour avancer, je suis en train de les implémenter en C++ sous VS et avec GCC.
Voici les 2 projets nécessaires : http://matthieu.brucher.free.fr/Sodoku.rar et http://matthieu.brucher.free.fr/Tester.rar
Le premier, c'est le Sodoku, le deuxième, c'est un outil pour tester si les fonctions implémentées font bien leur boulot, c'est pas indispensable, mais presque.
Sinon, il faut aussi QT4, j'ai fait un projet pour dans le forum C++.

[Matthieu Brucher]

http://matthieu.brucher.free.fr/Setup.msi
Mon début de solver de Sodoku, il implémente juste la règle 0.
On peut sauvegarder et charger un jeu, il y a un exemple fourni avec.

[Bloon]

Etant totalement hermétique aux mathématiques, j'ai pris une approche totalement objet qui donne de bons résultats, par exemple avec les grilles de DrTopos :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
2 8 3  6 7 1  9 4 5
9 7 6  5 4 8  2 3 1
4 1 5  3 9 2  8 7 6
 
5 6 7  4 1 9  3 8 2
8 3 4  2 6 7  1 5 9
1 9 2  8 3 5  4 6 7	
 
3 2 1  7 8 6  5 9 4
7 5 8  9 2 4  6 1 3
6 4 9  1 5 3  7 2 8

Code :

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

1
2
3
4
5
6
7
8
9
10
11
4 7 8  5 1 6  2 9 3
9 6 5  8 3 2  1 4 7
2 1 3  4 9 7  8 5 6
 
7 4 9  3 6 1  5 2 8
8 3 6  2 5 9  7 1 4
1 5 2  7 4 8  3 6 9
 
5 2 4  9 7 3  6 8 1
6 9 7  1 8 5  4 3 2
3 8 1  6 2 4  9 7 5

J'ai pas le courage de vérifier si c'est bon

Mais visiblement, mon programme fonctionne avec les grilles du programme TV

Il faut juste que je corrige la méthode qui cherche la solution qui ne fonctionne pas avec les grilles trop complexes car le retour en arrière n'est pas bien géré.

Les sources Delphi
L'exe

Bloon

[Bloon]

J'ai transformé ma fonction de recherche de solution en fonction récursive et ça semble fonctionner.

J'ai mis ça sur mon forum pour ne pas surcharger ce thread.

Voici en gros l'algorithme mis en oeuvre :

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
Une case appartient à 3 ensembles et leur notifie les changements qu'elle subit. Les ensembles réagissent à ces modifications en remodifiant éventuellement d'autres cases. Tout ceci est donc très récursif.
 
Principaux événements :
 
* case.valeur = v
    - si la valeur n'est pas autorisée, erreur
 
* case.valeursPossibles = case.valeursPossibles - v
    - si plus aucune valeur possible dans la case, erreur
    - s'il ne reste qu'une valeur possible, case.valeur = valeur restante
 
* ensemble.onValeurSupprimee
    - si la valeur supprimee n'est plus dans aucune case, erreur (remarque : ce test n'est pas fait au bon endroit dans le source, à modifier)
    - si la valeur supprimee est présente dans une seule case de l'ensemble, case.valeur = v
 
* ensemble.onValeurChangee
    - on supprime la valeur des valeurs possibles des autres cases
 
Les cases n'ayant plus qu'une solution sont donc automatiquement traitées par ce système
 
pour trouver la solution, une petite fonction récursive :
 
trouveSolution(level)
begin
  caseTrouvee = trouveCase(level); // level est initialisé à 2. le niveau c'est le nombre de possiblités restant sur une case
  sauvegarde de toutes les cases
  try
    caseTrouvee.valeur = premiere valeur possible
    trouveSolution(level)
  exception
    restauration des cases
    caseTrouvee.valeursPossibles = caseTrouvee.valeursPossibles - valeur qui a plante le truc
    trouveSolution(level)
  end;
end;

c'est trouveCase qui détermine quand c'est fini (si toutes les cases ont été valorisées).

Bloon

[Matthieu Brucher]

C'est pas une version vraiment basée uniquement sur la connaissance, tu fais de la force brute à la fin, non ?
Perso, j'ai implémenté la règle 1 et la 3 que j'ai renommée en 2 , et elle me résoud pas mal de niveaux difficiles- enfin, j'ai juste implémenté une moitié de la règle puisqu'elle existe en 4 variantes -, sauf la grille 1 de DrTopos
Et ce n'est pas de la force brute
J'ai mis à jour mon Sodoku en ligne.

[Bloon]

Non ce n'est pas de la force brute : je commence par résoudre ce qui est évident (cases à une seule possibilité) puis s'il reste des cases, je traite d'abord celles qui ont le moins de possibilités. Si ça déclenche une exception, j'enlève la valeur des valeurs possibles et je pars sur une autre piste.

C'est également basé sur des règles :

• l'affectation d'une valeur enlève la valeur des valeurs possibles des autres cases
• si une case n'a plus qu'une seule valeur possible, elle est affectée automatiquement
• si dans un ensemble de cases une valeur n'est présente que dans les valeurs possibles d'une case, elle est affectée.

J'avais d'autres règles en stock mais je n'ai pas encore eu besoin de les implémenter. Là je vais ajouter un mécanisme de validation parce que le prog me dit que c'est bon mais j'ai la flemme de vérifier

Bloon