A more efficient approach to Verbal arithmetic / Alphametics?

alphametic-question, cryptarithmetic-puzzle, java, math, performance

Solution

The big question here is: can you (do you want to) logically deduce certain constraints and apply them to your algorithm or do you want to brute-force it? Assuming the former, some of them are pretty obvious:

- B = 1

- T can't be 0 (because it's first in THE), thus neither S nor E can be 0 either.

- T = E + S % 10

Thus you have S, E, H to loop through giving you at most 9 * 8 * 8 combinations which is 576. Add to that the fact that H + T must be greater or equal to 9 and you'll reduce this even further.

Update Here's a quick and ugly solution. It's based only on 3 constraints listed above.

public class Puzzle {
  public static void main(String[] args) {
    for (int S = 1; S<10; S++) {
      for (int E = 1; E<10; E++) {
        if (S==E) continue; // all letters stand for different digits
        for (int H = 1; H<10; H++) {
          if (H==E || H==S) continue; // all letters stand for different digits
          checkAndPrint(S, E, H);
        }
      } // for
    } // for
  } // main

  private static boolean checkAndPrint(int S, int E, int H) {
    int T = (S + E) % 10;
    int S1 = (E + H) + (S + E) / 10; // calculates value for 'S' in 'BEST' (possibly + 10)
    if (S1 % 10 != S) return false;
    int E1 = H + T + S1 / 10; // calculates value for 'E' in 'BEST' (possibly + 10)
    if (E1 % 10 != E) return false;
    System.out.println(H + "" + E + "" + S + " + " + T + "" + H + "" + E + " = 1" + E + "" + S + "" + T);
    return true;
  }
}

Problem

Perhaps most of you know the Send + More = Money. Well, I'm currently learning java and one of the exercises is I have to solve HES + THE = BEST. Now, so far I can/should use if-for-while-do loops, nothing else. Although I'm sure there are different methods to solve it, that's not the point of the exercise I'm going through. I have to be able to use if-for-while-do loops the most efficient way. My problem? I can't seem to think of an efficient way to solve it! I've come up with this, which solves the puzzle, but is perhaps the worst efficient way to do so: ``` public class Verbalarithmetics { public static void main (String args[]) { // Countint Variables int index_h = 0; int index_e = 0; int index_s = 0; int index_t = 0; int index_b = 0; // Start with h = 1 and increase until the else-if statement is true for(int h = 1; h <= 9; h++) { // h = 1, because first Symbol can't be zero index_h++; // Increase e so long until e equals h for(int e = 0; e <= 9; e++) { index_e++; if (e == h) { continue; } // Increase s so long until s equals h or e for(int s = 0; s <= 9; s++) { index_s++; if (s == h || s == e) { continue; }//end if // Increase t so long until t equals h or e or s. for(int t = 1; t <= 9; t++) { // t = 1, because 1st Symbol cant be zero index_t++; if(t == h || t == e || t == s) { continue; }// end if // Increase b so long until b equals h, e, s or t. for(int b = 1; b <= 9; b++) { // b = 1, weil das 1. Symbol nicht für eine 0 stehen darf index_b++; if (b == h || b == e || b == s || b == t) { continue; }// end if // x = 100*h + 10*e + s // y = 100*t + 10*h + e // z = 1000*b + 100*e + 10*s + t // Check if x+y=z, if true -> Print out Solution, else continue with the upper most loop else if (100*h + 10*e + s + 100*t + 10*h + e == 1000*b + 100*e +10*s + t) { System.out.println("HES + THE = BEST => " + h + e + s + " + " + t + h + e + " = " + b + e + s + t); System.out.println("With H=" + h + ", E=" + e + ", S=" + s + ", T=" + t + ", und B=" + b + "."); System.out.println("It took " + index_h + " Loop-Cycles to find 'h' !"); System.out.println("It took " + index_e + " Loop-Cycles to find 'e' !"); System.out.println("It took " + index_s + " Loop-Cycles to find 's' !"); System.out.println("It took " + index_t + " Loop-Cycles to find 't' !"); System.out.println("It took " + index_b + " Loop-Cycles to find 'b' !"); System.out.println("This is a total of " + (index_h + index_e + index_s + index_t + index_b) + " Loop-Cycles"); }// end else if }//end for }//end for }//end for }//end for }//end for } } ``` It takes about 15000 odd loop-cycles in total to solve this puzzle. That's a lot in my opinion. Any pointers, please?

Original source