Problem Definition
Cryptarithm is a genre of mathematical puzzles in which the digits are replaced by letters of the alphabet or other symbols. (See the figure below.) If the same letter occurs more than once, it must be assigned the same digit each time. No two different letters may be assigned the same digit. So, the problem is to find the unique digit corresponding to a unique letter. Cryptarithmetic is the science and art of creating and solving cryptarithms. J. A. Hunter coined the word alphametic to designate a cryptaritm whose letters form sensible words or phrases.
S E N D
+ M O R E
-----------------
M O N E Y
The world’s best known alphametic puzzle is SEND+MORE = MONEY.
Explanation and Overview
The concept was first introduced by H.E. Dudeney and was first published in the July 1924 issue of Strand Magazine associated with the story of a kidnapper’s ransom demand.
Cryptarithmetic is a suitable example of the Constraint Satisfaction Problem. Instead of providing a description, a cryptarithmetic problem can be better described by some constraints. The constraints of defining a cryptarithmetic problem are as follows:
- Each letter or symbol represents only one and a unique digit throughout the problem.
- When the digits replace letters or symbols, the resultant arithmetical operation must be correct.
These two constraints lead to some other restrictions in the problem. Consider that the base of the numbers is 10. Then there must be at most 10 unique symbols or letters in the problem. Otherwise, it would not be possible to assign a unique digit to each unique letter or symbol in the problem.
To be semantically meaningful, a number must not begin with a zero. So, the letters at the beginning of each number should not correspond to zero.
Program Logic
Error Checking
Before we can apply any algorithm, we need to verify that the input entered by the user is proper.
- Total number of distinct letters should be less or equal to 10.
- Length of answer should not be lesser than the length of any operand.
- Length of answer can be only one more than any of the operands.
There are two algorithms which we can apply here to solve the problem. These are Constraint Specification and Evolutionary Algorithm.
Constraint Specification
Constraints are specific to the problem. Here are some examples. The puzzle SEND + MORE = MONEY, after solving, will appear like this:
S E N D
9 5 6 7
+ M O R E
1 0 8 5
---------
M O N E Y
1 0 6 5 2
Search 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 the 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 on 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
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".
A blind search can eventually find the solutions, if there is any, in a bound time. Given that the base of the number is 10, there may be 10n solutions to be checked in the problem space; where n is the number of unique letters or symbols in the problem. A rule based searching technique can provide the solution in minimum time.
When constraints are applied to the problem, if there are any, the solution space to be searched decreases.
Evolutionary Algorithm
An Evolutionary Algorithm (EA) is a common term for algorithms that utilize the adaptive behavior modeled after principles of nature.
Although the definition of Evolutionary Algorithm differs, the more common properties of EAs are that collections of potential solutions to the problem at hand are maintained.
These solutions are referred to as the population of a current generation. Each potential solution is called a chromosome.
Operations are applied to the current population to produce a new generation that will hopefully contain chromosomes that are better solutions of the problem. This process continues until some threshold value or stopping criterion is met.
The new population is produced through the operators on selected chromosomes of the current generation. Typically, the chromosomes of the current generation, to whom the operators are applied, are chosen based on their quality. In this way, it is more likely that the offspring chromosomes inherit desirable characteristics of its parents. Some heuristics or fitness functions are used to choose parent chromosomes in a generation.
So, a string of length 10 field by those letters and additional don’t care symbol(s) is a good choice. If the base of the number is n, then we will use an array of length n. The position of the letters in the string denotes their value.
S E N D M O R Y _ _
0 1 2 3 4 5 6 7 8 9
Above ‘_’ (underscore) is used as a don’t care symbol and the numbers just under the letters denote their position in the string as well as their respective values in the solution.
Now we can generate two random numbers and interchange the position of those letters as shown in figures below:
Y N R M _ O E D _ S
0 1 2 3 4 5 6 7 8 9
Position of letters after mutuation:
Y N R M _ O D E _ S
0 1 2 3 4 5 6 7 8 9
A Fitness function usually indicates the degree of correctness of a chromosome. An evaluation function can be easily formulated which will calculate the error of the mathematical result in the problem.
S E N D
9 7 1 6
+ M O R E
3 5 2 7
-------------
M O N E Y
3 5 1 7 0
ERROR = ABS (35170-(9716+3527)) = 21927
A chromosome with the minimum error is the fittest chromosome in a generation. To ensure that the offspring generation is not worse than the current one, the fittest chromosome of the current generation can be added to the next generation. But, this will introduce a deadlock when these fittest chromosomes cannot lead to a solution, even though there exists a solution. Or a problem called Local Minima. So, a random chromosome can be given a chance to contribute to the next generation. This modification will avoid deadlocks.
Algorithm
- Step 1: Scan the input strings.
- Step 2: Check that the input is proper.
- Step 3: Put the letters or symbols in
ARRAY[10]. - Step 4: Apply arithmetic rules and try to reduce the solution space.
- Step 5: If the number of distinct letter is less than 10, then fill the rest of the indices of
ARRAY with don’t care symbols. This ARRAY[10] now is our current generation. - Step 6: For several times, generate two random numbers m,n and swap the contents of index m and n of any one chromosome of the current generation and copy this new chromosome to the next generation.
- Step 7: Evaluate the fitness of each chromosome of the next generation and choose the best chromosomes. Now these best chromosomes become our current generation. Also include one random chromosome to the current generation. If there is no chromosome with error 0 in the current generation, then go to step 6. If one of the chromosomes is found with error 0, then report the solution and exit.
According to the toughness of the particular problem, a few parameters like the number of chromosomes in each generation, number of chromosomes selected for reproduction, and random chromosomes taken to avoid local minima should be set to get the solution using minimal search.
The Code
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
namespace CryptArithmetic
{
public partial class Form1 : Form
{
char[] s1 = new char[10];
char[] s2 = new char[10];
char[] s3 = new char[10];
int[] assinged = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
char[] c = new char[11];
int[] val = new int[11];
int topc = 0;
public Form1()
{
InitializeComponent();
}
private void btn_ok_Click(object sender, EventArgs e)
{
label4.Text = "";
s1 = textBox1.Text.ToCharArray();
s2 = textBox2.Text.ToCharArray();
s3 = textBox3.Text.ToCharArray();
int flag=0;
for(int i=0;i<s1.Length;i++)
{
for(int j=0;j<=topc;j++)
{
if(s1[i]!=c[j])
flag=1;
else
{
flag =0;
break;
}
}
if(flag==1)
c[topc++] =s1[i];
}
for(int i=0;i<s2.Length;i++)
{
for(int j=0;j<=topc;j++)
{
if(s2[i]!=c[j])
flag=1;
else
{
flag =0;
break;
}
}
if(flag==1)
c[topc++] =s2[i];
}
for(int i=0;i<s3.Length;i++)
{
for(int j=0;j<=topc;j++)
{
if(s3[i]!=c[j])
flag=1;
else
{
flag =0;
break;
}
}
if(flag==1)
c[topc++] =s3[i];
}
if (solve(0, assinged)==1)
{
for(int i=0;i<c.Length;i++)
label4.Text += "\n"+ c[i]+"--->"+val[i].ToString() + "\n";
}
else
label4.Text = "Sorry";
}
int solve(int ind,int []temp1)
{
int [] temp2 = new int[10];
int flag=0;
for(int i=0;i<10;i++)
{
if(temp1[i]==0)
{
for(int j=0;j<10;j++)
temp2[j]=temp1[j];
temp2[i]=1;
val[ind]=i;
if(ind==(topc-1))
{
if(verify()==1)
{
flag=1;
goto exit;
}
}
else
{
if(solve(ind+1,temp2)==1)
{
flag=1;
goto exit;
}
}
}
}
exit :
if(flag!=0)
return 1;
else
return 0;
}
int verify()
{
long n1=0,n2=0,n3=0;
long power=1;
char ch;
int i=s1.Length-1;
int in1;
while(i>=0)
{
ch=s1[i];
in1=0;
while(in1!=topc)
{
if(c[in1]==ch)
break;
else
in1++;
}
n1+=power*val[in1];
power *=10;
i--;
}
power=1;
i=s2.Length-1;
while(i>=0)
{
ch=s2[i];
in1=0;
while(in1!=topc)
{
if(c[in1]==ch)
break;
else
in1++;
}
n2+=power*val[in1];
power *=10;
i--;
}
power=1;
i=s3.Length-1;
while(i>=0)
{
ch=s3[i];
in1=0;
while(in1!=topc)
{
if(c[in1]==ch)
break;
else
in1++;
}
n3+=power*val[in1];
power *=10;
i--;
}
if(n1+n2==n3)
return 1;
else
return 0;
}
private void Form1_Load(object sender, EventArgs e)
{
}
private void textBox1_TextChanged(object sender, EventArgs e)
{
}
}
}
Limitation
This program has still a chance such that we can increase the efficiency and get the output in minimum time. It finds the maximum 10 distinct solutions, if they exist, not more than 10. This is limited to only addition and doesn’t solve subtraction or multiplication problems. This is also limited to solving problems which have two operands and can’t be used to solve more than two operands in an equation.
Sample Input/Output
References:
- Artificial Intelligence by Kelvin Knight and Rich.
