Cryptarithmetic 2

JCW2
JCW2 used Ask the Experts™
on
I'm a student and don't expect a full answer. This question is continued from http://www.experts-exchange.com/Programming/Algorithms/Q_26559345.html?useRichText=true&checkFlag=1#notices. I'm trying to understand how to properly implement the requested algorithm.

6.5) Solve the cryptarithmetic problem in Figure 6.2 by hand, using the strategy of backtracking with forward checking and the MRV and least-constraining-value heuristics.
Diagram.PNG
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
The square box at the top of the figure is the All Diff Constraint.
They give you that.

You have to figure out the other constraints and what they imply.


Look at the leftmost box under  "F"  for example:

   The constraint here is   C3 = F.
   Since leading zeros are not allowed,   F and C3 must be greater than zero.


Next look at the next box under  "T":

     The constraint here is   T + T + C2 = 10*C1 + O
     You don't know anything about C1 or O yet, but you can tell that  C3=F=1, and T={5,6,7,8,9}

And so on...

At some point you have to resort to trial and error, looking for inconsistencies.

Author

Commented:
Thanks. How do I deal with forward checking and the MRV and least-constraining-value heuristics?
>> forward checking and the MRV and least-constraining-value heuristics

I don't know what that means, except that heuristics is trial and error.
If I had to solve the problem, I would start picking values for C2 and T:

       C2=0    T=5  ==>  Oh=0    but Oh+Oh=R=0  and R can't also be zero.

               T=6  ==>  Oh=2    ==> Oh+Oh=R=4  and C1=0  
                                 ==> W can only be 3 or 4, making U be 6 or 8.  But 6 is taken.


So   642   is one solution.  I expect there are others.
    +642
    -----
    1284

Open in new window

Should you be charging more for IT Services?

Do you wonder if your IT business is truly profitable or if you should raise your prices? Learn how to calculate your overhead burden using our free interactive tool and use it to determine the right price for your IT services. Start calculating Now!

Author

Commented:
It looks like "the aim is to find a substitution of digits for letters such that the resulting sum is correct, with the added restriction that no leading zeros are allowed." How do I do that?
There is no equation to solve, but there are logical techniques that can help.

TWO could be anything between 000 and 999.

No leading zeroes eliminates  001 to 099.

All_Different   eliminates another bunch of possibilites:  11, 22, 33,  111, 121, ...

The carry into the fourth digit restricts the range further:  TWO must be between 523 and 987.

This is an exercise in logical thinking and organization.

If you follow the procedure I started in my last post to completion, you will find all the possible solutions.
      C2=0         ==>  W ={0,2,3,4)
              T=5  ==>  No Solutions
              T=6  ==>  One Solution ==>  TWO=642
              T=7
              T=8
              T=9


      C2=1         ==>  W ={5,6,7,8,9)
              T=5  
              T=6 
              T=7
              T=8 ==> Oh=7 ==> R=4   TW0 = 867

              T=9 ==> Oh=9 ==> No Solutions

Open in new window

Author

Commented:
Thank you for your help.

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial