求解数独谜题

什么是算术字谜？

算术字谜，也称为密码，是一种数学谜题，我们将数字分配给字母或符号。最终目标是找到每个字母的唯一数字分配，以便给定的数学运算成立。在这个谜题中，执行加法运算的等式是最常用的。但是，它也涉及其他算术运算，例如减法、乘法等。

算术字谜的规则如下：

我们只能使用 0 到 9 的数字来表示谜题中唯一的字母。
在整个等式中，不能将相同的数字分配给不同的字母。
用数字替换字母后形成的等式在数学上应该是正确的。

输入输出场景

假设给定的等式是：

Input:
             B A S E
             B A L L
           ----------
           G A M E S

在上式中，单词“BASE”和“BALL”相加得到“GAMES”。算法将把给定单词的每个字母与 0 到 9 的唯一数字相关联。对于上述输入，输出应为：

使用回溯法求解算术字谜

求解算术字谜的朴素方法是从左边的每个操作数中取一个字母，然后一个接一个地分配数字 0 到 9。分配数字后，检查算术表达式的有效性。但是，这种方法对于较大的操作数效率低下。

要使用回溯法求解算术字谜，请按照以下步骤操作：

首先，识别给定算术表达式中的所有唯一字符。
接下来，尝试将数字分配给字母。如果发现重复，则回溯并取消分配。这样将生成每个字母的所有可能的数字组合。
现在，用数字替换字母，并检查表达式是否正确。

示例

在下面的示例中，我们将实际演示如何求解算术字谜。

C C++ Java Python

#include <stdio.h>
#include <string.h>
//set 1, when one character is assigned previously
int use[10] = {0};
// structure
struct node {
   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;
   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 
         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
         if (permutation(count, nodeList, n + 1, s1, s2, s3) == 1)    
            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}; 
   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
      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;
}

