ในปัญหา crypt-arithmetic ตัวอักษรบางตัวถูกใช้กำหนดค่าตัวเลข เช่น ตัวอักษร 10 ตัวแทนค่าตัวเลข 0 ถึง 9 เพื่อทำให้การดำเนินการคณิตศาสตร์ถูกต้อง มีสองคำให้ และอีกคำหนึ่งเป็นคำตอบของการบวกสองคำนั้น ตัวอย่างเช่น สองคำ 'BASE' และ 'BALL' และผลลัพธ์คือ 'GAMES' ตอนนี้ถ้าเราลองบวก BASE และ BALL ด้วยตัวเลขสัญลักษณ์ของพวกเขา เราจะได้คำตอบ GAMES
NOTE − ต้องมีตัวอักษรสูงสุด 10 ตัว มิฉะนั้นจะแก้ไม่ได้
อินพุต
อัลกอริทึมนี้จะรับ 3 คำ
เอาต์พุต
จะแสดงว่าตัวอักษรไหนเก็บตัวเลขไหนจาก 0-9
สำหรับกรณีนี้เป็นดังนี้
| Letter | A | B | E | G | L | M | S |
| Values | 4 | 2 | 1 | 0 | 5 | 9 | 6 |
อัลกอริทึม
สำหรับปัญหานี้ เราจะกำหนด node ซึ่งประกอบด้วยตัวอักษรและค่าที่สอดคล้อง
isValid(nodeList, count, word1, word2, word3)
Input - รายการโหนด จำนวนองค์ประกอบในรายการโหนด และสามคำ
Output - True หากผลรวมของค่าสำหรับ word1 และ word2 เท่ากับค่าของ word3
Begin
m := 1
for each letter i from right to left of word1, do
ch := word1[i]
for all elements j in the nodeList, do
if nodeList[j].letter = ch, then
break
done
val1 := val1 + (m * nodeList[j].value)
m := m * 10
done
m := 1
for each letter i from right to left of word2, do
ch := word2[i]
for all elements j in the nodeList, do
if nodeList[j].letter = ch, then
break
done
val2 := val2 + (m * nodeList[j].value)
m := m * 10
done
m := 1
for each letter i from right to left of word3, do
ch := word3[i]
for all elements j in the nodeList, do
if nodeList[j].letter = ch, then
break
done
val3 := val3 + (m * nodeList[j].value)
m := m * 10
done
if val3 = (val1 + val2), then
return true
return false
End
permutation(nodeList, count, n, word1, word2, word3)
Input - รายการโหนด จำนวนรายการในลิสต์ จำนวนตัวอักษรที่มอบหมายแล้ว และสามคำ
Output - True เมื่อตัวอักษรทั้งหมดถูกมอบหมายค่าอย่างถูกต้องเพื่อแก้ปัญหาการบวก
Begin
if n letters are assigned, then
for all digits i from 0 to 9, do
if digit i is not used, then
nodeList[n].value := i
if isValid(nodeList, count, word1, word2, word3) = true
for all items j in the nodeList, do
show the letter and corresponding values.
done
return true
done
return false
for all digits i from 0 to 9, do
if digit i is not used, then
nodeList[n].value := i
mark as i is used
if permutation(nodeList, count, n+1, word1, word2, word3),
return true
otherwise mark i as not used
done
return false
End
ตัวอย่าง
#include <iostream>
#include<vector>
using namespace std;
vector<int> use(10); // set 1, when one character is assigned previously
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;
for (i = s1.length() - 1; i >= 0; i--) { // find number for first string
char ch = s1[i];
for (j = 0; j < count; j++)
if (nodeList[j].letter == ch) // when ch is present, break the loop
break;
val1 += m * nodeList[j].value;
m *= 10;
}
m = 1;
for (i = s2.length() - 1; i >= 0; i--) { // find number for second string
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;
for (i = s3.length() - 1; i >= 0; i--) { // find number for third string
char ch = s3[i];
for (j = 0; j < count; j++)
if (nodeList[j].letter == ch)
break;
val3 += m * nodeList[j].value;
m *= 10;
}
if (val3 == (val1 + val2)) // check whether the sum is same as 3rd string or not
return 1;
return 0;
}
bool permutation(int count, node* nodeList, int n, string s1, string s2, string s3) {
if (n == count - 1) { // when values are assigned for all characters
for (int i = 0; i < 10; i++) {
if (use[i] == 0) { // for those numbers, which are not used
nodeList[n].value = i; // assign value i
if (isValid(nodeList, count, s1, s2, s3) == 1) { // check validation
cout << "Solution found: ";
for (int j = 0; j < count; j++) // print code, which are assigned
cout << " " << nodeList[j].letter << " = " << nodeList[j].value;
return true;
}
}
}
return false;
}
for (int i = 0; i < 10; i++) {
if (use[i] == 0) { // for those numbers, which are not used
nodeList[n].value = i; // assign value i and mark as not available for future use
use[i] = 1;
if (permutation(count, nodeList, n + 1, s1, s2, s3)) // go for next characters
return true;
use[i] = 0; // when backtracks, make available again
}
}
return false;
}
bool solvePuzzle(string s1, string s2, string s3) {
int uniqueChar = 0; // Number of unique characters
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
vector<int> freq(26); // There are 26 different characters
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++)
if (freq[i] > 0) // whose frequency is > 0, they are present
uniqueChar++;
if (uniqueChar > 10) { // as there are 10 digits in decimal system
cout << "Invalid strings";
return 0;
}
node nodeList[uniqueChar];
for (int i = 0, j = 0; i < 26; i++) { // assign all characters found in three strings
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";
}
ผลลัพธ์
Solution found: A = 4 B = 2 E = 1 G = 0 L = 5 M = 9 S = 6
