TD Exercice 3
![](_img/sudoku_suduko_programmation_par_contraintes.jpg)
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) {
![](_img/spacer.png)
long
time = System.currentTimeMillis();
![](_img/spacer.png)
System.out.println("Sudoku");
![](_img/spacer.png)
assert
Math.rint(Math.sqrt(n))==Math.sqrt(n);
![](_img/spacer.png)
Model
m = new CPModel();
![](_img/spacer.png)
IntegerVariable[][]
vars = createVariables(m);
![](_img/spacer.png)
postConstraints(m,
vars);
![](_img/spacer.png)
Solver
s = new CPSolver();
![](_img/spacer.png)
s.read(m);
![](_img/spacer.png)
setHeuristic(s);
![](_img/spacer.png)
s.solve();
![](_img/spacer.png)
displayResult(s,
vars);
![](_img/spacer.png)
System.out.println("Time
ellapsed: " + (System.currentTimeMillis() - time) +
"ms.");
}
//
1. Création des variables
private
static IntegerVariable[][] createVariables(Model m) {
![](_img/spacer.png)
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) {
![](_img/spacer.png)
for(int
i = 0; i < n; i++) {
![](_img/spacer.png)
![](_img/spacer.png)
IntegerVariable[]
lignes = new IntegerVariable[n];
![](_img/spacer.png)
![](_img/spacer.png)
IntegerVariable[]
colonnes = new IntegerVariable[n];
![](_img/spacer.png)
![](_img/spacer.png)
IntegerVariable[]
carres = new IntegerVariable[n];
![](_img/spacer.png)
![](_img/spacer.png)
for(int
j = 0; j < n; j++) {
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
lignes[j]
= vars[i][j];
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
colonnes[j]
= vars[j][i];
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
int
sqrtn=(int) Math.sqrt(n);
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
carres[j]
= vars[j%sqrtn + (i % sqrtn) * sqrtn][j/sqrtn + (i / sqrtn)
* sqrtn];
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
![](_img/spacer.png)
postAlldiff(m,
lignes);
![](_img/spacer.png)
![](_img/spacer.png)
postAlldiff(m,
colonnes);
![](_img/spacer.png)
![](_img/spacer.png)
postAlldiff(m,
carres);
![](_img/spacer.png)
}
}
//
3. Création d'une contrainte Alldiff
private
static void postAlldiff(Model m, IntegerVariable[] vars)
{
![](_img/spacer.png)
for(int
i = 0; i < vars.length; i++) {
![](_img/spacer.png)
![](_img/spacer.png)
for(int
j = i+1; j < vars.length; j++) {
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
m.addConstraint(Choco.neq(vars[i],
vars[j]));
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
}
}
//
4. Réglage des heuristiques de choix de variables
et de valeurs
private
static void setHeuristic(Solver s) {
![](_img/spacer.png)
s.setVarIntSelector(new
RandomIntVarSelector(s));
![](_img/spacer.png)
s.setValIntIterator(new
IncreasingDomain());
}
//
5. Affichages des résultats
private
static void displayResult(Solver s, IntegerVariable[][]
vars) {
![](_img/spacer.png)
int
sqrtn=(int) Math.sqrt(n);
![](_img/spacer.png)
for(int
i = 0; i < n; i++) {
![](_img/spacer.png)
![](_img/spacer.png)
if
(i%sqrtn == 0) {
![](_img/spacer.png)
![](_img/spacer.png)
String
str="";
![](_img/spacer.png)
![](_img/spacer.png)
for(int
k=0;k<n+(2*(sqrtn+1));k++) str=str.concat("-");
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
System.out.println(str);
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
![](_img/spacer.png)
for(int
j = 0; j < n; j++) {
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
if
(j%sqrtn == 0) System.out.print("||");
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
int
val=s.getVar(vars[i][j]).getVal();
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
if(val>=10){
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
char
c= (char) ('A'+val-10);
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
System.out.print(c);
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
else
System.out.print(val);
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
![](_img/spacer.png)
System.out.println("||");
![](_img/spacer.png)
}
![](_img/spacer.png)
String
str="";
![](_img/spacer.png)
for(int
k=0;k<n+(2*(sqrtn+1));k++) str=str.concat("-");
![](_img/spacer.png)
System.out.println(str);
}
}
Voici
le plan de cette présentation sur la programmation par contraintes
- Les
notions de base
:
- Quelques
notions avancées :
- Quelques
exemples pour utiliser la P.P.C. :
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.
![](_img/choco_solver.png)