TD Exercice 5
![](_img/picross_programmation_par_contraintes.png)
Ce
problème est notamment utilisé en Tomographie.
Modéliser le problème et trouver la solution
au problème en utilisant le solveur Choco 2.0.
Solution
Modèle 1
- On
utilise les contraintes génériques :
- Une
variable (0/1) par case
-
Une contrainte par ligne / colonne :
- Vérifiant
lexistence des blocs (séparation
blocs vides)
- Vérifiant
leur longueur
Voici
le code java en Choco
2.0 de ce premier modèle :
import
choco.kernel.model.Model;
import choco.kernel.model.variables.integer.IntegerVariable;
import choco.kernel.solver.Solver;
import choco.kernel.solver.constraints.integer.extension.TuplesTest;
import choco.cp.model.CPModel;
import choco.cp.solver.CPSolver;
import choco.Choco;
public
class TomoAC {
static
int nbCol = 10;
static
int nbLig = 10;
static
int[][] colBlocs = new int[][]{
![](_img/spacer.png)
new
int[]{2, 3},
![](_img/spacer.png)
new
int[]{1, 2},
![](_img/spacer.png)
new
int[]{1, 1, 1, 1},
![](_img/spacer.png)
new
int[]{1, 2},
![](_img/spacer.png)
new
int[]{1, 1, 1, 1},
![](_img/spacer.png)
new
int[]{1, 2},
![](_img/spacer.png)
new
int[]{2, 3},
![](_img/spacer.png)
new
int[]{3, 4},
![](_img/spacer.png)
new
int[]{8},
![](_img/spacer.png)
new
int[]{9},
};
static
int[][] ligBlocs = new int[][]{
![](_img/spacer.png)
new
int[]{3, 6},
![](_img/spacer.png)
new
int[]{1, 4},
![](_img/spacer.png)
new
int[]{1, 1, 3},
![](_img/spacer.png)
new
int[]{2},
![](_img/spacer.png)
new
int[]{3, 3},
![](_img/spacer.png)
new
int[]{1, 4},
![](_img/spacer.png)
new
int[]{2, 5},
![](_img/spacer.png)
new
int[]{2, 5},
![](_img/spacer.png)
new
int[]{1, 1},
![](_img/spacer.png)
new
int[]{3},
};
public
static void main(String[] args)
{
![](_img/spacer.png)
Model
m = new CPModel();
![](_img/spacer.png)
IntegerVariable[][]
vars =
![](_img/spacer.png)
![](_img/spacer.png)
Choco.makeIntVarArray("case",
nbCol, nbLig, 0, 1);
![](_img/spacer.png)
for
(int i = 0; i < ligBlocs.length; i++)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
IntegerVariable[]
ligne = new IntegerVariable[nbCol];
![](_img/spacer.png)
![](_img/spacer.png)
for
(int j = 0; j < ligne.length; j++)
![](_img/spacer.png)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
ligne[j]
= vars[j][i];
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
![](_img/spacer.png)
int[]
blocs = ligBlocs[i];
![](_img/spacer.png)
![](_img/spacer.png)
postConstraint(m,
ligne, blocs);
![](_img/spacer.png)
}
![](_img/spacer.png)
for
(int i = 0; i < colBlocs.length; i++)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
IntegerVariable[]
colonne = new IntegerVariable[nbLig];
![](_img/spacer.png)
![](_img/spacer.png)
for
(int j = 0; j < colonne.length; j++)
![](_img/spacer.png)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
colonne[j]
= vars[i][j];
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
![](_img/spacer.png)
int[]
blocs = colBlocs[i];
![](_img/spacer.png)
![](_img/spacer.png)
postConstraint(m,
colonne, blocs);
![](_img/spacer.png)
}
![](_img/spacer.png)
Solver
s = new CPSolver();
![](_img/spacer.png)
s.read(m);
![](_img/spacer.png)
s.solve();
![](_img/spacer.png)
s.printRuntimeSatistics();
![](_img/spacer.png)
for
(int i = 0; i < nbLig; i++)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
for
(int j = 0; j < nbCol; j++)
![](_img/spacer.png)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
IntegerVariable
v = vars[j][i];
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
System.out.print(s.getVar(v).getVal()
== 0 ? " " : "#");
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
![](_img/spacer.png)
System.out.println();
![](_img/spacer.png)
}
}
private
static void postConstraint(Model m,
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
IntegerVariable[] ligne, final int[] blocs)
{
![](_img/spacer.png)
m.addConstraint(
![](_img/spacer.png)
![](_img/spacer.png)
Choco.relationTupleAC(ligne,
new TuplesTest()
![](_img/spacer.png)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
public
boolean checkTuple(int[] tuple)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
int
currentBloc = 0;
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
int
i = 0;
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
while
(i < tuple.length)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
while
(i < tuple.length && tuple[i] == 0) i++;
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
if
(currentBloc == blocs.length && i == tuple.length)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
return
true;
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
if
(currentBloc >= blocs.length) return false;
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
int
l = 0;
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
while
(i < tuple.length && tuple[i] == 1)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
i++;
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
l++;
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
if
(l != blocs[currentBloc]) return false;
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
currentBloc++;
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
if
(currentBloc == blocs.length && i == tuple.length)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
return
true;
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
return
false;
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
![](_img/spacer.png)
})
![](_img/spacer.png)
);
}
}
Solution
Modèle 2
- Utiliser
la contrainte Regular :
- Il
sagit dexpression régulière
- Par
exemple pour 1,4,3
0* 1 0+ 1111 0+ 111 0*
- Rappel
: dans une Regexp
+ = apparait au moins une fois
* = apparait un nombre quelconque de fois.
Voici
le code java en Choco
2.0 de ce second modèle :
import
choco.cp.model.CPModel;
import choco.cp.solver.constraints.global.regular.DFA;
import choco.cp.solver.CPSolver;
import choco.kernel.model.Model;
import choco.kernel.model.variables.integer.IntegerVariable;
import choco.kernel.solver.Solver;
import choco.Choco;
public
class TomoReg
{
static
int nbCol = 10;
static
int nbLig = 10;
static
int[][] colBlocs = new int[][]{
![](_img/spacer.png)
new
int[]{2, 3},
![](_img/spacer.png)
new
int[]{1, 2},
![](_img/spacer.png)
new
int[]{1, 1, 1, 1},
![](_img/spacer.png)
new
int[]{1, 2},
![](_img/spacer.png)
new
int[]{1, 1, 1, 1},
![](_img/spacer.png)
new
int[]{1, 2},
![](_img/spacer.png)
new
int[]{2, 3},
![](_img/spacer.png)
new
int[]{3, 4},
![](_img/spacer.png)
new
int[]{8},
![](_img/spacer.png)
new
int[]{9},
};
static
int[][] ligBlocs = new int[][]{
![](_img/spacer.png)
new
int[]{3, 6},
![](_img/spacer.png)
new
int[]{1, 4},
![](_img/spacer.png)
new
int[]{1, 1, 3},
![](_img/spacer.png)
new
int[]{2},
![](_img/spacer.png)
new
int[]{3, 3},
![](_img/spacer.png)
new
int[]{1, 4},
![](_img/spacer.png)
new
int[]{2, 5},
![](_img/spacer.png)
new
int[]{2, 5},
![](_img/spacer.png)
new
int[]{1, 1},
![](_img/spacer.png)
new
int[]{3},
};
public
static void main(String[] args)
{
![](_img/spacer.png)
Model
m = new CPModel();
![](_img/spacer.png)
IntegerVariable[][]
vars =
![](_img/spacer.png)
![](_img/spacer.png)
Choco.makeIntVarArray("case",
nbCol, nbLig, 0, 1);
![](_img/spacer.png)
for
(int i = 0; i < ligBlocs.length; i++)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
int[]
blocs = ligBlocs[i];
![](_img/spacer.png)
![](_img/spacer.png)
StringBuilder
sb = new StringBuilder();
![](_img/spacer.png)
![](_img/spacer.png)
sb.append("0*");
![](_img/spacer.png)
![](_img/spacer.png)
for
(int j = 0; j < blocs.length; j++)
![](_img/spacer.png)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
if
(j > 0) sb.append("0+");
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
int
bloc = blocs[j];
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
for
(int n = 0; n < bloc; n++) sb.append("1");
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
![](_img/spacer.png)
sb.append("0*");
![](_img/spacer.png)
![](_img/spacer.png)
IntegerVariable[]
ligne = new IntegerVariable[nbCol];
![](_img/spacer.png)
![](_img/spacer.png)
for
(int j = 0; j < ligne.length; j++)
![](_img/spacer.png)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
ligne[j]
= vars[j][i];
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
![](_img/spacer.png)
m.addConstraint(
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
Choco.regular(new
DFA(sb.toString(), nbCol), ligne));
![](_img/spacer.png)
}
![](_img/spacer.png)
for
(int i = 0; i < colBlocs.length; i++)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
int[]
blocs = colBlocs[i];
![](_img/spacer.png)
![](_img/spacer.png)
StringBuilder
sb = new StringBuilder();
![](_img/spacer.png)
![](_img/spacer.png)
sb.append("0*");
![](_img/spacer.png)
![](_img/spacer.png)
for
(int j = 0; j < blocs.length; j++)
![](_img/spacer.png)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
if
(j > 0) sb.append("0+");
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
int
bloc = blocs[j];
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
for
(int n = 0; n < bloc; n++) sb.append("1");
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
![](_img/spacer.png)
sb.append("0*");
![](_img/spacer.png)
![](_img/spacer.png)
IntegerVariable[]
colonne = new IntegerVariable[nbLig];
![](_img/spacer.png)
![](_img/spacer.png)
for
(int j = 0; j < colonne.length; j++)
![](_img/spacer.png)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
colonne[j]
= vars[i][j];
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
![](_img/spacer.png)
m.addConstraint(
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
Choco.regular(new
DFA(sb.toString(), nbLig), colonne));
![](_img/spacer.png)
}
![](_img/spacer.png)
Solver
s = new CPSolver();
![](_img/spacer.png)
s.read(m);
![](_img/spacer.png)
s.solve();
![](_img/spacer.png)
s.printRuntimeSatistics();
![](_img/spacer.png)
for
(int i = 0; i < nbLig; i++)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
for
(int j = 0; j < nbCol; j++)
![](_img/spacer.png)
![](_img/spacer.png)
{
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
IntegerVariable
v = vars[j][i];
![](_img/spacer.png)
![](_img/spacer.png)
![](_img/spacer.png)
System.out.print(s.getVar(v).getVal()
== 0 ? " " : "#");
![](_img/spacer.png)
![](_img/spacer.png)
}
![](_img/spacer.png)
![](_img/spacer.png)
System.out.println();
![](_img/spacer.png)
}
}
}
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)