Quelques indices pour démarrer l'exercice 4

Pour modéliser ce problème sous la forme d'un CSP, il s'agit d'identifier les variables (les inconnues du problème), les domaines de valeur de ces variables, et les contraintes existant entre ces variables.

Ici, les inconnues du problème sont les valeurs des lettres S, E, N, D, M, O, R et Y. On a donc 8 variables, chacune pouvant prendre une valeur comprise entre 0 et 9, sauf S et M qui ne peuvent être égales à 0 puisqu'elles sont en début de mot.

Il s'agit ensuite de définir les contraintes. Une première possibilité consiste à définir une seule contrainte "traduisant" l'équation SEND + MORE = MONEY. Pour cela, il s'agit de reconstituer le nombre associé à chaque mot à partir des valeurs des lettres le composant (par exemple, le nombre associé au mot SEND est égal à D + 10N + 100E + 1000S).

Une autre possibilité, pour définir les contraintes, consiste à poser les contraintes "verticalement", comme quand on fait une addition à la main :

Avec une telle modélisation, il faut rajouter 3 variables R1, R2 et R3 correspondant aux retenues successives, et pouvant prendre pour valeur 0 ou 1 (car la somme de deux chiffres compris entre 0 et 9 est toujours inférieure ou égale à 18).

Il faut par ailleurs ajouter une contrainte pour exprimer le fait que toutes les lettres doivent prendre des valeurs différentes...