Thursday, 4 July 2013

How To Solve Cryptarithmetic Puzzles

In Case You Haven't Checked These Out:

Elitmus pH Test Pattern & Syllabus

Tips For Elitmus Test


Cryptarithmetic, also known as alphametics, cryptarithmetic, Verbal Arithmetic, cryptarithm or word addition, is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters. The goal is to identify the value of each letter. The name can be extended to puzzles that use non-alphabetic symbols instead of letters.

The equation is typically a basic operation of arithmetic, such as addition, multiplication, or division. The classic example, published in the July 1924 issue of Strand Magazine by Henry Dudeney, is:
    S E N D
+ M O R E
-------------     
M O N E Y

The solution to this puzzle is O = 0, M = 1, Y = 2, E = 5, N = 6, D = 7, R = 8, and S = 9.

Yeah, yeah that was not a tip. The points that follow are the tips that you are looking for:

Cryptarithmetic Conventions:

  1. Each letter or symbol represents only one digit throughout the problem;
  2. When letters are replaced by their digits, the resultant arithmetical operation must be correct;
  3. The numerical base, unless specifically stated, is 10;
  4. Numbers must not begin with a zero;
  5. There must be only one solution to the problem.

Subtractions = Upside Down Addition:

Subtraction cyrptarithmetic puzzles are nothing but Upside Down Additions. To make this clear, consider the same example mentioned above, except that it is converted to a subtraction cryptarithmetic puzzle:
  
M O N E Y
-   S E N D
-------------   

    M O R E

Hope I made it clear.

Look for "0" and "9" in Additions or Subtractions:

A good hint to find zero or 9 is to look for columns containing two or three identical letters.

Look at these additions:

     * * * A            * * * B
  + * * * A         + * * * A
     -------              -------
     * * * A            * * * B
The columns A+A=A and B+A=B indicate that A=zero. In math this is called the "additive identity property of zero"; it says that you add "0" to anything and it doesn't change, therefore it stays the same.
Now look at those same additions in the body of the cryptarithm:

      * A * *             * B * *
  + * A * *         +  * A * *
       -------             -------
      * A * *             * B * *
In these cases, we may have A=zero or A=9. It depends whether or not "carry 1" is received from the previous column. In other words, the "9" mimics zero every time it gets a carry-over of "1".

Search for "1" in additions or subtractions


Look for left hand digits. If single, they are probably "1".

Take the world's most famous cryptarithm:

             S E N D
         + M O R E
         ---------
         M O N E Y
"M" can only equal 1, because it is the "carry 1" from the column S+M=O (+10). In other words, every time an addition of "n" digits gives a total of "n+1" digits, the left hand digit of the total must be "1".
In this Madachy's subtraction problem, "C" stands for the digit "1":

         C O U N T
         -   C O I N
            ---------
             S N U B

Search for "1" in multiplications or divisions


In this multiplication:

           M A D
           x  B E
           -------
           M A D
           R A E
           -------
         A M I D
The first partial product is E x MAD = MAD. Hence "E" must equal "1". In math jargon this is called the "identity" property of "1" in multiplication; you multiply anything by "1" and it doesn't change, therefore it remains the same.
Look this division:

               K T
               --------
     N E T / L I N K
                   N E T
                  -------
                K E K K
                K T E C
                 -------
                  K E Y
In the first subtraction, we see K x NET = NET. Then K=1.

Search for "1" and "6" in multiplications or divisions


Any number multiplied by "1" is the number itself. Also, any even number multiplied by "6" is the number itself:

         4 x 1 = 4
         7 x 1 = 7
         2 x 6 = 2 (+10)
         8 x 6 = 8 (+40)         
Looking at right hand digits of multiplications and divisions, can help you spot digits "1" and "6". Those findings will show like these ones:
                               C B
                              ----------
     * * A        * * A / * * * * *
       B C                     * * * C
    ------                    ---------
   * * * C                    * * * *
 * * * B                      * * * B
 ---------                    -------
 * * * * *                     * * *
The logic is: if
   C  x  * * A  =  * * * C 
   B  x  * * A  =  * * * B
then A=1 or A=6.

Search for "0" and "5" in multiplications or divisions


Any number multiplied by zero is zero. Also, any odd number multiplied by "5" is "5":

          3 x 0 = 0
          6 x 0 = 0
          7 x 5 = 5 (+30)
          9 x 5 = 5 (+40)         
Looking at right hand digits of multiplications and divisions, can help you spot digits "0" and "5". Those findings will show like these ones:
                              C B
                            ----------
    * * A        * * A / * * * * *
      B C                     * * * A
  -------                    ---------
  * * * A                    * * * *
  * * * A                    * * * A
---------                    -------
* * * * *                     * * *
The logic is: if
   C  x  * * A  =  * * * A 
   B  x  * * A  =  * * * A
then A=0 or A=5

Match to make progress


Matching is the process of assigning potential values to a variable and testing whether they match the current state of the problem.

To see how this works, let's attack this long-hand division:

                K M
                ----------
    A K A / D A D D Y
                   D Y N A
                    ---------
                    A R M Y
                    A R K A
                     -------
                         R A
To facilitate the analysis, let's break it down to its basic components, i.e., 2 multiplications and 2 subtractions:
  I.   K  x  A K A = D Y N A
  
  II.  M  x  A K A = A R K A
   
  III.        D A D D 
            - D Y N A
               ---------
                A R M  
  IV.         A R M Y
            -  A R K A
               ---------
                  R A
From I and II we get:
   K  x  * * A  =  * * * A
   M  x  * * A  =  * * * A
