modelisation send more money

Corrigé de l'exercice 4

Première modélisation

Variables : on associe une variable à chaque lettre
X = {S,E,N,D,M,O,R,Y}
Domaines : les variables correspondant au premier chiffre d'un mot (S et M) doivent prendre une valeur différente de 0 ; les autres peuvent prendre n'importe quelle valeur entre 0 et 9.
D(S) = D(M) = {1,2,3,4,5,6,7,8,9}
D(E) = D(N) = D(D) = D(O) = D(R) = D(Y) = {0,1,2,3,4,5,6,7,8,9}
Contraintes :
- Une première contrainte exprime le fait que SEND+MORE=MONEY :
  C1 = 1000*S + 100*E + 10*N + D
  +1000*M + 100*O + 10*R + E
  = 10000*M + 1000*O + 100*N + 10*E + Y
- Une seconde contrainte exprime le fait que toutes les variables doivent prendre des valeurs différentes. On peut utiliser pour cela la contrainte globale "toutes-différentes" :
  C2 = toutes-différentes({S,E,N,D,M,O,R,Y})

Deuxième modélisation

La première modélisation exprime en une seule contrainte (C1) le fait que SEND+MORE=MONEY. Une deuxième modélisation consiste à poser les contraintes "verticalement", comme quand on fait une addition à la main. Pour cela, on rajoute 3 variables R1, R2 et R3 correspondant aux retenues successives. On obtient le CSP suivant :

Variables :
X = {S,E,N,D,M,O,R,Y,R1,R2,R3}
Domaines :
D(S) = D(M) = {1,2,3,4,5,6,7,8,9}
D(E) = D(N) = D(D) = D(O) = D(R) = D(Y) = {0,1,2,3,4,5,6,7,8,9}
D(R1) = D(R2) = D(R3) = {0,1}
Contraintes :
- Un premier ensemble de contraintes exprime le fait que SEND+MORE=MONEY :
  C1 = { D + E = Y + 10*R1,
  R1 + N + R = E + 10*R2,
  R2 + E + O = N + 10*R3,
  R3 + S + M = O + 10*M }
- Une dernière contrainte exprime le fait que toutes les variables doivent prendre des valeurs différentes. On peut utiliser pour cela la contrainte globale "toutes-différentes" :
  C2 = toutes-différentes({S,E,N,D,M,O,R,Y})