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.