7 min readDec 31, 2019
Backtracking
The most classical example should be 8 queens.
Here I’d like to talk about the latest leetcode question.
1307. Verbal Arithmetic Puzzle
https://leetcode.com/problems/verbal-arithmetic-puzzle/
This code is from cui aoxiang. It is slow with runtime of 1816 ms. Sometimes, we will get TLE for this solution.
bool used[10];
int a[10], A[26];class Solution {
public:
vector<string> words;
bool search(int pos, int idx, int cur) {
//cout << pos << " " << idx << " " << sum << endl;
if (pos == words.size()) {
int sum = 0;
for (int i = 0; i < pos - 1; ++i) sum += a[i];
sum -= a[pos - 1];
return sum == 0;
}
if (idx == words[pos].size()) {
a[pos] = cur;
return search(pos + 1, 0, 0);
}
int k = words[pos][idx] - 'A';
if (A[k] >= 0) {
return search(pos, idx + 1, cur * 10 + A[k]);
} else {
for (int j = 0; j < 10; ++j) {
if (idx == 0 && j == 0) continue;
if (used[j]) continue;
A[k] = j;
used[j] = true;
if (search(pos, idx + 1, cur * 10 + A[k])) return true;
used[j] = false;
A[k] = -1;
}
}
return false;
}
bool isSolvable(vector<string>& words, string result) {
this->words = words;
this->words.push_back(result);
memset(used, 0, sizeof(used));
memset(A, 255, sizeof(A));
bool ret = search(0, 0, 0);
return ret;
}
};
Python version of the above code is below. Of course, it got TLE.
9 / 26 test cases passed.
used = [False]*10
a =[0]*10
A = [-1]*26
class Solution:
def isSolvable(self, words: List[str], result: str) -> bool:
words.append(result)
N = len(words)
def search(pos, idx, cur):
if pos==len(words):
S = sum(a[i] for i in range(N-1))
return S-a[N-1]==0
if idx==len(words[pos]):
a[pos] = cur
return search(pos + 1, 0, 0)
k = ord(words[pos][idx]) - ord('A')
if A[k]>=0:
return search(pos, idx+1, cur*10+A[k])
else:
for j in range(10):
#leading zero
if idx==0 and j==0:continue
if used[j]:continue
used[j], A[k]= True, j
if search(pos, idx + 1, cur * 10 + A[k]): return True
used[j], A[k] = False, -1
return False
return search(0, 0, 0)This is one submission from the leetcode. It is very fast only 12ms. It is from
class Solution
{
public:
int c2i[26];//map the char (A~Z) to integer (0~9)
int i2c[10];//map the integer(0~9) to char (A~Z)
vector<string> w; //global variable for words (just for convenience)
string r; //global variable for result (just for convenience)
bool dfs(int index,int l,int s)
{
//index is the current word index in words
//(eg. words[index], for index from 0~words.length()-1)
//l is the current digit for the word and result
//(eg. words[index][l], result[l] for l from 0~result.length()-1 or l from 0~words[index].length()-1)
//s is the accumulated sum for those words[index] at digit l; so s%10 is the final result of current digit, s/10 is the carry
if(l==r.length()) //if we reach the end of result
return s==0; //we have to check if there is no carry
if(index==w.size()) //if we traverse the digit for all the words, we will go to next digit
{
if(c2i[r[l]-'A']!=-1) //if the character in the result at digit l has been used
{
if(c2i[r[l]-'A']==s%10) //we check if the digit matches to s%10 (the accumulated sum of current digit mod by 10)
return dfs(0,l+1,s/10);//we start from words[0] of next digit, and pass on the carry value
}
else if(i2c[s%10]==-1) //we check if the digit for the accumulated sum has not been used
{
if(l==(int)r.length()-1&&s%10==0) //the leading digit must not be 0
return false;
c2i[r[l]-'A']=s%10; //we map the character in result to the accumulated sum of current digit
i2c[s%10]=r[l]-'A'; //we map the accumulated sum of current digit to the character in result
bool temp=dfs(0,l+1,s/10); //we store the result here for backtracking instead of directly return the result (because we have to undo the previous 2 operations), note that we start from words[0] at next digit, and pass on the carry (s/10)
c2i[r[l]-'A']=-1; //we undo the operation (part of backtracking)
i2c[s%10]=-1; //we undo the operation (part of backtracking)
return temp; //return the result
}
return false; //if we didn't go to above "if" or "else if", then the result must be false
}
if(l>=w[index].length()) //if the current digit is larger than the current length of words[index], we just skip the word
return dfs(index+1,l,s); //go to word[index+1] at the same digit, the sum s will not be updated since we skip the word
if(c2i[w[index][l]-'A']!=-1) //if the character has already been used
return dfs(index+1,l,s+c2i[w[index][l]-'A']); //we will add the digit corresponding to the character to result s, and go to word[index+1]
for(int i=0;i<10;i++) //if the character has not been used, and the current digit does not reach the end of the word
{
if(i2c[i]!=-1) //if the digit has been used, we can't use it again
continue;
if(i==0&&l==w[index].length()-1) //the leading digit of word[index] must not be 0
continue;
i2c[i]=w[index][l]-'A'; //we use the digit i, and map the digit to the character
c2i[w[index][l]-'A']=i; //we use the digit i, and map the character to the digit
bool temp=dfs(index+1,l,s+i); //we store the result here for backtracking instead of directly return the result (because we have to undo the previous 2 operations)
i2c[i]=-1; //we undo the operation (part of backtracking)
c2i[w[index][l]-'A']=-1; //we undo the operation (part of backtracking), so we can try the next possibility
if(temp) //if any of the digit leads to correct output, then return true
return true;
}
return false; //if all of above fails, return false
}
bool isSolvable(vector<string>& words, string result)
{
for(int i=0;i<words.size();i++)
if((int)words[i].length()>(int)result.length()) //the length of all words must not be longer than the length of result
return false;
memset(c2i,-1,sizeof(c2i)); //set all to -1, which means the character is not used yet
memset(i2c,-1,sizeof(i2c)); //set all to -1, which means the digit is not used yet
w=words; //global variable for words
r=result; //global varialbe for result
for(int i=0;i<words.size();i++) //reverse all the words, so that we can calculate the current digit and pass on the carry more intuitionally
reverse(w[i].begin(),w[i].end());
reverse(r.begin(),r.end()); //reverse all result, so that we can calculate the current digit and pass on the carry more intuitionally
return dfs(0,0,0); //we start from words[0] at digit 0 (the least significant digit in this case), and the initial sum is 0
}
};class Solution {
public:
int c2i[26];//把每個字母映射到數字 (確保每個字母只會映射到同1個數字)
int i2c[10];//把每個數字映射到字母 (確保數字不會被重複使用)
vector<string> w; //words的全域變數 (純粹為了方便)
string r; //result的全域變數 (純粹為了方便)
bool dfs(int index,int l,int s) {
//遍歷順序是把當前的位數中的所有單字處理完後，才會進展到下一個位數，直到所有位數被處理完為止
//index代表當前到了words中的哪1個單字
//(eg. words[index], index從0~words.length()-1)
//l代表當前走到了words中單字或result的哪1個位數(因為我們要統計完所有當前位數才能進位)
//(eg. words[index][l], result[l], l從0~result.length()-1或是l從0~words[index].length()-1)
//s是所有單字在當前的位數的總合;s%10是當前位數所有單字合的個位數, s/10就是我們傳遞的進位值
if(l==r.length()) //如果已經遍歷完所有的位數，就抵達終止條件
return s==0; //我們要確保當前的s進位值已經是0
if(index==w.size()) //如果對於所有單字words[0]~words[end]，都已經遍歷完當前位數l，就遍歷下個位數
{
if(c2i[r[l]-'A']!=-1) //如果result當中，當前位數對應的字母已經被分配過數字
{
if(c2i[r[l]-'A']==s%10) //確認此字母映射到的數字是否為s的個位數 (s是所有的單字在當前位數的總合)
return dfs(0,l+1,s/10);//因為所有單字的當前位數都遍歷完了，所以我們從下個位數的words[0]開始遍歷，並且傳遞進位值(s/10)
}
else if(i2c[s%10]==-1) //如果字母還沒映射過，我們要確認我們該使用的數字(s%10)是否還沒被用過
{
if(l==(int)r.length()-1&&s%10==0) //最大位數不能為0
return false;
c2i[r[l]-'A']=s%10; //把所有單字的當前位數的總和之個位數分配給result的當前位數對應的字母
i2c[s%10]=r[l]-'A'; //確保所有單字當前位數的總和對應的個位數字已經被分配給字母r[l]，避免重複分配
bool temp=dfs(0,l+1,s/10); //我們先把backtracking的結果存下來，因為此後還要把前面2個操作的結果復原, 而傳遞的index=0代表對於下個位數從words[0]開始遍歷, 把位數l增加1以前進到下個位數,傳遞進位值(s/10)
c2i[r[l]-'A']=-1; //把前面的操作復原，這是回溯法backtracking的一部份
i2c[s%10]=-1; //把前面的操作復原，這是回溯法backtracking的一部份
return temp; //回傳結果
}
return false; //如果沒辦法符合以上的if或else if中的條件，代表此路不通，沒辦法形成正確等式
}
if(l>=w[index].length()) //如果當前處理的位數已經大於當前單字的長度，就直接跳過此單字
return dfs(index+1,l,s); //直接跳過words[index]，從words[index+1]繼續遍歷當前的位數，s不會被改變，因為此單字已經被跳過了if(c2i[w[index][l]-'A']!=-1) //如果此字母已經分配過數字了
return dfs(index+1,l,s+c2i[w[index][l]-'A']); //把此字母對應的數字加到s，並且從下個單字words[index+1]繼續遍歷
for(int i=0;i<10;i++) //如果此字母還沒被分配過任何數字
{
if(i2c[i]!=-1) //如果此數字已經被用過，就不能重複使用
continue;
if(i==0&&l==w[index].length()-1) //word[index]的首位數不能是0
continue;
i2c[i]=w[index][l]-'A'; //我們分配數字i給了字母w[index][l]，因此數字i不能再次被使用
c2i[w[index][l]-'A']=i; //我們把字母w[index][l]映射的值設成數字i，因此該字母不能再被映射成其他數字
bool temp=dfs(index+1,l,s+i); //我們先把backtracking的結果存下來，因為此後還要把前面2個操作的結果復原。並且從下個單字words[index+1]開始遍歷此位數(此位數被遍歷完才會再進位)，並且把s加上此操作所分配的數字
i2c[i]=-1; //把前面的操作復原，這是回溯法backtracking的一部份
c2i[w[index][l]-'A']=-1; //把前面的操作復原，這是回溯法backtracking的一部份(讓我們能開始嘗試下一種可能)
if(temp) //如果任何一種單字分配的方式能形成正確等式，就回傳true
return true;
}
return false; //如果所有的數字分配都嘗試過也不能成功，就回傳false
}
bool isSolvable(vector<string>& words, string result) {
for(int i=0;i<words.size();i++)
if((int)words[i].length()>(int)result.length()) //每個單字的長度都不能長於result的長度
return false;memset(c2i,-1,sizeof(c2i)); //把所有的26個字母的映射初始成-1，代表我們還沒有為此字母分配過數字
memset(i2c,-1,sizeof(i2c)); //把所有10的數字的映射初始成-1,代表我們還沒有分配過此數字給任何字母
w=words; //words的全域變數是w
r=result; //result的全域變數是r
for(int i=0;i<words.size();i++) //把所有的單字反轉，以便我們能從個位、十位、百位遍歷到最大位數
reverse(w[i].begin(),w[i].end());
reverse(r.begin(),r.end()); //把結果對應的字串反轉，以便我們能從個位、十位、百位遍歷到最大位數
return dfs(0,0,0); //我們從words[0]的最小位數(個位數)開始遍歷，個位數的總和初始為0
}
};
Check column by column will do the trick
class Solution:
def isSolvable(self, words: List[str], result: str) -> bool:
def solve(i, j, carry):
if j == len(words): # The current column assignment is over, so check for validity
csum = carry
for k in range(len(words)):
csum += 0 if i >= len(words[k]) else assign[words[k][i]]
if i >= len(result): return False # We have come to column i, but the result itself is not long enough.
if result[i] in assign:
return csum % 10 == assign[result[i]] and solve(i+1, 0, csum // 10) # i th char of result is already assigned, so check if its valid and go to next column i+1 and start from word 0
else:
# If the current digit can't be assigned to ith char of result or if its 0 and we are looking at first char of a word: then return False
if (csum % 10) in assign.values() or (csum % 10 == 0 and i == len(result) - 1): return False
assign[result[i]] = csum % 10
ret = solve(i+1, 0, csum // 10)
del assign[result[i]]
return ret
if i == len(result):
return i >= max(len(w) for w in words) and carry == 0
# Handle length of word less than the column we are looking at OR the ith column char of the jth word is already assigned previously
if i >= len(words[j]) or words[j][i] in assign: return solve(i, j+1, carry)
for val in range(10):
if val == 0 and i == len(words[j]) - 1: continue # Handle not to assign 0 for first letter of a word
if val not in assign.values():
assign[words[j][i]] = val
ret = solve(i, j+1, carry)
if ret: return True
del assign[words[j][i]]
return False
result = result[::-1]
words = [w[::-1] for w in words]
assign = dict()
return solve(0, 0, 0)My own python code, with some pruning and got
19 / 26 test cases passed.
class Solution:
def isSolvable(self, words: List[str], result: str) -> bool:
left,right, t = collections.defaultdict(int),collections.defaultdict(int),collections.defaultdict(int)
for word in words:
N= len(word)
for i, w in enumerate(word):
left[w] += 10**(N-i-1)
for i,w in enumerate(result):
N = len(result)
right[w] += 10**(N-i-1)
for key in (set(left.keys())|set(right.keys())):
this_res = left[key]-right[key]
if this_res !=0:
t[key] = this_res
values = list(t.values())
values.sort(key=abs)
vs, L = values[:-1], values[-1]
neg, pos = [], []
for v in values:
if v>0:pos.append(v)
else:neg.append(-v)
if not neg or not pos:return False
neg.sort()
if len(pos)<len(neg):
pos, neg = neg[:], pos[:]
for a in itertools.permutations(range(10), len(pos)):
a = list(a)
S = sum(c*d for c,d in zip(pos, a))
b = sorted(list(set(range(10)) - set(a)))
min_, max_ = sum(c1*c2 for c1, c2 in zip(neg, b[:len(neg)][::-1])), sum(c1*c2 for c1, c2 in zip(neg, b[-len(neg):]))
if min_>S or max_<S: continue
if len(neg)==1:
if 0<=neg[0]<=9 and neg[0] in b:return True
else:continue
for c in itertools.permutations(b, len(neg)-1):
c = list(c)
S1 = sum(e*f for e,f in zip(neg[:-1], c))
rest = S-S1
if rest==0:
if 0 in b and 0 not in c:return True
continue
if rest%neg[-1]!=0:continue
this_res= rest//neg[-1]
if 0<=this_res<=9 and this_res in b and this_res not in c:return True
return False
