TD Exercice 2

Soit le problème suivant :

Trouver la valeur associée à chaque lettre, de telle manière que :

• La somme soit vérifiée.
• et soient différents de 0.
• Chaque lettre ait une valeur différente.

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

 

Solution

On peut définir un modèle avec des bornes sur chaque lettre :

• 1 ≤ S ≤ 9
  
• 0 ≤ E ≤ 9
• ...
  

Toutes les lettres sont différentes : S &neq; E &neq; N ...

et une équation principale permettant la vérification de la somme globale :

9000 * M + 900 * O + 90 * N - 91 * E + Y – 10 * R – 1000 * S – D = 0

Ici il n'y a pas vraiment d’objectif, il est plutôt artificiel.

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

import choco.kernel.model.Model;
import choco.kernel.model.variables.integer.IntegerVariable;
import choco.kernel.solver.Solver;
import choco.cp.model.CPModel;
import choco.cp.solver.CPSolver;
import choco.Choco;

public class SendMoreMoney {

public static void main(String[] args) {

// Création du modèle

Model m = new CPModel();

// Création des variables avec leur domaine

IntegerVariable S = Choco.makeIntVar("S", 0, 9);
IntegerVariable E = Choco.makeIntVar("E", 0, 9);
IntegerVariable N = Choco.makeIntVar("N", 0, 9);
IntegerVariable D = Choco.makeIntVar("D", 0, 9);
IntegerVariable M = Choco.makeIntVar("M", 0, 9);
IntegerVariable O = Choco.makeIntVar("O", 0, 9);
IntegerVariable R = Choco.makeIntVar("R", 0, 9);
IntegerVariable Y = Choco.makeIntVar("Y", 0, 9);
IntegerVariable[] letters = {S, E, N, D, M, O, R, Y};

// Ajout des contraintes d'unicité de chaque lettre

for (int i = 1; i <= 7; i++) {
for (int j = 0; j < i; j++) {
m.addConstraint( Choco.neq(letters[i], letters[j]) );
}
}

// Ajout de la contrainte de vérification de la somme

m.addConstraint( Choco.eq( Choco.scalar( letters, new int[]{-1000, -91, 90, -1, 9000, 900, -10, 1}), 0));

// Création du solveur

Solver s = new CPSolver();

// Le solveur lit le modèle

s.read(m);

// On cherche l'énumération de toutes les solutions de ce problème

s.solveAll();

// On affiche les résultats

System.out.println("nb solutions = " + s.getNbSolutions());

System.out.println(s.pretty());

}

}

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

• Les notions de base :
  • Les C.S.P.
  • La Recherche / Propagation
    
    
• Quelques notions avancées :
• Les Contraintes Globales
• Le Continu
• Les Explications
  
  
• Quelques exemples pour utiliser la P.P.C. :
  • Les N-Reines
  • Send More Money
  • Le Sudoku
  • Le Kakuro
  • Picross

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.