PPC > EXEMPLES > Sudoku



TD Exercice 3

Modéliser le problème et trouver la solution au problème en utilisant le solveur Choco 2.0.

 

Solution Modèle 1


Pour chaque case une variable énumérée allant de 1 à 9

Pour chaque ligne, colonne, carré de 3*3, des contraintes de différence entre chaque couple

Voici le code java en Choco 2.0 de ce premier modèle :

import choco.cp.model.CPModel;
import choco.cp.solver.CPSolver;
import choco.cp.solver.search.integer.valiterator.*;
import choco.cp.solver.search.integer.varselector.*;
import choco.cp.solver.search.integer.valselector.*;
import choco.kernel.model.Model;
import choco.kernel.model.variables.integer.IntegerVariable;
import choco.kernel.solver.Solver;
import choco.Choco;
import java.lang.Math;

public class Sudoku {

public static int n = 9;

public static void main(String[] args) {
long time = System.currentTimeMillis();
System.out.println("Sudoku");
assert Math.rint(Math.sqrt(n))==Math.sqrt(n);
Model m = new CPModel();
IntegerVariable[][] vars = createVariables(m);
postConstraints(m, vars);
Solver s = new CPSolver();
s.read(m);
setHeuristic(s);
s.solve();
displayResult(s, vars);
System.out.println("Time ellapsed: " + (System.currentTimeMillis() - time) + "ms.");
}

// 1. Création des variables
private static IntegerVariable[][] createVariables(Model m) {
return Choco.makeIntVarArray("Case", n, n, 1, n);
}

// 2. Création des contraintes sur les lignes, colonnes, carrés
private static void postConstraints(Model m, IntegerVariable[][] vars) {
for(int i = 0; i < n; i++) {
IntegerVariable[] lignes = new IntegerVariable[n];
IntegerVariable[] colonnes = new IntegerVariable[n];
IntegerVariable[] carres = new IntegerVariable[n];
for(int j = 0; j < n; j++) {
lignes[j] = vars[i][j];
colonnes[j] = vars[j][i];
int sqrtn=(int) Math.sqrt(n);
carres[j] = vars[j%sqrtn + (i % sqrtn) * sqrtn][j/sqrtn + (i / sqrtn) * sqrtn];
}
postAlldiff(m, lignes);
postAlldiff(m, colonnes);
postAlldiff(m, carres);
}
}

// 3. Création d'une contrainte Alldiff
private static void postAlldiff(Model m, IntegerVariable[] vars) {
for(int i = 0; i < vars.length; i++) {
for(int j = i+1; j < vars.length; j++) {
m.addConstraint(Choco.neq(vars[i], vars[j]));
}
}
}

// 4. Réglage des heuristiques de choix de variables et de valeurs
private static void setHeuristic(Solver s) {
s.setVarIntSelector(new RandomIntVarSelector(s));
s.setValIntIterator(new IncreasingDomain());
}

// 5. Affichages des résultats
private static void displayResult(Solver s, IntegerVariable[][] vars) {
int sqrtn=(int) Math.sqrt(n);
for(int i = 0; i < n; i++) {
if (i%sqrtn == 0) {
String str="";
for(int k=0;k<n+(2*(sqrtn+1));k++) str=str.concat("-");
System.out.println(str);
}
for(int j = 0; j < n; j++) {
if (j%sqrtn == 0) System.out.print("||");
int val=s.getVar(vars[i][j]).getVal();
if(val>=10){
char c= (char) ('A'+val-10);
System.out.print(c);
}
else System.out.print(val);
}
System.out.println("||");
}
String str="";
for(int k=0;k<n+(2*(sqrtn+1));k++) str=str.concat("-");
System.out.println(str);
}
}

 

Voici le plan de cette présentation sur la programmation par contraintes

Cette page a été co-réalisée avec Guillaume Rochart, docteur en mathématiques dans mon équipe de recherche au Bouygues e-lab.10/03/2009.