Giải bài toán Cryptarithmetic (Toán học chữ cái)

Giới thiệu

Bài toán cryptarithmetic: gán chữ số 0-9 cho các chữ cái để phép cộng đúng. Ví dụ: BASE + BALL = GAMES. Tối đa 10 chữ cái khác nhau.

Lưu ý: Không quá 10 chữ cái, nếu không không giải được.

Đầu vào và Đầu ra

Đầu vào: Ba từ: BASE + BALL = GAMES
Đầu ra: Ánh xạ chữ cái -> số:
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

Thuật toán

Định nghĩa nút (node) chứa chữ cái và giá trị tương ứng.

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

Đầu vào: Danh sách nút, số lượng, ba từ.

Đầu ra: True nếu word1 + word2 = word3.

Begin
  m := 1
  với mỗi chữ cái i từ phải sang trái của word1 làm:
    ch := word1[i]
    tìm j trong nodeList sao cho nodeList[j].letter = ch
    val1 := val1 + m * nodeList[j].value
    m := m * 10
  done
  // Tương tự cho word2, word3 tính val2, val3
  nếu val3 = val1 + val2 thì return true
  return false
End

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

Đầu vào: Danh sách nút, số lượng, số chữ cái đã gán, ba từ.

Đầu ra: True khi gán đúng cho tất cả chữ cái.

Begin
  nếu n = count - 1 thì  // đã gán hết trừ 1
    với i := 0 đến 9 làm:
      nếu chữ số i chưa dùng thì
        nodeList[n].value := i
        nếu isValid(...) thì in kết quả, return true
    done
    return false
  với i := 0 đến 9 làm:
    nếu i chưa dùng thì
      nodeList[n].value := i, đánh dấu i đã dùng
      nếu permutation(..., n+1, ...) thì return true
      bỏ đánh dấu i (backtrack)
  done
  return false
End

Ví dụ (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;
  }
  return (val3 == val1 + val2) ? 1 : 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";
}

Kết quả đầu ra

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