Page 1 of 6
Home Whiteboard Graphing Calculator Online Compilers Articles Tools
Home Data_structures_algorithms Solving Cryptarithmetic Puzzles
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
----------
Advertisement
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 −
Page 2 of 6
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.
C C++ Java Python
Advertisement
#include <stdio.h>
#include <string.h>
//set 1, when one character is assigned previously
int use[10] = {0};
// structure
struct node {
Page 3 of 6
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;
Advertisement
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
Page 4 of 6
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
Chapters
if (permutation(count, nodeList, n + 1, s1, s2, s3) == 1) Categories
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};
Advertisement
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
Page 5 of 6
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;
}
Output
Solution found: A = 4 B = 2 E = 1 G = 0 L = 5 M = 9 S = 6
TOP TUTORIALS TRENDING TECHNOLOGIES
Python Tutorial Cloud Computing Tutorial
Java Tutorial Amazon Web Services Tutorial
Advertisement
C++ Tutorial Microsoft Azure Tutorial
C Programming Tutorial Git Tutorial
C# Tutorial Ethical Hacking Tutorial
PHP Tutorial Docker Tutorial
R Tutorial Kubernetes Tutorial
HTML Tutorial DSA Tutorial
CSS Tutorial Spring Boot Tutorial
JavaScript Tutorial SDLC Tutorial Page 6 of 6
SQL Tutorial Unix Tutorial
CERTIFICATIONS COMPILERS & EDITORS
Business Analytics Certification Online Java Compiler
Java & Spring Boot Advanced Certification Online Python Compiler
Data Science Advanced Certification Online Go Compiler
Cloud Computing And DevOps Online C Compiler
Advanced Certification In Business Analytics Online C++ Compiler
Artificial Intelligence And Machine Learning Online C# Compiler
DevOps Certification Online PHP Compiler
Game Development Certification Online MATLAB Compiler
Front-End Developer Certification Online Bash Terminal
AWS Certification Training Online SQL Compiler
Python Programming Certification Online Html Editor
ABOUT US | OUR TEAM | CAREERS | JOBS | CONTACT US | TERMS OF USE |
PRIVACY POLICY | REFUND POLICY | COOKIES POLICY | FAQ'S
Tutorials Point is a leading Ed Tech company striving to provide the best learning material on
technical and non-technical subjects.
© Copyright 2026. All Rights Reserved.
Advertisement