A "quicker" brute force (not the one with 10! complexity) is by doing a recursion starting from the rightmost digit.
The number of levels in the recursion is the same as the longest digits (in the sample case: 5, which is length of MONEY). After we processed 5 levels, we know we got a solution.
The idea follows:
In the first level, we are faced with D + E = Y (or possibly: D + E = 1Y). Brute force the D and E (since we have no idea what they are ...), and for each possible combination of D and E, we automatically knows Y. Make sure that this Y is never assigned a value, OR if it is assigned, it should match the result of D+E. Also make sure that whatever Y is, the digit is never used by another letter. Up to this point, we'd know whether or not there's a "carry".
When the D+E=Y is valid, then we should recurse deeper to the second level N+R=E (propagating the carry information). This one here, we also look for combination of N and R, ... but, whichever combination it is, it should match the E (since we already have the tentative answer for E in the previous level).
The same process goes on until we processed 5 levels (for this example) at which we know we have a valid solution.
You need to take care of little details such as whether leading zeroes is allowed. Also, when the operands have lesser digits, it should be clear that we can just assume we can pad the left digit with constant 0.
Best,
-Lego
On 11/2/06, Rave Hanker <[EMAIL PROTECTED]> wrote:
Hello,
I was asked this in my ICPC qualifiers. Are there any good algorithms to solve Cryptarithmetic problems http://en.wikipedia.org/wiki/Send%2Bmore%3Dmoney like
SEND
+MORE
------------
MONEY
where each character should be assigned a unique digit.
One more constraint i got was to sort the answer by the value of the first operand
--
Well," said Owl, "the customary procedure in such cases is as follows."
"What does Crustimoney Proseedcake mean?" said Pooh. "For I am a Bear of Very Little Brain, and long words Bother me."
"It means the Thing to Do."
"As long as it means that, I don't mind," said Pooh humbly.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
- [algogeeks] Cryptarithmetic problems Rave Hanker
- [algogeeks] Re: Cryptarithmetic problems Lego Haryanto
- [algogeeks] Re: Cryptarithmetic problems Arun prasath N
