PPC > EXEMPLES > Picross


TD Exercice 5


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 l’existence 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[][]{
new int[]{2, 3},
new int[]{1, 2},
new int[]{1, 1, 1, 1},
new int[]{1, 2},
new int[]{1, 1, 1, 1},
new int[]{1, 2},
new int[]{2, 3},
new int[]{3, 4},
new int[]{8},
new int[]{9},
};

static int[][] ligBlocs = new int[][]{
new int[]{3, 6},
new int[]{1, 4},
new int[]{1, 1, 3},
new int[]{2},
new int[]{3, 3},
new int[]{1, 4},
new int[]{2, 5},
new int[]{2, 5},
new int[]{1, 1},
new int[]{3},
};

public static void main(String[] args)
{
Model m = new CPModel();
IntegerVariable[][] vars =
Choco.makeIntVarArray("case", nbCol, nbLig, 0, 1);

for (int i = 0; i < ligBlocs.length; i++)
{
IntegerVariable[] ligne = new IntegerVariable[nbCol];
for (int j = 0; j < ligne.length; j++)
{
ligne[j] = vars[j][i];
}
int[] blocs = ligBlocs[i];
postConstraint(m, ligne, blocs);
}

for (int i = 0; i < colBlocs.length; i++)
{
IntegerVariable[] colonne = new IntegerVariable[nbLig];
for (int j = 0; j < colonne.length; j++)
{
colonne[j] = vars[i][j];
}
int[] blocs = colBlocs[i];
postConstraint(m, colonne, blocs);
}

Solver s = new CPSolver();
s.read(m);

s.solve();
s.printRuntimeSatistics();
for (int i = 0; i < nbLig; i++)
{
for (int j = 0; j < nbCol; j++)
{
IntegerVariable v = vars[j][i];
System.out.print(s.getVar(v).getVal() == 0 ? " " : "#");
}
System.out.println();
}
}

private static void postConstraint(Model m,
IntegerVariable[] ligne, final int[] blocs)
{
m.addConstraint(
Choco.relationTupleAC(ligne, new TuplesTest()
{
public boolean checkTuple(int[] tuple)
{
int currentBloc = 0;
int i = 0;
while (i < tuple.length)
{
while (i < tuple.length && tuple[i] == 0) i++;
if (currentBloc == blocs.length && i == tuple.length)
return true;
if (currentBloc >= blocs.length) return false;
int l = 0;
while (i < tuple.length && tuple[i] == 1)
{
i++;
l++;
}
if (l != blocs[currentBloc]) return false;
currentBloc++;
if (currentBloc == blocs.length && i == tuple.length)
return true;
}
return false;
}
})
);
}
}

Solution Modèle 2

  • Utiliser la contrainte Regular :
    • Il s’agit d’expression 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[][]{
new int[]{2, 3},
new int[]{1, 2},
new int[]{1, 1, 1, 1},
new int[]{1, 2},
new int[]{1, 1, 1, 1},
new int[]{1, 2},
new int[]{2, 3},
new int[]{3, 4},
new int[]{8},
new int[]{9},
};

static int[][] ligBlocs = new int[][]{
new int[]{3, 6},
new int[]{1, 4},
new int[]{1, 1, 3},
new int[]{2},
new int[]{3, 3},
new int[]{1, 4},
new int[]{2, 5},
new int[]{2, 5},
new int[]{1, 1},
new int[]{3},
};

public static void main(String[] args)
{
Model m = new CPModel();
IntegerVariable[][] vars =
Choco.makeIntVarArray("case", nbCol, nbLig, 0, 1);

for (int i = 0; i < ligBlocs.length; i++)
{
int[] blocs = ligBlocs[i];
StringBuilder sb = new StringBuilder();
sb.append("0*");
for (int j = 0; j < blocs.length; j++)
{
if (j > 0) sb.append("0+");
int bloc = blocs[j];
for (int n = 0; n < bloc; n++) sb.append("1");
}
sb.append("0*");

IntegerVariable[] ligne = new IntegerVariable[nbCol];
for (int j = 0; j < ligne.length; j++)
{
ligne[j] = vars[j][i];
}

m.addConstraint(
Choco.regular(new DFA(sb.toString(), nbCol), ligne));
}

for (int i = 0; i < colBlocs.length; i++)
{
int[] blocs = colBlocs[i];
StringBuilder sb = new StringBuilder();
sb.append("0*");
for (int j = 0; j < blocs.length; j++)
{
if (j > 0) sb.append("0+");
int bloc = blocs[j];
for (int n = 0; n < bloc; n++) sb.append("1");
}
sb.append("0*");

IntegerVariable[] colonne = new IntegerVariable[nbLig];
for (int j = 0; j < colonne.length; j++)
{
colonne[j] = vars[i][j];
}

m.addConstraint(
Choco.regular(new DFA(sb.toString(), nbLig), colonne));
}

Solver s = new CPSolver();
s.read(m);

s.solve();
s.printRuntimeSatistics();
for (int i = 0; i < nbLig; i++)
{
for (int j = 0; j < nbCol; j++)
{
IntegerVariable v = vars[j][i];
System.out.print(s.getVar(v).getVal() == 0 ? " " : "#");
}
System.out.println();
}
}
}

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.