Je me suis posé la question de la génération en Java d’un grille de Sudoku. Pour arrivé à obtenir une grille aléatoire, j’ai entrevu deux solutions :
– Utiliser un algorithme complexe utilisant le « backtracking » pour revenir en arrière si aucune solution ne permet de résoudre le problème.
– Utiliser un framework de programmation par contrainte.
C’est la seconde solution que j’ai mis en oeuvre, et que je détaille…
Qu’est-ce que le Sudoku ?
« Le principe semble en avoir été découvert en 1979 par Howard Games sous le nom de Number place. Les premières grilles ont été publiées dans la revue Math, puzzles and logic problems avec un modeste succès…
…Sudoku est connu sous sa forme actuelle depuis 1984 au Japon et s’est fortement propagé dans le monde en 2005 » (cf : http://www.mots-croises.ch/Manuels/Sudoku/histoire.htm)
Une grille de Sudoku contient des chiffres qui doivent respecter les trois règles :
- Chaque colonne doit contenir tous les chiffres de 1 à 9
- Chaque ligne doit contenir tous les chiffres de 1 à 9
- Chaque pavé de 3×3 doit contenir tous les chiffres de 1 à 9
Exemple de grille :
L’objectif est donc de trouver tous les chiffres manquants.
Utiliser la programmation par contraintes.
Aprés études des différente solutions, j’ai opté pour la programmation par contraintes. Ce type de programmation permet via l’utilisation d’un framework adapté, de définir les contraintes d’un problème pour en obtenir une ou des solutions. Ces frameworks embarquent des algorithmes de résolution bien loin de mes compétences.
L’objectif via l’utilisation de la programmation pas contraintes, est de definir l’univers de notre problème et d’en définir les contraintes. Le framework se charge ensuite de trouver l’algorithme le plus adéquat pour trouver la solution.
Voici sur wikipedia la liste des frameworks : http://fr.wikipedia.org/wiki/Programmation_par_contraintes
J’ai sélectionné CHOCO car c’est un framework non-commercial (url : http://choco.sourceforge.net/).
La définition des contraintes via CHOCO
Définition d’une valeur pour une case (hypothèse de départ)
Iterator iter = predefSlots.iterator();
while (iter.hasNext()) {
Slot slot = (Slot) iter.next();
this.post(this.eq(px[slot.getX()][slot.getY()], slot.getValue()));
System.out.println("Hypothese : " + slot);
}
- predefSlots est une liste d’objets Slots définissant une case par ses valeurs x,y,value.
- Ma classe de Sudoku étends la classe Problem du framework, ce qui me permet d’utiliser this.post pour ajouter une contrainte.
- j’ai définis deux Matrices (pour me simplifier la vie) l’une définissant p(x)[x][y] et la seconde p(y)[y][x].
Cette contrainte indique donc que P(x)[valeurPrédéfinieX][valeurPrédéfinieY] doit etre égale à : valeurPrédéfinie.
Les chiffres des colonnes doivent être uniques.
for (int i = 0; i < 9; i++) {
this.post(this.allDifferent(px[i]));
this.post(this.allDifferent(py[i]));
}
- Contrainte : P(x)[Colonne] doivent tous être différent (this.allDifferent)
- Contrainte : P(y)[Ligne] doivent tous être différent (this.allDifferent)
C’est la première règle du jeu, chaque ligne et colonne ne doit contenir qu’une fois chaque valeurs!!!
Chaque case de P(x) doit être équivalente à son opposée dans P(y).
// b : px[i][j] = py[j][i]
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
this.post(this.eq(px[i][j], py[j][i]));
}
}
- Contrainte : P(y)[i][j] = P(x)[j][i]
Pourquoi ? me simplifier le travail pour valider que chaque case de chaque colonne est unique, j’utilise deux Matrices, qui doivent bien sùr être totalement identiques.
Chaque pavé de 3×3 ne doit contenir que une seule fois chaque chiffre !!!
// Constraint 2 : 3x3 Girds should be unique.
for (int i = 0; i < 3; i++) {
int it = i * 3;
for (int j = 0; j < 3; j++) {
int jt = j * 3;
this.post(this.allDifferent(new IntVar[] { px[it][jt],
px[it][jt + 1], px[it][jt + 2], px[it + 1][jt],
px[it + 1][jt + 1], px[it + 1][jt + 2], px[it + 2][jt],
px[it + 2][jt + 1], px[it + 2][jt + 2] }));
}
}
- Parcours de chaque lignes / colonnes (1 à 3 car fonctionnement par groupe de 3).
- Doivent être différent : P(x)[x][y], P(x)[x][y + 1], P(x)[x][y + 2], P(x)[x + 1][y], P(x)[x + 1][y + 1], P(x)[x + 1][y + 2], P(x)[x + 2][y], P(x)[x + 2][y + 1], P(x)[x + 2][y + 2]
- Pa
Et voila, c’est terminé…. simple non ? 🙂
Maintenant il suffit de demander à Choco de résoudre le problème :
Résolution par Choco
try {
problem.propagate();
} catch (ContradictionException e) {
System.err.println("This problem is over-constrained");
// System.exit(-1);
}
System.out.println("-----------------------------------------");
System.out.println(" Solve ");
System.out.println("-----------------------------------------");
if (problem.solve() == Boolean.TRUE) {
System.out.println("the problem has at least one solution");
System.out.println(problem.toString());
}else {
System.out.println("the problem has no solution");
}
System.out.println("the problem has " + problem.getSolver().getNbSolutions() + " solutions");
- 1) Propagate, permet de propager les contraintes à l’ensemble du problème, afin de savoir si deja le probleme est insoluble.
- 2) Solve, permet de trouver 1 réponse au problème. bien sùr l’utilisation de solveAll est possible, mais peut être très coûteuse en temps car nous ne controllons pas le nombre de solutions possible à notre grille….
Exemple de résultat de mon code JAVA :
Hypothese: [5][2] : 8
Hypothese: [3][2] : 2
Hypothese: [5][7] : 6
Hypothese: [6][5] : 8
Hypothese: [1][5] : 5
-------------------------------
---------- Solve ----------
-------------------------------
the problem has at least one solution
-------------------------------------
| 7 | 8 | 2 | 4 | 5 | 1 | 9 | 3 | 6 |
| 5 | 9 | 1 | 6 | 7 | 3 | 2 | 4 | 8 |
| 4 | 3 | 6 | 2 | 9 | 8 | 1 | 5 | 7 |
| 6 | 7 | 9 | 8 | 3 | 4 | 5 | 2 | 1 |
| 1 | 2 | 8 | 9 | 6 | 5 | 3 | 7 | 4 |
| 3 | 5 | 4 | 7 | 1 | 2 | 8 | 6 | 9 |
| 8 | 4 | 3 | 1 | 2 | 7 | 6 | 9 | 5 |
| 9 | 1 | 5 | 3 | 4 | 6 | 7 | 8 | 2 |
| 2 | 6 | 7 | 5 | 8 | 9 | 4 | 1 | 3 |
-------------------------------------
the problem has 1 solutions
-- solve => 1 solutions
-- 203[+0] millis.
-- 40[+0] nodes
Voila, bientôt une application en ligne de Sudoku 🙂
Si vous voulez le code source, n’hesitez pas à me contacter, un simple lien vers mon site et il sera à vous.
Et on peut même jouer au sudoku en ligne : http://www.sudoku.free.fr
Bonjour,rnTout ça c’est bien, mais pour moi le problème de la solution unique à un sudoku pour qu’il soit "valable" reste en suspend. Comment tester toutes les solutions (théoriquement et non spécifiquement à ce joli petit programme !) ?rnProgrammer la création d’un sudoku : moyennement facile. Programmer la résolution un sudoku : facile. Mais faire un programme qui assure que les sudokus produits n’ont qu’une solution une et unique, ça…rnSi tu as une piste efficace, ça m’intéresse !!!rnMerci 😉
Voilà un artcile qui pourrait vous plaire. Sur le site d’ E-tud.com, un portrait a été réalisé sur Narendra Jussien, un enseignant-chercheur qui a introduit le Sudoku dans une école d’ingénieur (EMN). Je vous conseille d’y jeter un coup d’oeil, c assez sympa! De plus vous pourrez laisser vos commentaires sur le blog du site!
Bonjour,Mikaelov, Pour savoir si le sudoku a plus d’une solution sans les tester toutes avec un solveAll, tu peux utiliser le nextSolution pour t’arreter des la deuxième solution (attention il faut impérativement faire un solve avant) :pb.solve();Boolean isFeasible = pb.nextSolution();Adjanakis, as tu toujours ton erreur avec le alldiff ? Est ce que tu utilisesdes constantIntVar pour les cases fixées du sudoku ? je crois qu’il y a un bug à ce niveau. Sinon peux tu m’envoyer ton code ?N’hésitez pas à utiliser la mailing list de choco.Hadrienps : l’applet njussien.e-constraints.ne… est assez sympa et a été faite avec choco
bonjour, es ce que quelqu’un pourrait m’expliquer comment on programme un sudoku mais en ADA ???
bonjour!je suis en DUT informatique 2eme année !je dois programmer le sudoku en java avec une interface graphiqueça serai super sympa que tu me file le code source s’il te plaitmerci !! 🙂
Bonjour,
je dirais que c’est vraiment très remarquant comme travail, bien expliqué, bonne interprétation, je suis très intéressé par la programmation par contraintes, et j’aimerai bien jeté un coup d’oeil sur ton code, si c’est possible de me le passer.
Merci
Bonjour,
je vous remercie infiniment pour cet article, je suis intéressée par le code, si c’est possible de me le passer.
et merci d’avance.
Bonjour, je serais interessé par le code de cet article si c’est toujours possible. Je pourrais également ajouter un lien vers votre site depuis mon site personnel. Merci d’avance
bonjour,
je voulais aussi acquérir comme certains le code source.
Je suis actuellement en terminale, et pour mon projet d’ISN (informatique et science du numérique) qui est de créer un sudoku jouable sous plusieurs niveau (temps pour le finir de plus en plus rapide selon la difficulté choisie), j’aurai besoin de ce code, du moins pour m’en inspirer.
merci d’avance 🙂
Bonjour,
je vous remercie infiniment pour cet article, je suis intéressée par le code, si c’est possible de me le passer.
et merci d’avance.
Bonjour
Merci bien pour cet article et toute les explications du code. Je développe une application se base sur la résolution par contraintes et je ne sais pas encore si je vais travailler par choco ou non.
Je veux bien avoir ce code s’il est encore disponible ^_^
Merciii d’avance 🙂
Salut,
Tres bien expliquer comme toujours 🙂
Je t’encourage pour la suite !
Es ce que le code est encore disponible ? j’aimerai bien l’obtenir si possible
Merci pour tout !
J’aimerais bien voir le code source pour comprendre la conception de la grille.
je serai également intéressé par le code source