Automatiser la réponse au Sudoku

Bonjour,
J'ai essayé de programmer en Delphi un "solutionneur" de Sudoku. Hélas mon algorithme n'est pas assez performant, en effet il trouve la solution des niveaux facile et moyen, quelques difficiles mais aucun diabolique.

Cqfd : Le Sudoku est une grille carrée de 81 cases séparé en 9 carré de 9 cases. elle est pré-remplie avec quelques chiffres et le but est de tout remplir avec cette logique : il doit y avoir tous les chiffres de 1 à 9 sur chaque ligne, sur chaque colonne et dans chaque carré de 9 cases.

Personnellement j'ai bouclé sur chaque case en testant toutes les combinaisons et si il n'y avait qu'une possibilité alors je l'écrivais.

Merci à vous savants amis

Envoyé par -Sylvain Leray-

Bonjour,
Personnellement j'ai bouclé sur chaque case en testant toutes les combinaisons et si il n'y avait qu'une possibilité alors je l'écrivais.

Toute la qualité de l'algorithme va dépendre des règles qui permettent de savoir qu'il n'y a qu'une seule solution dans une case.

D'une manière générale, on ne peut pas tout déduire par de simple règle, il faut donc passer par une méthode énumérative.
On prend s'il n'y a pas de case avec une seule possibilité, on prend une case avec peu de possibilité (disons 2) et on crée deux sous-problèmes qu'on essaie de résoudre de manière indépendante et ainsi de suite. On crée une arborescence de sous-problèmes avec des grilles éventuellement infaisables.
Je crois que l'article SuDoku dans wikipédia (au moins en anglais) est bien fait et donne des pistes vers différentes approches algorithmiques.

Le type de raisonnement utilisé pour résoudre les sudoku est, dans l'esprit, très proche de la programmation par contraintes.
Un article en anglais sur le sujet:
http://www.icparc.ic.ac.uk/~hs/sudoku.pdf

