There are some constraints to apply before you start, such as "leading zeros are not allowed", and "only a one is ever carried from the sum of two digits plus a possible carry" so:

  B != 0
  J != 0
  A != 0
  D + S = T or (T + 10)
[download]

Test each partial solution for impossibilities and eliminate it from the list as soon as you can, so the problem does not grow exponentially.

OK I get the testing part. But how should I go about sequentally replacing the letters with numbers?

I would say that you need a simple data stucture to represent the state of the solution so far, say a hash in which $digit{B} = 1 if you chose B to represent 1, and unchosen assignments are undefs.

Suppose you worked from right to left across the addition problem, choosing all of 0 to 9 as the 1's digit of the first number, then each possible unassigned number as the 1's digit of the second number. Then a third digit choice will be automatic (the 1's digit of the sum of the first two choices). Some of these choices will be eliminated by testing that you haven't assigned the same digit to two letters. Keep working right to left, and it should work out.

I would say that the first thing to notice is that you can constrain the numbers from the right hand end, for example if you have defined D to be 3 and S to be 4 you know that T must be 7. In fact we know that (D+S)%10 == T, (ND+ES)%100 == NT and so on. So if we had some code that assigns values in that order and checks constraints at the earliest moment it would solve the problem. To show you what I mean suppose we had some code:

# Note the digits that are not yet assigned
$un0 = "0123456789";
foreach $d (split(//,$un0))
  {
    my $un1 = $un0;
    $un1 =~ s/$d//;
    foreach $s (split(//,$un1))
      {
        my $un2 = $un1;
        $un2 =~ s/$s//;
        foreach $t (split(//,$un2))
          {
            # Now we can check the first constraint
            next unless(($d + $s)%10 == $t);
            my $un3 = $un2;
            $un3 =~ s/$t//;
            foreach $n (split(//,$un3))
              {
                my $un4 = $un3;
                $un4 =~ s/$n//;
                foreach $e (split(//,$un4))
                  {
                    next unless(($n.$d + $e.$s)%100 == $n.$t);
                      .
                      .
                      .
                        # Having assigned everything see if
                        # we have the correct answer
                        if(($j.$a.$m.$e.$s + $b.$o.$n.$d) \
                             == ($a.$g.$e.$n.$t))
                          {
                            print "B=$b A=$a ...
                            goto success;
                          }
                  }
              }
          }
      }
  }
print "Failed\n";
exit(0);
success:
print "Solved\n";

# Warning code not checked in any way!
[download]

Of course the next step is is to convert the problem into a similar piece of text (without the comments and strange indentation). Once we have the text we can evaluate it and get the answer. (I'll leave the fine details to you)

Your solution will work, hawtin (I tried it for the famous "SEND + MORE = MONEY"), except that the operator precedence of $n.$d + $e.$s causes it to be grouped as $n.($d+$e).$s. A join('',...) might be more efficient anyway.

By the way, there's no need for a separate solution process for subtraction. You can just rearrange it into an addition problem.

In essence what one wants to do is to allocate the numbers 0 - 9 over 10 or less letters. To make it easier we will allocate the figures 0 to 9 over exactly 10 letters (we will make up the missing letters and drop them when appropriate).

Of course we may allocate each letter only once, but I think that using a clever algorithm to make sure that each letter is not used more than once will take more time than using real brute force and dropping "wrong" solutions afterwards.

So I would set up a for loop starting with '0123456789' till '9876543210' with a step of 1 and directly allocating the first digit to the (alphabetically) first letter used in your equation and so on. (Perhaps it is easier to start with the last digit in order not to involuntarily shift the whole pattern if it starts with a zero)

Then checking if the equation holds and if it holds checking if no digit has been used more than once.

Thus you delay at lot of "expensive" tests and logic until they are really necessary.

If you optimise the allocation of the digits to the letters and you hard code the testing of the equation, it should be possible.

CountZero

"If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

I really wouldn't do it that way, because now you are dealing in billions of combinations (9,753,086,421 to be exact) which is worse than the 10! count for every possible permutation with no repeated digits.

Suppose the program could check a combination every .001 seconds. Then for an unsolvable problem where it had to try all 9.7 billion combinations, it would take about 112 days.

If you have to use brute-force rather than an AI-style search, at least use a permutation generator like Algorithm::Permute. If you don't need all 10 digits in the problem, then Algorithm::ChooseSubsets would also help.

Well to make my solution a little less "brute" and a bit more smart, only check the combinations where the sum of all digits is equal to 45, which is the sum of the digits one to nine.

This should save some time.

I really wonder if using a permutation engine would be that much faster as it takes time to generate the 10! combinations as well.

In any case my proposed solution woudl work equally well (and probably even better) with the generated list of allowable permutations.

I have a feeling that hardcoding the problem into a PERL script with all constraints will take much longer. At least my solution is more general.

CountZero

"If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law