The CLP Procedure

The Send More Money problem consists of finding unique digits for the letters D, E, M, N, O, R, S, and Y such that S and M are different from zero (no leading zeros) and the following equation is satisfied:

S E N D

+ M O R E

M O N E Y

You can use the CLP procedure to formulate this problem as a CSP by representing each of the letters in the expression with an integer variable. The domain of each variable is the set of digits 0 through 9. The VARIABLE statement identifies the variables in the problem. The DOM= option defines the default domain for all the variables to be [0,9]. The OUT= option identifies the CSP as a standard type. The LINCON statement defines the linear constraint SEND + MORE = MONEY, and the restrictions that S and M cannot take the value zero. (Alternatively, you can simply specify the domain for S and M as [1,9] in the VARIABLE statement.) Finally, the ALLDIFF statement is specified to enforce the condition that the assignment of digits should be unique. The complete representation, using the CLP procedure, is as follows:

proc clp dom=[0,9]                  /* Define the default domain */
         out=out;                   /* Name the output data set  */
   var S E N D M O R E M O N E Y;   /* Declare the variables     */
   lincon                           /* Linear constraints        */
                                    /* SEND + MORE = MONEY       */
      1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E
      = 
      10000*M + 1000*O + 100*N  + 10*E + Y,
      S<>0,                         /* No leading zeros          */
      M<>0;
   alldiff();      /* All variables have pairwise distinct values*/
run;

The solution data set produced by the CLP procedure is shown in Figure 3.1.

The unique solution to the problem determined by the CLP procedure is as follows:

9 5 6 7

+ 1 0 8 5

1 0 6 5 2