#include <iostream>
#include <vector>
using namespace std;
//set 1, when one character is assigned previously
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;
   //find number for first string
   for (i = s1.length() - 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 = 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;
   //find number for third string
   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;
   }
   //check whether the sum is same as 3rd string or not
   if (val3 == (val1 + val2))    
      return 1;
   return 0;
}
bool permutation(int count, node* nodeList, int n, string s1, string s2, string 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 
         if (use[i] == 0) {   
             //assign value i 
            nodeList[n].value = i; 
            //check validation
            if (isValid(nodeList, count, s1, s2, s3) == 1) { 
               cout << "Solution found: ";
               //print code, which are assigned
               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++) {
      // 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
         if (permutation(count, nodeList, n + 1, s1, s2, s3))    
            return true;
         //when backtracks, make available again    
         use[i] = 0; 
      }
   }
   return false;
}
bool solvePuzzle(string s1, string s2,string s3) {
   //Number of unique characters    
   int uniqueChar = 0; 
   int len1 = s1.length();
   int len2 = s2.length();
   int len3 = s3.length();
   //There are 26 different characters
   vector<int> freq(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++)
      //whose frequency is > 0, they are present
      if (freq[i] > 0)     
         uniqueChar++;
   //as there are 10 digits in decimal system
   if (uniqueChar > 10) { 
      cout << "Invalid strings";
      return 0;
   }
   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() {
   string s1 = "BASE";
   string s2 = "BALL";
   string s3 = "GAMES";
   if (solvePuzzle(s1, s2, s3) == false)
      cout << "No solution";
}

public class Main {
   // Set 1 when one character is assigned previously    
   int[] use = new int[10]; 
   class Node {
      char letter;
      int value;
   }
   public int isValid(Node[] nodeList, int count, String s1, String s2, String s3) {
      int val1 = 0, val2 = 0, val3 = 0;
      int m = 1;
      int j, i;
      //find number for first string
      for (i = s1.length() - 1; i >= 0; i--) {
         char ch = s1.charAt(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 = s2.length() - 1; i >= 0; i--) { 
         char ch = s2.charAt(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 = s3.length() - 1; i >= 0; i--) { 
         char ch = s3.charAt(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;
      }
      return 0;
   }
   public int permutation(int count, Node[] nodeList, int n, String s1, String s2, String s3) {
      //when values are assign 
      if (n == count - 1) { 
         // for those numbers, which are not used 
         for (int i = 0; i < 10; i++) { 
            if (use[i] == 0) {
               //assign value i    
               nodeList[n].value = i; 
               if (isValid(nodeList, count, s1, s2, s3) == 1) {
                  System.out.print("Solution found:");
                  //print code, which are assigned
                  for (int j = 0; j < count; j++) { 
                     System.out.print(" " + nodeList[j].letter + " = " + nodeList[j].value);
                  }
                  return 1;
               }
            }
         }
         return 0;
      }
      // for those numbers, which are not used
      for (int i = 0; i < 10; i++) { 
         if (use[i] == 0) {
            //assign value i and mark as not available for future use
            nodeList[n].value = i;
            use[i] = 1;
            if (permutation(count, nodeList, n + 1, s1, s2, s3) == 1) {
               //go for next characters
               return 1; 
            }
            //when backtracks, make available again
            use[i] = 0; 
         }
      }
      return 0;
   }
   public int solvePuzzle(String s1, String s2, String s3) {
      //Number of unique characters
      int uniqueChar = 0; 
      int len1 = s1.length();
      int len2 = s2.length();
      int len3 = s3.length();
      // There are 26 different characters
      int[] freq = new int[26]; 
      for (int i = 0; i < len1; i++) {
         freq[s1.charAt(i) - 'A']++;
      }
      for (int i = 0; i < len2; i++) {
         freq[s2.charAt(i) - 'A']++;
      }
      for (int i = 0; i < len3; i++) {
         freq[s3.charAt(i) - 'A']++;
      }
      //whose frequency is > 0, they are present
      for (int i = 0; i < 26; i++) { 
         if (freq[i] > 0) {
             uniqueChar++;
         }
      }
      //as there are 10 digits in decimal system
      if (uniqueChar > 10) { 
         System.out.println("Invalid strings");
         return 0;
      }
      Node[] nodeList = new Node[uniqueChar];
      int j = 0;
      for (int i = 0; i < 26; i++) {
         //assign all characters found in three strings 
         if (freq[i] > 0) { 
             nodeList[j] = new Node();
             nodeList[j].letter = (char) (i + 'A');
             j++;
         }
      }
      return permutation(uniqueChar, nodeList, 0, s1, s2, s3);
   }
   public static void main(String[] args) {
      Main main = new Main();
      String s1 = "BASE";
      String s2 = "BALL";
      String s3 = "GAMES";
      if (main.solvePuzzle(s1, s2, s3) == 0) {
         System.out.println("No solution");
      }
   }
}

class Main:
    #Set 1 when one character is assigned previously
    use = [0] * 10  
    class Node:
        def __init__(self):
            self.letter = ''
            self.value = 0

    def isValid(self, nodeList, count, s1, s2, s3):
        val1 = 0
        val2 = 0
        val3 = 0
        m = 1
        j = 0
        i = 0
        #find number for first string
        for i in range(len(s1) - 1, -1, -1):  
            ch = s1[i]
            for j in range(count):
                #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 the second string
        for i in range(len(s2) - 1, -1, -1):  
            ch = s2[i]
            for j in range(count):
                if nodeList[j].letter == ch:
                    break
            val2 += m * nodeList[j].value
            m *= 10

        m = 1
        #find number for the third string
        for i in range(len(s3) - 1, -1, -1):  
            ch = s3[i]
            for j in range(count):
                if nodeList[j].letter == ch:
                    break
            val3 += m * nodeList[j].value
            m *= 10
        #check whether the sum is the same as the 3rd string or not
        if val3 == (val1 + val2):  
            return 1
        return 0

    def permutation(self, count, nodeList, n, s1, s2, s3):
        #when values are assigned
        if n == count - 1:  
            for i in range(10):
                #for those numbers, which are not used
                if self.use[i] == 0:  
                    #assign value i
                    nodeList[n].value = i  
                    if self.isValid(nodeList, count, s1, s2, s3) == 1:
                        print("Solution found:", end='')
                         #print code, which is assigned
                        for j in range(count): 
                            print(f" {nodeList[j].letter} = {nodeList[j].value}", end='')
                        return 1
            return 0

        for i in range(10):
            #for those numbers, which are not used
            if self.use[i] == 0:  
                #assign value i and mark as not available for future use
                nodeList[n].value = i  
                self.use[i] = 1
                if self.permutation(count, nodeList, n + 1, s1, s2, s3) == 1:  
                    #go for the next characters
                    return 1
                 #when backtracking, make available again    
                self.use[i] = 0 
        return 0

    def solvePuzzle(self, s1, s2, s3):
        #Number of unique characters
        uniqueChar = 0  
        len1 = len(s1)
        len2 = len(s2)
        len3 = len(s3)
        #There are 26 different characters
        freq = [0] * 26  

        for i in range(len1):
            freq[ord(s1[i]) - ord('A')] += 1

        for i in range(len2):
            freq[ord(s2[i]) - ord('A')] += 1

        for i in range(len3):
            freq[ord(s3[i]) - ord('A')] += 1

        for i in range(26):
            #whose frequency is > 0, they are present
            if freq[i] > 0:  
                uniqueChar += 1
        #as there are 10 digits in the decimal system
        if uniqueChar > 10:  
            print("Invalid strings")
            return 0

        nodeList = [self.Node() for _ in range(uniqueChar)]
        j = 0

        for i in range(26):
            #assign all characters found in three strings
            if freq[i] > 0:  
                nodeList[j].letter = chr(i + ord('A'))
                j += 1

        return self.permutation(uniqueChar, nodeList, 0, s1, s2, s3)

if __name__ == "__main__":
    main = Main()
    s1 = "BASE"
    s2 = "BALL"
    s3 = "GAMES"
    if main.solvePuzzle(s1, s2, s3) == 0:
        print("No solution")

输出

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

打印页面