Mystery sum with placeholder digits I came across this coding problem.


  Back in primary school, maybe you were sometimes asked to solve a
  fill-in-the-blank sum - or "mystery sum" - in which certain digits are
  removed and you had to figure out what they originally were.
  
  Now, it's time for serious business: sums with no digits, where every
  digit is replaced by a letter. Within each seperate sum, a letter
  replaces one digit and it is always the same letter for that one
  digit.
  
  For example, in the sum below: A+BB=ACC The aim is to figure out which
  digits are hidden behind the letters A, B and C so that the sum turns
  out correct. Here, the solution is that A replaces 1, B replaces 9 and
  C replaces 0; resulting in: 1+99=100
  
  Finally, there is the constraint that the length of the given word is
  equal to the length of the hidden number. Thus, in the sum
  CHEVAL+VACHE=OISEAU, CHEVAL is indeed a 6 digit number: the C (more
  precisely the first letter of any word) cannot correspond to a zero.
  
  For each given sum, there is only one possible solution to the
  problem. You are asked to write the result value of the sum to the
  standard output.
  
  INPUT: One line : a sum in the form WORD1+WORD2=RESULT, in which each
  word is a sequence of capital letters.
  
  OUTPUT: The result of the solved sum.
  
  CONSTRAINTS: Each sum has 2 to 20 words, each made up of 1 to 20
  capital letters


I solved it using brute force checking against each permutation of assigned integers to the unique characters. Can anybody suggest a better strategy or algorithm?

public static void mysterySum(String equation) {
String[] breakUp = equation.split("=");
String[] lhs = breakUp[0].split("\\+");
String rhs = breakUp[1];

HashSet&lt;Character&gt; charSet = new HashSet&lt;Character&gt;();
for (char charVal : equation.toCharArray()) {
    if (!(charVal == '+' || charVal == '=')) {
        charSet.add(new Character(charVal));
    }
}

char[] refCharVals = new char[10];

int i = 0;
for (Character charVal : charSet) {
    refCharVals[i++] = charVal;
}
while (i &lt; 10)
    refCharVals[i++] = '=';

String refString = new String(refCharVals);
StringBuilder currRef = new StringBuilder();
checkAllPermutations(refString, currRef, lhs, rhs);

}

private static void checkAllPermutations(String string, StringBuilder outstr,   String[] lhs, String rhs) {

if (resultMatched)
    return;

HashSet&lt;Character&gt; current = new HashSet&lt;&gt;();
if (string.length() == 0) {
    HashMap&lt;Character, Integer&gt; refChars = getRefMap(outstr);

    int sumLhs = 0;
    for (String strNumber : lhs) {
        int number = getnumber(strNumber, refChars);
        sumLhs += number;
    }

    int rhsNumber = getnumber(rhs, refChars);
    if(rhsNumber == sumLhs) {
        resultMatched = true;
    System.out.println(rhsNumber);}
    return;
}

char[] chars = string.toCharArray();

for (int i = 0; i &lt; chars.length; i++) {
    if (current.add(chars[i])) {
        outstr.append(chars[i]);
        checkAllPermutations(string.substring(0, i) + string.substring(i + 1, string.length()), outstr, lhs, rhs);
        outstr.setLength(outstr.length() - 1);
        if(resultMatched) break;
    }

}

}

private static int getnumber(String strNumber,  HashMap&lt;Character, Integer&gt; refChars) {
int number = 0;
for (int i = 0; i &lt; strNumber.length(); i++) {
    number = number * 10 + refChars.get(strNumber.charAt(i));
}
return number;

}

private static HashMap&lt;Character, Integer&gt; getRefMap(StringBuilder outstr) {
HashMap&lt;Character, Integer&gt; refChars = new HashMap&lt;&gt;();

for (int i = 0; i &lt; outstr.length(); i++) {
    if (outstr.charAt(i) != '=')
        refChars.put(outstr.charAt(i), i);
}

return refChars;
}
As for a review of the code I would suggest to avoid acronyms (also recommend, as @200_success did, to better indent the code, in case this is how your code is indented).

As for the solution, I would strongly avoid brute force ones. This is a cryptarithmetic problem and, if you work only on base 10, you have 10! possible assignments, but if you generalize (for any base) then the problem is NP-complete. I would suggest to look for solutions for cryptarithmetic problems (usually they are described on texts/sources on AI).