三羊献瑞
观察下面的加法算式：
祥 瑞 生 辉
- 三 羊 献 瑞
三 羊 生 瑞 气
(如果有对齐问题，可以参看【图1.jpg】)
其中，相同的汉字代表相同的数字，不同的汉字代表不同的数字。
请你填写“三羊献瑞”所代表的4位数字（答案唯一），不要填写任何多余内容。
答案：1085
思路一：暴力法，8层循环，从0~9中选8个数参与加法运算，筛选条件：满足abcd+efgb = efcbx
思路二：dfs求全排列，筛选条件满足：abcd+efgb = efcbx
代码一暴力枚举：
#include<iostream>
using namespace std;
/*枚举法，暴力解法*/
int main(){
// abcd + efgb
for(int a = 1;a<=9;a++){
for(int b = 0;b<=9;b++){
if(b == a){
continue;
}
for(int c = 0;c<=9;c++){
if(c==b || c==a){
continue;
}
for(int d = 0;d<=9;d++){
if(d==c || d==b || d==a){
continue;
}
for(int e = 1;e<=9;e++){
if(e==d || e==c ||e ==b || e==a){
continue;
}
for(int f=0;f<=9;f++){
if(f == e|| f==d ||f == c || f==b || f==a){
continue;
}
for(int g=0;g<=9;g++){
if(g==f ||g == e|| g== d|| g==c ||g == b|| g==a){
continue;
}
int x = a*1000+b*100+c*10+d;
int y = e*1000+f*100+g*10+b;
int z = e*10000+f*1000+c*100+b*10;
//筛选条件
for(int i=0;i<=9;i++){
if(i==a||i==b||i==c||i==d||i==e||i==f||i==g){
continue;
}
if(x+y == z+i){
cout<<y<<endl;
}
}
}
}
}
}
}
}
}
return 0;
}
代码二dfs全排列：
#include<iostream>
using namespace std;
bool visited[10];
int arr[10];
//参数k表示第k个位置 共8个位置 abcd + efgh
void dfs(int k){
if(k==9){
//判断条件
int x = 1000*arr[1] + 100*arr[2] + 10*arr[3] + arr[4];
int y = 1000*arr[5] + 100*arr[6] + 10*arr[7] + arr[2];
int z = 10000*arr[5] + 1000*arr[6] + 100*arr[3] + 10*arr[2];
for(int i = 0;i<=9;i++){
if(!visited[i]){
z = z + i;
if(z == x+y){
cout<<y<<endl;
}
z = z - i;
}
}
return;
}
if(k==1 || k==5){
for(int i=1;i<=9;i++){
if(!visited[i]){
visited[i] = true;
arr[k] = i;
dfs(k+1);
visited[i] = false;
}
}
}else{
for(int i=0;i<=9;i++){
if(!visited[i]){
visited[i] = true;
arr[k] = i;
dfs(k+1);
visited[i] = false;
}
}
}
}
int main(){
dfs(1);
}