Solving Cryptarithmetic Puzzles
What is Crypt-arithmetic Puzzle?
A Crypt-arithmetic puzzle, also known as a cryptogram, is a type of mathematical puzzle in which we assign digits to alphabetical letters or symbols. The end goal is to find the unique digit assignment to each letter so that the given mathematical operation holds true. In this puzzle, the equation performing an addition operation is the most commonly used. However, it also involves other arithmetic operations, such as subtraction, multiplication etc.
The rules for a Crypt-arithmetic puzzle are as follows −
We can use digits from 0 to 9 only to represent a unique alphabetical letter in the puzzle.
The same digit cannot be assigned to different letters in the whole equation.
The resulting equation formed by replacing letters with digits should be mathematically correct.
Input Output Scenario
Suppose the given equation is −
Input: B A S E B A L L ---------- G A M E S
In the above equation, the words namely "BASE" and "BALL" are added to produce "GAMES". The algorithm will associate each letter of the given words with a unique number from 0 to 9. For the above input, the ouput should be −
Solving Crypt-arithmetic Puzzles using Backtracking Approach
The naive approach to solving the cryptarithmetic problem is by taking one letter from each operand starting from the left-hand side and assigning digits from 0 to 9 one by one. After assigning the digits, check the validity of the arithmetic expression. However, this method is inefficient for larger operands.
To solve a crypt-arithmetic problem using the backtracking approach, follow the below steps −
First, identify all the unique characters from the given arithmetic expression.
Next, try assigning digits to the letters. If duplicacy is found backtrack and unassign. This way all possible combinations of digits for each letter will be generated.
Now, replace the letters with digits and check if the expression is true.
Example
In the following example, we will practically demonstrate how to solve the cryptarithmetic problem.
#include <stdio.h>
#include <string.h>
//set 1, when one character is assigned previously
int use[10] = {0};
// structure
struct node {
char letter;
int value;
};
int isValid(struct node* nodeList, const int count, char* s1, char* s2, char* s3) {
int val1 = 0, val2 = 0, val3 = 0, m = 1, j, i;
//find number for first string
for (i = strlen(s1) - 1; i >= 0; i--) {
char ch = s1[i];
for (j = 0; j < count; j++)
//when ch is present, break the loop
if (nodeList[j].letter == ch)
break;
val1 += m * nodeList[j].value;
m *= 10;
}
m = 1;
//find number for second string
for (i = strlen(s2) - 1; i >= 0; i--) {
char ch = s2[i];
for (j = 0; j < count; j++)
if (nodeList[j].letter == ch)
break;
val2 += m * nodeList[j].value;
m *= 10;
}
m = 1;
//find number for third string
for (i = strlen(s3) - 1; i >= 0; i--) {
char ch = s3[i];
for (j = 0; j < count; j++)
if (nodeList[j].letter == ch)
break;
val3 += m * nodeList[j].value;
m *= 10;
}
//check whether the sum is same as 3rd string or not
if (val3 == (val1 + val2))
return 1;
return 0;
}
int permutation(int count, struct node* nodeList, int n, char* s1, char* s2, char* s3) {
//when values are assigned for all characters
if (n == count - 1) {
for (int i = 0; i < 10; i++) {
// for those numbers, which are not used
if (use[i] == 0) {
//assign value i
nodeList[n].value = i;
//check validation
if (isValid(nodeList, count, s1, s2, s3) == 1) {
printf("Solution found: ");
//print code, which are assigned
for (int j = 0; j < count; j++)
printf(" %c = %d", nodeList[j].letter, nodeList[j].value);
return 1;
}
}
}
return 0;
}
for (int i = 0; i < 10; i++) {
// for those numbers, which are not used
if (use[i] == 0) {
//assign value i and mark as not available for future use
nodeList[n].value = i;
use[i] = 1;
//go for next characters
if (permutation(count, nodeList, n + 1, s1, s2, s3) == 1)
return 1;
//when backtracks, make available again
use[i] = 0;
}
}
return 0;
}
int solvePuzzle(char* s1, char* s2, char* s3) {
//Number of unique characters
int uniqueChar = 0;
int len1 = strlen(s1);
int len2 = strlen(s2);
int len3 = strlen(s3);
//There are 26 different characters
int freq[26] = {0};
for (int i = 0; i < len1; i++)
++freq[s1[i] - 'A'];
for (int i = 0; i < len2; i++)
++freq[s2[i] - 'A'];
for (int i = 0; i < len3; i++)
++freq[s3[i] - 'A'];
for (int i = 0; i < 26; i++)
//whose frequency is > 0, they are present
if (freq[i] > 0)
uniqueChar++;
//as there are 10 digits in decimal system
if (uniqueChar > 10) {
printf("Invalid strings");
return 0;
}
struct node nodeList[uniqueChar];
//assign all characters found in three strings
for (int i = 0, j = 0; i < 26; i++) {
if (freq[i] > 0) {
nodeList[j].letter = (char)(i + 'A');
j++;
}
}
return permutation(uniqueChar, nodeList, 0, s1, s2, s3);
}
int main() {
char s1[] = "BASE";
char s2[] = "BALL";
char s3[] = "GAMES";
if (solvePuzzle(s1, s2, s3) == 0)
printf("No solution");
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
//set 1, when one character is assigned previously
vector<int> use(10);
struct node {
char letter;
int value;
};
int isValid(node* nodeList, const int count, string s1, string s2, string s3) {
int val1 = 0, val2 = 0, val3 = 0, m = 1, j, i;
//find number for first string
for (i = s1.length() - 1; i >= 0; i--) {
char ch = s1[i];
for (j = 0; j < count; j++)
//when ch is present, break the loop
if (nodeList[j].letter == ch)
break;
val1 += m * nodeList[j].value;
m *= 10;
}
m = 1;
//find number for second string
for (i = s2.length() - 1; i >= 0; i--) {
char ch = s2[i];
for (j = 0; j < count; j++)
if (nodeList[j].letter == ch)
break;
val2 += m * nodeList[j].value;
m *= 10;
}
m = 1;
//find number for third string
for (i = s3.length() - 1; i >= 0; i--) {
char ch = s3[i];
for (j = 0; j < count; j++)
if (nodeList[j].letter == ch)
break;
val3 += m * nodeList[j].value;
m *= 10;
}
//check whether the sum is same as 3rd string or not
if (val3 == (val1 + val2))
return 1;
return 0;
}
bool permutation(int count, node* nodeList, int n, string s1, string s2, string s3) {
//when values are assigned for all characters
if (n == count - 1) {
for (int i = 0; i < 10; i++) {
// for those numbers, which are not used
if (use[i] == 0) {
//assign value i
nodeList[n].value = i;
//check validation
if (isValid(nodeList, count, s1, s2, s3) == 1) {
cout << "Solution found: ";
//print code, which are assigned
for (int j = 0; j < count; j++)
cout << " " << nodeList[j].letter << " = " << nodeList[j].value;
return true;
}
}
}
return false;
}
for (int i = 0; i < 10; i++) {
// for those numbers, which are not used
if (use[i] == 0) {
//assign value i and mark as not available for future use
nodeList[n].value = i;
use[i] = 1;
//go for next characters
if (permutation(count, nodeList, n + 1, s1, s2, s3))
return true;
//when backtracks, make available again
use[i] = 0;
}
}
return false;
}
bool solvePuzzle(string s1, string s2,string s3) {
//Number of unique characters
int uniqueChar = 0;
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
//There are 26 different characters
vector<int> freq(26);
for (int i = 0; i < len1; i++)
++freq[s1[i] - 'A'];
for (int i = 0; i < len2; i++)
++freq[s2[i] - 'A'];
for (int i = 0; i < len3; i++)
++freq[s3[i] - 'A'];
for (int i = 0; i < 26; i++)
//whose frequency is > 0, they are present
if (freq[i] > 0)
uniqueChar++;
//as there are 10 digits in decimal system
if (uniqueChar > 10) {
cout << "Invalid strings";
return 0;
}
node nodeList[uniqueChar];
//assign all characters found in three strings
for (int i = 0, j = 0; i < 26; i++) {
if (freq[i] > 0) {
nodeList[j].letter = char(i + 'A');
j++;
}
}
return permutation(uniqueChar, nodeList, 0, s1, s2, s3);
}
int main() {
string s1 = "BASE";
string s2 = "BALL";
string s3 = "GAMES";
if (solvePuzzle(s1, s2, s3) == false)
cout << "No solution";
}
public class Main {
// Set 1 when one character is assigned previously
int[] use = new int[10];
class Node {
char letter;
int value;
}
public int isValid(Node[] nodeList, int count, String s1, String s2, String s3) {
int val1 = 0, val2 = 0, val3 = 0;
int m = 1;
int j, i;
//find number for first string
for (i = s1.length() - 1; i >= 0; i--) {
char ch = s1.charAt(i);
for (j = 0; j < count; j++) {
// when ch is present, break the loop
if (nodeList[j].letter == ch) {
break;
}
}
val1 += m * nodeList[j].value;
m *= 10;
}
m = 1;
//find number for second string
for (i = s2.length() - 1; i >= 0; i--) {
char ch = s2.charAt(i);
for (j = 0; j < count; j++) {
if (nodeList[j].letter == ch) {
break;
}
}
val2 += m * nodeList[j].value;
m *= 10;
}
m = 1;
//find number for third string
for (i = s3.length() - 1; i >= 0; i--) {
char ch = s3.charAt(i);
for (j = 0; j < count; j++) {
if (nodeList[j].letter == ch) {
break;
}
}
val3 += m * nodeList[j].value;
m *= 10;
}
//check whether the sum is same as 3rd string or not
if (val3 == (val1 + val2)) {
return 1;
}
return 0;
}
public int permutation(int count, Node[] nodeList, int n, String s1, String s2, String s3) {
//when values are assign
if (n == count - 1) {
// for those numbers, which are not used
for (int i = 0; i < 10; i++) {
if (use[i] == 0) {
//assign value i
nodeList[n].value = i;
if (isValid(nodeList, count, s1, s2, s3) == 1) {
System.out.print("Solution found:");
//print code, which are assigned
for (int j = 0; j < count; j++) {
System.out.print(" " + nodeList[j].letter + " = " + nodeList[j].value);
}
return 1;
}
}
}
return 0;
}
// for those numbers, which are not used
for (int i = 0; i < 10; i++) {
if (use[i] == 0) {
//assign value i and mark as not available for future use
nodeList[n].value = i;
use[i] = 1;
if (permutation(count, nodeList, n + 1, s1, s2, s3) == 1) {
//go for next characters
return 1;
}
//when backtracks, make available again
use[i] = 0;
}
}
return 0;
}
public int solvePuzzle(String s1, String s2, String s3) {
//Number of unique characters
int uniqueChar = 0;
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
// There are 26 different characters
int[] freq = new int[26];
for (int i = 0; i < len1; i++) {
freq[s1.charAt(i) - 'A']++;
}
for (int i = 0; i < len2; i++) {
freq[s2.charAt(i) - 'A']++;
}
for (int i = 0; i < len3; i++) {
freq[s3.charAt(i) - 'A']++;
}
//whose frequency is > 0, they are present
for (int i = 0; i < 26; i++) {
if (freq[i] > 0) {
uniqueChar++;
}
}
//as there are 10 digits in decimal system
if (uniqueChar > 10) {
System.out.println("Invalid strings");
return 0;
}
Node[] nodeList = new Node[uniqueChar];
int j = 0;
for (int i = 0; i < 26; i++) {
//assign all characters found in three strings
if (freq[i] > 0) {
nodeList[j] = new Node();
nodeList[j].letter = (char) (i + 'A');
j++;
}
}
return permutation(uniqueChar, nodeList, 0, s1, s2, s3);
}
public static void main(String[] args) {
Main main = new Main();
String s1 = "BASE";
String s2 = "BALL";
String s3 = "GAMES";
if (main.solvePuzzle(s1, s2, s3) == 0) {
System.out.println("No solution");
}
}
}
class Main:
#Set 1 when one character is assigned previously
use = [0] * 10
class Node:
def __init__(self):
self.letter = ''
self.value = 0
def isValid(self, nodeList, count, s1, s2, s3):
val1 = 0
val2 = 0
val3 = 0
m = 1
j = 0
i = 0
#find number for first string
for i in range(len(s1) - 1, -1, -1):
ch = s1[i]
for j in range(count):
#when ch is present, break the loop
if nodeList[j].letter == ch:
break
val1 += m * nodeList[j].value
m *= 10
m = 1
#find number for the second string
for i in range(len(s2) - 1, -1, -1):
ch = s2[i]
for j in range(count):
if nodeList[j].letter == ch:
break
val2 += m * nodeList[j].value
m *= 10
m = 1
#find number for the third string
for i in range(len(s3) - 1, -1, -1):
ch = s3[i]
for j in range(count):
if nodeList[j].letter == ch:
break
val3 += m * nodeList[j].value
m *= 10
#check whether the sum is the same as the 3rd string or not
if val3 == (val1 + val2):
return 1
return 0
def permutation(self, count, nodeList, n, s1, s2, s3):
#when values are assigned
if n == count - 1:
for i in range(10):
#for those numbers, which are not used
if self.use[i] == 0:
#assign value i
nodeList[n].value = i
if self.isValid(nodeList, count, s1, s2, s3) == 1:
print("Solution found:", end='')
#print code, which is assigned
for j in range(count):
print(f" {nodeList[j].letter} = {nodeList[j].value}", end='')
return 1
return 0
for i in range(10):
#for those numbers, which are not used
if self.use[i] == 0:
#assign value i and mark as not available for future use
nodeList[n].value = i
self.use[i] = 1
if self.permutation(count, nodeList, n + 1, s1, s2, s3) == 1:
#go for the next characters
return 1
#when backtracking, make available again
self.use[i] = 0
return 0
def solvePuzzle(self, s1, s2, s3):
#Number of unique characters
uniqueChar = 0
len1 = len(s1)
len2 = len(s2)
len3 = len(s3)
#There are 26 different characters
freq = [0] * 26
for i in range(len1):
freq[ord(s1[i]) - ord('A')] += 1
for i in range(len2):
freq[ord(s2[i]) - ord('A')] += 1
for i in range(len3):
freq[ord(s3[i]) - ord('A')] += 1
for i in range(26):
#whose frequency is > 0, they are present
if freq[i] > 0:
uniqueChar += 1
#as there are 10 digits in the decimal system
if uniqueChar > 10:
print("Invalid strings")
return 0
nodeList = [self.Node() for _ in range(uniqueChar)]
j = 0
for i in range(26):
#assign all characters found in three strings
if freq[i] > 0:
nodeList[j].letter = chr(i + ord('A'))
j += 1
return self.permutation(uniqueChar, nodeList, 0, s1, s2, s3)
if __name__ == "__main__":
main = Main()
s1 = "BASE"
s2 = "BALL"
s3 = "GAMES"
if main.solvePuzzle(s1, s2, s3) == 0:
print("No solution")
Output
Solution found: A = 4 B = 2 E = 1 G = 0 L = 5 M = 9 S = 6
