需要先将棋盘和对应的操作就行预处理,处理成程序便于表达的形式
#include<bits/stdc++.h>
using namespace std;
const int N = 24;
int a[N], res;
int op[8][7] = {
0, 2, 6, 11, 15, 20, 22,
1, 3, 8, 12, 17, 21, 23,
10, 9, 8, 7, 6, 5, 4,
19, 18, 17, 16, 15, 14, 13,
23, 21, 17, 12, 8, 3, 1,
22, 20, 15, 11, 6, 2, 0,
13, 14, 15, 16, 17, 18, 19,
4, 5, 6, 7, 8, 9, 10
};
int cel[8] = {6, 7, 8, 11, 12, 15, 16, 17};
int oop[8] = {5, 4, 7, 6, 1, 0, 3, 2};
string ans;
int f(){
int q[4]={0};
for(int i=0; i<8; i++) q[a[cel[i]]]++;
int mx = 0;
for(int i=1; i<4; i++) mx = max(mx, q[i]);
return 8-mx;
}
void pull(int k){
int t = a[op[k][0]];
for(int i=0; i<6; i++) a[op[k][i]] = a[op[k][i+1]];
a[op[k][6]] = t;
}
bool dfs(int u, int k, int pre, string s){
//每次操作 中间八个格子进一个数字出一个数字
//对于中间八个格子中出现最多的数字x
//最好情况下每次操作都会让x的个数+1,这种情况下剩余的预计操作数最少
//如果已经操作的操作数加上预计的最少操作数依旧超过了搜索上限
//当前的状态就是不满足要求的,需要回溯
if(u+f()>k) return false;
//预计操作数为0 意味着中间八个格子的数都一样了
if(f()==0){
ans = s;
return true;
}
for(int i=0; i<8; i++){
if(oop[i]==pre) continue;
pull(i);
if(dfs(u+1, k, i, s+(char)('A'+i))) return true;
pull(oop[i]);
}
return false;
}
int main(){
while(scanf("%d", &a[0]), a[0]){
for(int i=1; i<N; i++) scanf("%d", &a[i]);
int k = 0;
ans = "";
while(!dfs(0, k, -1, "")) k++;
if(k) cout<< ans<< endl;
else cout<< "No moves needed"<< endl;
cout<< a[6]<< endl;
}
return 0;
}