// SendMoreMoney.java
// Krzysztof Kuchcinski and Radoslaw Szymanek, 2008
// Slightly modified by Andrew Davison, ad@coe.psu.ac.th, Dec. 2022

/*
   Cryptogram:    SEND
               +  MORE
                 -----
                 MONEY

   Solution:      9567
               +  1085
                 -----
                 10652

   More Info: https://en.wikipedia.org/wiki/Verbal_arithmetic

  The code utilizes a weighted sum LinearInt constraint:
      w1 * x1 + w2 * x2 + ... + wn * xn == sum

  See DonaldGeraldRobert.java for a more fancy approach.

  Usage:
     > compile SendMoreMoney.java
     > run SendMoreMoney

     Solve the cryptogram: SEND+MORE=MONEY
     S = 9;  E = 5;  N = 6;  D = 7;  M = 1;
     O = 0;  R = 8;  Y = 2;

*/


import org.jacop.constraints.*;
import org.jacop.core.*;
import org.jacop.search.*;
  // uses Jacop: https://jacop.cs.lth.se/

import java.util.*;


public class SendMoreMoney
{

  public static void main(String args[])
  {
    System.out.println("Solve the cryptogram: SEND+MORE=MONEY");

    Store store = new Store();

    // create constraint variables
    // Note: the first letter of each word cannot be 0
    IntVar s = new IntVar(store, "S", 1, 9);  // not 0
    IntVar e = new IntVar(store, "E", 0, 9);
    IntVar n = new IntVar(store, "N", 0, 9);
    IntVar d = new IntVar(store, "D", 0, 9);
    IntVar m = new IntVar(store, "M", 1, 9);  // not 0
    IntVar o = new IntVar(store, "O", 0, 9);
    IntVar r = new IntVar(store, "R", 0, 9);
    IntVar y = new IntVar(store, "Y", 0, 9);

    IntVar digits[] = {s, e, n, d, m, o, r, y};
    store.impose(new Alldifferent(digits));

    IntVar[] allVars = {  s,   e,   n,   d,
                          m,   o,   r,   e,
                     m,   o,   n,   e,   y };

    int[] weights = {   1000,  100,  10,  1,
                       1000,  100,  10,  1,
              -10000, -1000, -100, -10, -1 };
          // negative so that the sum will be 0

    store.impose(new LinearInt(allVars, weights, "==", 0));

    SelectChoicePoint<IntVar> select = 
       new SimpleSelect<>(digits,  null, new IndomainMin<>());

    Search<IntVar> search = new DepthFirstSearch<>();
    search.setPrintInfo(false);
    search.labeling(store, select);
    JacopUtils.printSolns(search);
  } /* main */

}  // end of SendMoreMoney class