การแก้ปริศนาคริปโตแอริทเมติก (Cryptarithmetic Puzzles)

บทนำ

ปริศนาคริปโตแอริทเมติก (Cryptarithmetic) ใช้ตัวอักษรแทนตัวเลข 0-9 ทำให้การบวกถูกต้อง ตัวอย่าง: BASE + BALL = GAMES ตัวอักษรแต่ละตัวแทนเลข 0-9 ไม่ซ้ำกัน สูงสุด 10 ตัวอักษร

อินพุตและเอาต์พุต

Input: 3 คำ
  B A S E
+ B A L L
----------
G A M E S

Output: การจับคู่ตัวอักษร-ตัวเลข:
        B=2, A=4, S=6, E=1
        B=2, A=4, L=5
        G=0, A=4, M=9, E=1, S=6
        2461 + 2455 = 04916

อัลกอริทึม

กำหนด Node เก็บตัวอักษรและค่าที่สอดคล้อง

isValid(nodeList, count, word1, word2, word3)

Input: รายการโหนด, จำนวน, 3 คำ
Output: True ถ้าค่าของ word1 + word2 = word3

Begin
    คำนวณค่า val1 จาก word1 (อ่านจากขวาไปซ้าย คูณ 10^position)
    คำนวณค่า val2 จาก word2
    คำนวณค่า val3 จาก word3
    if val3 = val1 + val2 then return true
    return false
End

permutation(nodeList, count, n, word1, word2, word3)

Input: รายการโหนด, จำนวน, ตัวอักษรที่มอบค่าแล้ว, 3 คำ
Output: True เมื่อมอบค่าครบทุกตัวอักษรถูกต้อง

Begin
    if n ตัวอักษรมอบค่าแล้ว then
        for i = 0 ถึง 9 (เลขที่ยังไม่ได้ใช้) do
            nodeList[n].value := i
            if isValid(...) = true then แสดงคำตอบ, return true
        done
        return false
    for i = 0 ถึง 9 (เลขที่ยังไม่ได้ใช้) do
        nodeList[n].value := i
        mark i ใช้แล้ว
        if permutation(..., n+1, ...) return true
        mark i ไม่ได้ใช้ (backtrack)
    done
    return false
End

ตัวอย่างโค้ด (C++)

#include <iostream>
#include<vector>
using namespace std;

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;
    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;
            if (isValid(nodeList, count, s1, s2, s3)) {
                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; 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;
    vector<int> freq(26);
    for (char c: s1) freq[c-'A']++;
    for (char c: s2) freq[c-'A']++;
    for (char c: s3) freq[c-'A']++;
    for (int i = 0; i < 26; i++) if (freq[i] > 0) uniqueChar++;
    if (uniqueChar > 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", s2 = "BALL", s3 = "GAMES";
    if (!solvePuzzle(s1, s2, s3)) cout << "No solution";
}

ผลลัพธ์

Solution found:  A = 4 B = 2 E = 1 G = 0 L = 5 M = 9 S = 6