in reply to Words that equal numbers

Watch out, there are 10! = 3,628,800 combinations possible for a complete brute-force search.

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]
I once implemented a solution for a peg-jumping game in perl by keeping a stack of game states, and doing all possible next jumps to make a stack of all possible next states, and so on. In your case a "move" would be the choice of another digit-to-letter assignment.

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

Replies are listed 'Best First'.
Re: Re: Words that equal numbers
by Anonymous Monk on Jan 18, 2003 at 00:45 UTC
    OK I get the testing part. But how should I go about sequentally replacing the letters with numbers?
[reply]
      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.

[reply]
[d/l]

In Section Seekers of Perl Wisdom