This pattern suggests A=0 or A=5. But a look at the divisor "A K A" reveals that A=0 is impossible, because leading letters cannot be zero. Hence A=5.
Replacing all A's with "5", subtraction IV becomes:

          5 R M Y
        - 5 R K 5
        ---------
              R 5
From column Y-5=5 we get Y=0.
Replacing all Y's with zero, multiplication I will be:
   K  x  5 K 5  = D 0 N 5
Now, matching can help us make some progress. Digits 1, 2, 3, 4, 6, 7, 8 and 9 are still unidentified. Let's assign all these values to the variable K, one by one, and check which of them matches the above pattern.
Tabulating all data, we would come to:
                           K  x  5K5  =  D0N5
                          ----------------------
                           1     515      515
                           2     525     1050
                           3     535     1605
                           4     545     2180
                           6     565     3390
      SOLUTION --> 7     575     4025 <-- SOLUTION 
                           8     585     4680
                           9     595     5355
                        ----------------------
You can see that K=7 is the only viable solution that matches the current pattern of multiplication I, yielding:
   K  x  A K A  =  D Y N A
   7        5 7 5         4 0 2 5
This solution also identifies two other variables: D=4 and N=2.

When stuck, generate-and-test


Usually we start solving a cryptarithm by searching for 0, 1, and 9. Then if we are dealing with an easy problem there is enough material to proceed decoding the other digits until a solution is found.

This is the exception and not the rule. Most frequently after decoding 1 or 2 letters (and sometimes none) you get stuck. To make progress we must apply the generate-and-test method, which consists of the following procedures:

1. List all digits still unidentified;
2. Select a base variable (letter) to start generation;
3. Do a cycle of generation and testing: from the list of still unidentified digits (procedure 1) get one and assign it to the base variable; eliminate it from the list; proceed guessing values for the other variables; test consistency; if not consistent, go to perform the next cycle (procedure 3); if consistent, stop: you have found the solution to the problem.
To demonstrate how this method works, let's tackle this J. A. H. Hunter's addition:

            T A K E
                     A
       +  C A K E
           ----------
            K A T E
The column AAA suggests A=0 or A=9.
But column EAEE indicates that A+E=10, hence the only acceptable value for "A" is 9, with E=1.
Replacing all "A's" with 9 and all "E's" with 1, we get
            T 9 K 1
                     9
       +  C 9 K 1
         ----------
           K 9 T 1
Letter repetition in columns KKT and TCK allows us to set up the following algebraic system of equations:
       C1 + K + K = T + 10
       C3 + T + C = K         
Obviously C1=1 and C3=1. Solving the equation system we get K+C=8: not much, but we discovered a relationship between the values of "K" and "C" that will help us later. 
But now we are stuck! It's time to use the "generate-and-test" method.
Procedure 1: digits 2,3,4,5,6,7 and 8 are still unidentified;

Procedure 2: we select "K" as the base variable;

CYCLE #1, procedure 3: column TCK shows that T+C=K and no carry, hence "K" must be a high valued digit. So we enter the list obtained through procedure 1 from the high side, assigning "8" to the base variable "K".

Knowing that K+C=8, if K=8 then C=0. But this is an unacceptable value for "C", because the addend "CAKE" would become "0981" and cryptarithmetic conventions say that no number can start with zero. So, we must close this cycle and begin cycle #2.

By now, the addition layout and the table summarizing current variable data would look like this:

    T 9 8 1   CYCLE  A   E   K   C   T
            9   ========================
+  0 9 8 1    #1    9   1   8  [0]
----------
    8 9 T 1
Conflicting values for variables are noted within square brackets.
CYCLE #2, procedure 3: assigning "7" to the letter "K" we get C=1 because K+C=8. This is an unacceptable value for "C" considering that we have already fixed E=1. Again we have to close the current cycle and go to cycle #3, with the setup and table showing:

    T 9 7 1   CYCLE  A   E   K   C   T
            9   ========================
+  1 9 7 1    #1    9   1   8  [0]
----------     #2    9   1   7  [1]
    7 9 T 1
CYCLE #3, procedure 3: assigning "6" to the letter "K" we get C=2 because K+C=8. Testing these values for "K" and "C" in the column TCK, we get C3+T+2+=6 making T=3.
Now, testing T in column KKT, we would obtain C1+K+K=T+10 or 1+6+6=T+10, making T=3. This is an acceptable value for T, confirming the previous value T=3 we had already found.

So, we have got the final solution to the problem, stopping the routine "generate-and-test".

The final layout and table would read

    3 9 6 1   CYCLE  A   E   K   C   T
            9   ========================
+  2 9 6 1     #1    9   1   8  [0]
----------      #2    9   1   7  [1]
    6 9 3 1    #3    9   1    6   2   3    


We will see some typical cryptarithmetic puzzles which were asked in the Elitmus test.

You can find the solved example of a cryptarithm asked in elitmus below:

Multiplication Cryptarithmetic Puzzle - 1


Solved Questions asked in eLitmus

3 comments:

  1. how could u assign O = 0, M = 1, Y = 2, E = 5, N = 6, D = 7, R = 8, and S = 9 values?? are they default values??

    ReplyDelete
  2. Hello,
    No, those are not the default values. I got those values after solving the puzzle. I have solved many such problems in this blog, you can check them out to get a feel of how to solve such kind of puzzles.

    ReplyDelete
  3. Find More Information about crypt
    http://www.informguru.com/search/label/cryptarithmetic

    ReplyDelete