암호 산수(Crypt-Arithmetic) 문제는 알파벳 문자에 숫자를 대입하여 산술 연산이 성립하도록 만드는 퍼즐입니다. 서로 다른 열 개 이하의 문자가 0부터 9까지의 숫자 값을 하나씩 가지며, 각 문자에 대응하는 숫자로 계산했을 때 연산 결과가 실제로 맞아야 합니다.
가장 대표적인 예시는 두 단어 'BASE'와 'BALL'을 더한 결과가 'GAMES'가 되는 경우입니다. 각 문자에 적절한 숫자를 배정하면 BASE + BALL = GAMES라는 등식이 실제 숫자 연산으로 성립하게 됩니다.
참고: 사용되는 고유 문자는 최대 10개여야 합니다. 10진법에서 사용할 수 있는 숫자가 0~9까지 총 10개뿐이기 때문에, 문자가 11개 이상이면 문제를 풀 수 없습니다.
입력과 출력
입력:
알고리즘은 세 개의 단어를 입력받습니다.
B A S E
B A L L
----------
G A M E S
출력:
각 문자가 0~9 중 어떤 숫자를 가지는지 보여줍니다.
이 예시의 경우 다음과 같습니다.
B A S E 2 4 6 1
B A L L 2 4 5 5
--------- ---------
G A M E S 0 4 9 1 6알고리즘 설계
이 문제를 해결하기 위해 먼저 노드(node)를 정의합니다. 노드는 하나의 문자와 그에 대응하는 숫자 값을 함께 저장하는 구조체입니다. 그다음 백트래킹(backtracking) 기법을 활용해 모든 가능한 숫자 조합을 탐색하며 등식이 성립하는 경우를 찾습니다.
1. isValid 함수 — 대입 값의 유효성 검사
isValid(nodeList, count, word1, word2, word3)
입력: 노드 리스트, 리스트의 원소 개수, 세 개의 단어
출력: word1과 word2의 값의 합이 word3의 값과 같으면 true, 아니면 false
각 단어를 오른쪽(일의 자리)부터 왼쪽으로 훑으면서, 각 문자에 해당하는 노드의 값을 찾아 자릿수 가중치(m)를 곱해 더합니다. 세 단어 모두에 대해 이 과정을 수행한 뒤, val3 == val1 + val2 인지 확인합니다.
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
// word2, word3에 대해서도 동일한 방식으로 val2, val3를 계산
if val3 = (val1 + val2), then
return true
return false
End2. permutation 함수 — 백트래킹으로 숫자 조합 탐색
permutation(nodeList, count, n, word1, word2, word3)
입력: 노드 리스트, 리스트 항목 수, 이미 값이 배정된 문자 수, 세 개의 단어
출력: 모든 문자에 올바른 값이 배정되어 덧셈이 성립하면 true
0부터 9까지의 숫자 중 아직 사용하지 않은 숫자를 차례대로 문자에 배정하고, 재귀 호출을 통해 다음 문자로 진행합니다. 배정이 실패하면 해당 숫자를 다시 사용 가능 상태로 되돌리는 백트래킹을 수행합니다.
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
EndC++ 전체 구현 예제
다음은 위 알고리즘을 C++로 구현한 전체 코드입니다. 세 단어에 등장하는 고유 문자의 개수를 센 뒤, 10개를 초과하면 유효하지 않은 입력으로 처리하고, 그렇지 않으면 백트래킹으로 해를 탐색합니다.
#include <iostream>
#include<vector>
using namespace std;
vector<int> use(10); // 숫자가 이미 사용되었으면 1로 설정
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--) { // 첫 번째 문자열의 숫자 값 계산
char ch = s1[i];
for (j = 0; j < count; j++)
if (nodeList[j].letter == ch) // 문자를 찾으면 반복 종료
break;
val1 += m * nodeList[j].value;
m *= 10;
}
m = 1;
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;
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;
}
if (val3 == (val1 + val2)) // 합이 세 번째 문자열과 같은지 검사
return 1;
return 0;
}
bool permutation(int count, node* nodeList, int n, string s1, string s2, string s3) {
if (n == count - 1) { // 모든 문자에 값이 배정된 경우
for (int i = 0; i < 10; i++) {
if (use[i] == 0) { // 아직 사용되지 않은 숫자
nodeList[n].value = i; // 값 i 배정
if (isValid(nodeList, count, s1, s2, s3) == 1) { // 유효성 검사
cout << "Solution found: ";
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++) {
if (use[i] == 0) { // 아직 사용되지 않은 숫자
nodeList[n].value = i; // 값 i를 배정하고 사용 처리
use[i] = 1;
if (permutation(count, nodeList, n + 1, s1, s2, s3)) // 다음 문자로 진행
return true;
use[i] = 0; // 백트래킹 시 다시 사용 가능으로 복원
}
}
return false;
}
bool solvePuzzle(string s1, string s2,string s3) {
int uniqueChar = 0; // 고유 문자의 개수
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
vector<int> freq(26); // 알파벳은 총 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++)
if (freq[i] > 0) // 빈도가 0보다 큰 문자만 존재
uniqueChar++;
if (uniqueChar > 10) { // 10진법의 숫자는 10개뿐
cout << "Invalid strings";
return 0;
}
node nodeList[uniqueChar];
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";
}실행 결과
Solution found: A = 4 B = 2 E = 1 G = 0 L = 5 M = 9 S = 6
실행 결과를 확인해 보면 A=4, B=2, E=1, G=0, L=5, M=9, S=6으로 배정되었으며, 실제로 2461(BASE) + 2455(BALL) = 4916(GAMES)이 성립하는 것을 알 수 있습니다.
마무리
암호 산수 문제는 제약 충족 문제(Constraint Satisfaction Problem)의 대표적인 예로, 백트래킹의 동작 원리를 익히기에 좋은 소재입니다. 시간 복잡도는 최악의 경우 O(10!)까지 증가할 수 있지만, 가지치기(pruning)와 제약 전파 기법을 함께 사용하면 탐색 범위를 크게 줄일 수 있습니다. SEND + MORE = MONEY 같은 유명한 퍼즐에도 동일한 접근법을 적용해 볼 수 있습니다.