Cryptarithmatic and Constraint Satisfaction Procedures

Cryptarithmatic puzzles consist of calculations where all of the numbers have been replaced by letters, such as SEND + MORE = MONEY. To solve the puzzle you need to find which digit each letter represents. Constraint satisfaction is a kind of reasoning that uses constraints to deduce a solution to problems -- it is a natural way to solve cryptarithmatic puzzles because the many constraints of arithmetic are well known and easy to apply.
  1. Arithmetic Constraints

    • Consider the constraints of arithmetic when approaching a problem. For example, in the SEND + MORE = MONEY puzzle, two four-digit numbers are added to get a five-digit number. This means that M is a carry. M can only be 1. The constraint that the carry from the addition of two digits can only be 1 starts us on the path to solving the problem.

    Updating the Puzzle

    • Update the puzzle as you find solutions for each digit. Having the digits mixed in with the letters makes it easier to solve for new digits. After we find that M = 1 in the SEND + MORE = MONEY puzzle, we would rewrite it as: SEND + 1ORE = 1ONEY

    Cryptarithmatic Constraints

    • Add the few constraints that are standard with cryptarithmatic puzzles to the constraints inherent in mathematics. One of these constraints is that each letter represents a single digit. We can use this constraint to get the second part of the puzzle to the SEND + 1ORE = 1ONEY puzzle. The letter O is either 0 or 1 because S + 1 or S + carry + 1 = 10 or 11, but S cannot be 1 because is 1; therefore O is 0, and we now have SEND + 10RE = 10NEY.

    Relationships between Columns

    • Determine whether or not there is a carry from one column to find the results of the column to the left. For example, S can be 8 or 9, depending on if there is a carry from the E + 0 = N or E + carry + 0 = N column. E must be different from N, using another constraint. Therefore, we have E + 1 = N, and E and N cannot be 8 and 9 as S must be one of these. With this information, S is 9, and we have 9END + 10RE = 10NEY.

    More Complex Constraints

    • From 9END + 10RE = 10NEY, we see that E + 1 = N with no carry because E cannot be 9 and N cannot be 0. From the next column to the right, N + R + possibly 1 more = E + 10. If we subtract one formula from the other, such that [N + R + possibly 1 more = E + 10] - [E + 1 = N], we get R + possibly one more = 9, which means that R = 8 because S was 9. Now we have 9END + 108E = 10NEY. Continuing in this fashion, we ultimately get 9,567 + 1,085 = 10,652.

Learnify Hub © www.0685.com All Rights Reserved