Je ne connaissais pas le Sudoku. Je viens de découvrir (en diagonale) la littérature sur ce sujet. J'ai eu l'idée d'une méthode, qui s'apparente d'ailleurs à de la programmation par contrainte. Je ne l'ai pas testée, donc je ne sais pas si elle est performante. Par contre, il se peut que dans le cas où la grille n'a qu'une solution, on trouve cette solution sans faire aucune recherche (pas d'essais/erreurs).

L'idée est de transfomer le problème en un système linéaire sur un corps fini, qu'on va résoudre par le pivot de Gauss. Le corps fini en question est GF(2^9), qu'on peut voir comme le quotient de l'anneau des polynômes sur Z/2, qu'on notera Z/2[X] par l'idéal (maximal) engendré par un polynôme irréductible. On a de la chance, car le trinôme X^9+X+1 est irréductible modulo 2 (ce n'est pas le cas pour tous les exposants). Evidemment, il faut implémenter le calcul dans ce corps. Un polynôme peut être représenté par un mot de 9 bits. Ce genre de choses est bien conue en cryptographie.

Maintenant, les solutions d'une grille partiellement remplie sont certaines solutions (pas toutes) d'un système linéaire sur ce corps. On va remplir la grille, non pas avec des chiffres, mais avec des éléments de GF(2^9). Evidemment, les seules solutions valables sont celles pour lesquelles les cases contiennent un monôme non nul (un mot de 9 bits avec un seul 1), qui lui représente un chiffre (l'exposant du monôme). C'est cette restriction qui complique le problème (sinon, il ne serait pas NP-complet).

Le système linéaire a au plus 81 inconnues (en fait il y a autant d'inconnues que le nombre de cases vides au départ) et 27 équations linéaires, qui consistent à dire, par exemple pour une colonne que la somme des cases est le polynôme X+X^2+X^3+...+X^9, c'est à dire le mot de 9 bits 111111111. Une fois le système posé, on peut le résoudre par la méthode du pivot. Pour cela il suffit de savoir inverser les éléments non nul du corps GF(2^9). Bien entendu, on établit la table de multiplication et la table des inverses une fois pour toutes. A chaque pivot, on récupère une équation d'élimination, qui donne la valeur d'une inconnue en fonction des suivantes. Si le problème à au moins une solution, on tombe nécessairement après un certain nombre de pivots sur le système 0=0. Il reste alors éventuellement des inconnues pour lesquelles on n'a pas de formule d'élimination. Il faut donner à chaque inconnue restante chacune des 9 valeurs possibles, et tester à l'aide des formules d'élimination si on obtient des monômes. Ceci va éliminer beaucoup de valeurs, et on a certainement une chance de trouver toutes les solution dans un temps (et une occupation mémoire) raisonnable.

Il faut remarquer que les équations d'élimination qui résultent du pivot de Gauss servent précisément à propager les contraintes.

Evidemment, il y a un peu de travail, à commencer par le calcul dans GF(2^9). Mais ça me paraît faisable.

Envoyé par DrTopos

L'idée est de transfomer le problème en un système linéaire sur un corps fini, qu'on va résoudre par le pivot de Gauss. Le corps fini en question est GF(2^9), qu'on peut voir comme le quotient de l'anneau des polynômes sur Z/2, qu'on notera Z/2[X] par l'idéal (maximal) engendré par un polynôme irréductible. On a de la chance, car le trinôme X^9+X+1 est irréductible modulo 2 (ce n'est pas le cas pour tous les exposants). Evidemment, il faut implémenter le calcul dans ce corps. Un polynôme peut être représenté par un mot de 9 bits. Ce genre de choses est bien conue en cryptographie.

Cher Docteur Topos, est ce que cet exposé est écrit avec l'intention que la majorité de personne n'y comprenne pas un mot ? Si j'ai ouvert ce sujet, c'est pour comprendre les explications qu'on m'y donne ! Donc la solution est peut être dans ton message, mais comme je n'ai pas compris un mot, je ne pourrais pas m'en servir.

J'ai cru lire quelque part que la pédagogie c'était d'expliquer des choses compliquées avec des mots simples. J'aimerais vraiment comprendre ce que tu expliques, pourrais tu l'expliquer comme si tu le faisais à un élève de CM2 ?


PS : en lisant ta réponse, j'ai pensé au film les 3 frères...

Même si je n'ai pas tout compris à l'approche de DrTopos, j'ai bien été intéressé par ce qu'il dit: l'idée de voir un sudoku comme un problème d'inversion dans un corps fini m'avait aussi titillé l'esprit il y a qq mois. Je suis bien conscient qu'il est difficile de faire dans un seul message un cours sur ce sujet. Existe-t-il des tutoriels/références sur cette approche et des applications que j'imagine en tomographie discrète, reconstruction de matrices, optimisation inverse...

Je suis désolé si Sylvain n'a pas tout compris, et je le prie de m'en excuser. Ce n'est pas très difficile en fait, mais je voulais juste dans ce post donner une vue d'ensemble de mon idée. Je précise que ça n'est qu'une idée qui m'est venue en prenant connaissance du jeu, et il n'y a aucune garantie qu'elle soit bonne.

Non, je n'écris pas pour qu'on ne comprenne pas, ce n'est pas du tout mon genre, mais il y a des choses qui ne peuvent pas se dire en seulement trois lignes. J'ai remarqué que la plupart des développeurs connaissent le pivot de Gauss, donc je n'ai pas jugé utile de l'expliquer. De même pour le corps GF(2^9), un peu de culture cryptographique suffit en principe. Maintenant, s'il faut expliquer je vais le faire, avec encore une fois le rappel qu'il n'est pas sûr que mon idée soit bonne, c'est à dire qu'elle ne fait peut-être que déplacer le problème. C'est une chose qu'on ne pourra savoir qu'en expérimentant.

En fait, il n'y a que deux choses à expliquer: le pivot de Gauss (éventuellement) et le calcul dans le corps GF(2^9). Je suis tout disposé à le faire, mais je crois qu'il vaut mieux que je prépare un document avec LaTeX plutôt que de faire un post. De toute façon, même s'il s'avère que l'algorithme obtenu n'est pas très bon on aura appris des choses utiles, par exemple pour la crypto. Quant-au pivot de Gauss, il est très souvent utile en algorithmique.

Donc juste un peu de patience, je me colle au calcul dans GF(2^9) (ou même un peu plus général que ça) dès ce soir.

en gros je crois que ce qu'il veut dire c'est que cela consiste tout simplement a resoudre un system d'equation lineaire avec 81 inconnus la tu obtiens plusieurs solutions et il ne te reste plus qu'a choisir celles ou les valeurx de tes inconnues sont uniques.


x1+x2+x3=1+2+3
y1+y2+y3=1+2+3
z1+z2+z3=1+2=3

et

x1 + y1 +z1 = 1 +2 +3
x2 + y2 + z2 =1 +2 +3
x3 + y3 + z3 =1 +2 +3
voila le meme exemple avec 9 inconnues au lieur de 81.


avec bien sur pour certaines variables des donnes par example sera donne par le jeu y2 = 1 et z3 =2 et x1 =2 ;

il sera peut-etre plus judicieux pour accelere le calcul de mettre au bon index la valeur donne je veux dire par la que si 2 est donne alors on l'atribura a y2 et pas y3 .


ai-je bien compris ce dr topos voulez dire ???

Bonjour à tous.

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.

Pour en revenir au Sudoku, j'ai bien peur en fait que la méthode que j'ai proposée ne nous fasse pas tellement avancer. L'idée est de rendre linéaire la contrainte d'avoir des chiffres tous différents dans chaque case. Pour le faire, j'ai proposé de remplacer les chiffres par des polynômes. On peut alors exprimer linéairement la contrainte ``tous différents'', mais la contre-partie est qu'on doit ajouter de nouvelles contraintes à savoir qu'on ne retiendra que les solutions en monômes. Il en résulte que même si la grille n'a qu'une solution en monômes, elle peut avoir de nombreuses solutions en polynômes, et donc qu'on va arriver après quelques pivots au système 0=0, avec encore de nombreuses inconnues en main, auquelles il va falloir donner des valeurs monômiales arbitraires et les tester. Bien entendu, on disposera quand même des équations d'élimination donnant la valeur d'une variable en fonction des suivantes. A quel point cette remontée à l'aide de ces équations va-t-elle simplifier le problème est justement ce que je ne sais pas pour le moment.

zeavan >> Il faut comprendre que je propose de remplacer les chiffres par des polynômes dont les coefficients sont à calculer modulo 2. Donc en fait ton système:

x1+x2+x3=1+2+3
y1+y2+y3=1+2+3
z1+z2+z3=1+2=3

s'écrirait plutôt:

x1+x2+x3=X^0+X^1+X^2
y1+y2+y3=X^0+X^1+X^2
z1+z2+z3=X^0+X^1+X^2

où X est la ``lettre'' de ces polynômes.

Envoyé par FrancisSourd

l'idée de voir un sudoku comme un problème d'inversion dans un corps fini m'avait aussi titillé l'esprit il y a qq mois.

En fait, je ne présente pas le problème comme un problème d'inversion dans un corps fini, mais comme un problème d'inversion de matrice sur un corps fini.

Ceci dit, ton idée que ce serait une inversion d'un élément dans un corps fini est séduisante. Evidemment, il ne peut s'agir que d'un corps beaucoup plus gros que GF(2^9). Si c'est un quotient d'un anneau de polynômes, l'algorithme d'Euclide permettra d'inverser. De toute façon, il y a peu d'espoir qu'on échappe à un problème de complexité combinatoire quelque part.

Je me suis aussi demandé si on ne pourait pas essayer une méthode de réécriture. Autrement-dit, y aurait-il des règles de transformation d'une grille fausse, qui la rendrait un peu moins fausse. En itérant ces transformations on trouverait peut être une grille juste c'est à dire une solution. J'ai un collègue à la fac de Grenoble qui a fait des choses dans ce genre là pour simplifier des ensembles simpliciaux et ça marche très bien. En fait la question serait d'abord d'être capable de mesurer à quel point une solution est fausse.

P.S. J'ai lu l'article que tu as cité, mais j'avoue que je n'y comprends pas grand chose.

Envoyé par DrTopos

J'ai lu l'article que tu as cité, mais j'avoue que je n'y comprends pas grand chose.

Effectivement, je citais plus cet article pour dire que la programmation par contraintes était une bonne approche pour le sudoku.
Pour s'intéresser à la programmation par contraintes, il est mieux d'aller sur le site
http://kti.ms.mff.cuni.cz/~bartak/constraints/
(il y a aussi wikipedia).

Le sudoku utilise à fond la contrainte all-different
http://www.cs.cornell.edu/~vanhoeve/papers/ercim2001.pdf
(mais là encore c'est un article de "spécialistes").

PS: il me semble qu'il y a des liens qui s'établissent entre programmation par contraintes et réécriture.

Je vous expose mon idée, dites moi si elle vous parait cohérente. Parceque j'ai l'impression que j'ai bon, mais dans la pratique ça ne fonctionne pas. J'ai bien peur d'avoir la solution mais d'avoir du mal à l'écrire en Delphi.

NB : désolé si j'écorche du vocabulaire / des normes d'écriture mathématiques.

Pour chaque case de 1 à 81 je par du postulat qu'elle peut recevoir les chiffres de 1 à 9. Liste de chiffre à laquelle j'enlève les valeurs que je trouve :
Sur la même ligne que cette case
Sur la même colonne que cette case
Dans le même carré que cette case.

Si ma liste de possible ne contient plus qu'une valeur alors je l'écris. Sinon, je ne fais rien et je passe à la suivante.

L'écriture d'au moins une case déclenche à nouveau la boucle sur les 81 cases car il se peut qu'une nouvelle solution unique est été créée.

Avec cette logique, les sudokus simples sont tous résolus en moins de 2 secondes.

Le problème arrive lorsque j'ai fini de boucler sur les 81 cases et que je n'ai réussi à en remplir aucune. Je relance alors ma boucle en précisant que je passe en mode "supposition", et là, dès la première case vide trouvée, je lui met la première valeur de ses possibles en notant bien son degré de suposition (ici : 1) et c'est reparti pour 81 cases à boucler jusqu'a retomber sur le problème alors je m'abîme dans les suppositions. Si je tombe sur une case vide avec une liste de possible sans valeur, alors ce degré de supposition est faux. j'efface toute cette supposition je supprime la supposition de la valeur des possibles de la case et je retente une autre valeur.

Moi ça me parait pas mal comme idée, mais dans la pratique ça ne marche pas !
Alors erreur de programmation ou erreure de logique ?

=> En notation mathématique, mon idée ça donne quoi ? (juste pour rire, je sais que j'y comprendrais rien )

Sylvain >> Je viens de faire un sudoku à la main et je peux te dire ceci:

Au lieu de ne rien mettre dans une case quand tu as plusieurs valeurs possibles, tu mets la liste des valeurs possibles. A ce moment là il se peut que tu résolves un carré même si dans toutes les cases traitées il y a plus d'une valeur. Par exemple, j'ai eu ceci dans l'un des carrés:

79 | (2) | (6) |
----------------------
(3) | 19 | 159 |
----------------------
(4) | 189 | 19 |

où les chiffres entre parenthèses sont ceux qui étaient à l'origine dans la grille. On voit que bien que j'ai été obligé de mettre plusieurs chiffres par case, je peux qaund même déduire que la case en haut à gauche contient 7, que celle en bas au milieu contient 8, que celle au milieu à droite contient 5, et il me reste juste les deux case 19 pour lesquelles je ne peux pas décider.

Donc, tu peux rendre ton algo beaucoup plus efficace.

Envoyé par -Sylvain Leray-

Moi ça me parait pas mal comme idée, mais dans la pratique ça ne marche pas !
Alors erreur de programmation ou erreure de logique ?

C'est pas mal comme idée.
Ce qu'il faut bien voir, dès que tu fais des hypothèses, c'est que tu as un arbre (arbre des choix) car tu peux être obligé de faire une seconde hypothèse alors que tu n'as pas résolu (confirmé ou infirmé) le première hypothèse. D'un point de vue algorithmique, tu dois parcourir cet arbre, le plus simple est de le faire par un parcours en profondeur d'abord (fais une recherche google sur ce terme si cela ne te dis rien). Cela permet de bien gérer toutes les hypothèses faites. Fait une recherche sur les algorithmes de résolution de problèmes, algorithmes d'énumération (de solutions), éventuellement regarde aussi "branch-and-bound".

Si on considère l'efficacité de l'algorithme, les règles que tu énonces sont justes mais c'est vrai qu'il existe plein d'autres règles de déduction, comme celles énoncées par DrTopos et Miles.

Sylvain >> S'il te plait, pourrais-tu tester ton algo sur la grille suivante:

Code :

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

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

et me dire ce que ça donne. Merci.

Envoyé par DrTopos

Sylvain >> S'il te plait, pourrais-tu tester ton algo sur la grille suivante:

Code :

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

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

Après avoir écrit en 1 seconde les 4 chiffres sur la première ligne ( 1, 3 5 et 9) mon prog se perds dans le néant et me dit que la grille n'a pas de solution...
Mais je sais que c'est faux, plein de grille officielles finissent en "sans solution" avec mon prog... Si ma logique est bonne c'est mon code qui est mauvais, peut-être devrais-je le poster ici, l'erreur vous sauterait aux yeux ?

C'est une grille que j'ai trouvée sur le net, et qui est donnée comme 'Hard'. Elle a une solution unique autant que je sache, car je l'ai résolue (à la main) par un algo sans retour en arrière. Il doit y avoir de toute façon une faute dans ton programme car je trouve 2 8 3 au début de la première ligne et non pas 2 1 3.

Je n'ai pas le temps tout de suite, mais je t'expliquerai ma méthode ce soir. Elle reprend certaines des suggestions de Miles (et n'a rien a voir avec GF(2^9) !).

@+

Question pour modo :
770 Lignes c'est, je suppose trop long pour être collé ici.
Y a t il possibilité de stocker ce bout de code temporairement sur dev.com le temps de résoudre la question ou dois-je utiliser un site perso ?