Session 2 :
Modélisation de CSPs

Sommaire de la session 2 :

Objectif de la session et rappels

• X = { X1, X2, ..., Xn} est l'ensemble des variables (les inconnues) du problème ;
• D est la fonction qui associe à chaque variable Xi son domaine D(Xi), c'est-à-dire l'ensemble des valeurs que peut prendre Xi ;
• C = {C1, C2, ..., Ck} est l'ensemble des contraintes. Chaque contrainte Cj est une relation entre certaines variables de X, restreignant les valeurs que peuvent prendre simultanément ces variables.

Exercice 1 : Retour de monnaie

1. Modélisez ce problème sous la forme d'un CSP.
2. Comment pourrait-on exprimer le fait que l'on souhaite que le distributeur rende le moins de pièces possibles ?

Exercice 2 : Coloriage d'une carte

Il s'agit de colorier les 14 régions de la carte ci-dessous, de sorte que deux régions ayant une frontière en commun soient coloriées avec des couleurs différentes. On dispose pour cela des 4 couleurs suivantes : bleu, rouge, jaune et vert.

Exercice 3 : Sel et moutarde

Cinq amis, Barnabé, Casimir, Désiré, Ludovic et Martial, se retrouvent chaque jour au restaurant. Ils ont établi les règles suivantes, qu'ils appliquent chaque fois qu'on leur sert du boeuf :

• Barnabé prend du sel si et seulement si Casimir ne prend que du sel ou que de la moutarde. Il prend de la moutarde si et seulement si, ou bien Désiré ne prend ni sel ni moutarde, ou bien Martial prend les deux.
• Casimir prend du sel si et seulement si, ou bien Barnabé ne prend qu'un des deux condiments, ou bien Martial n'en prend aucun. Il prend de la moutarde si et seulement si Désiré ou Ludovic prennent les deux condiments.
• Désiré prend du sel si et seulement si ou bien Barnabé ne prend aucun condiment, ou bien Casimir prend les deux. Il prend de la moutarde si et seulement si Ludovic ou Martial ne prennent ni sel ni moutarde.
• Ludovic prend du sel si et seulement si Barnabé ou Désiré ne prennent ni sel ni moutarde. Il prend de la moutarde si et seulement si Casimir ou Martial ne prennent ni sel, ni moutarde.
• Martial prend du sel si et seulement si Barnabé ou Ludovic prennent des deux condiments. Il prend de la moutarde si et seulement si Casimir ou Désiré ne prennent qu'un seul condiment.

En fin de compte, que vont-ils mettre sur leurs steaks ?

Exercice 4 : Send more money

On considère l'addition suivante :

   SEND
 + MORE
-------
= MONEY

où chaque lettre représente un chiffre différent (compris entre 0 et 9). On souhaite connaitre la valeur de chaque lettre, sachant que la première lettre de chaque mot représente un chiffre différent de 0.

Modélisez ce problème sous la forme d'un CSP.

Exercice 5 : Le zèbre

Cinq maisons consécutives, de couleurs différentes, sont habitées par des hommes de différentes nationalités. Chacun possède un animal différent, a une boisson préférée différente et fume des cigarettes différentes. De plus, on sait que :

1. Le norvégien habite la première maison,
2. La maison à coté de celle du norvégien est bleue,
3. L'habitant de la troisième maison boit du lait,
4. L'anglais habite la maison rouge,
5. L'habitant de la maison verte boit du café,
6. L'habitant de la maison jaune fume des kools,
7. La maison blanche se trouve juste après la verte,
8. L'espagnol a un chien,
9. L'ukrainien boit du thé,
10. Le japonais fume des cravens,
11. Le fumeur de old golds a un escargot,
12. Le fumeur de gitanes boit du vin,
13. Le voisin du fumeur de Chesterfields a un renard,
14. Le voisin du fumeur de kools a un cheval.

Qui boit de l'eau ? A qui appartient le zèbre ?

Modélisez ce problème sous la forme d'un CSP.