主要是设计乐观估计函数来减枝
假设中心区域有6个2，2个3，那肯定是消掉3最好，毕竟就两个。
那么理想情况下，旋转一次就能把一个3变成2，那么最少操作2次。
我们用h()来计算最少还要操作几次，其原理是假设中心区域都放1或2或3，返回至少操作的次数中最小的数
maxd是假设最多能操作的数;
d是已经操作的数;
那么就可以得出乐观估计函数 h()+d>maxd
其含义为 ： 若 至少还要操作次数 加上 已经操作的次数 大于 最多总共操作的次数就退出 。
其次就是节点的处理了，编个号数组保存一下就方便多了。
给节点编号
A-0 B-1
00 01
02 03
H-7 04 05 06 07 08 09 10 C-2
11 12
G-6 13 14 15 16 17 18 19 D-3
20 21
22 23
F-5 E-4
#include<cstdio>
#include<algorithm>
using namespace std;
/*A-0 B-100 0102 03
H-7 04 05 06 07 08 09 10 C-211 12
G-6 13 14 15 16 17 18 19 D-320 2122 23F-5 E-4
*/
int line[8][7]={{0,2,6,11,15,20,22}, //A{1,3,8,12,17,21,23}, //B{10,9,8,7,6,5,4}, //C{19,18,17,16,15,14,13} //D
};
#define min3(x,y,z) min(min(x,y),z)
const int rev[]={5,4,7,6,1,0,3,2}; //保存对面的编号，如A-0条对面是F-5条，见上图
const int center[]={6,7,8,12,17,16,15,11}; //中心区域点的编号
const int maxn=1000+5;int a[24];
char ans[maxn];bool is_solved() //观察是否完成任务
{for(int i=0;i<8;i++)if(a[center[i]]!=a[center[0]]) return false;return true;
}
inline int diff(int n) //中心区域有多少与n不同的数 ;
{int cnt=0;for(int i=0;i<8;i++)if(a[center[i]]!=n) cnt++;return cnt;
}
inline int h()
{return min3(diff(1),diff(2),diff(3)); //如果中心区域要填满1,2,3,那么最少的不同数，即理想的操作数;
}
void move(int k)
{int t=a[line[k][0]];for(int i=0;i<7-1;i++) a[line[k][i]]= a[line[k][i+1]];a[line[k][6]]=t;
}
bool dfs(int d,int maxd)
{if(d==maxd){if(is_solved()) {ans[d]='\0';printf("%s\n",ans);return true;}}else{if(h()+d>maxd) return false; for(int i=0;i<8;i++){ans[d]='A'+i; //打印答案，因为是从A开始操作所以肯定是最小字典序 move(i); //旋转第i条条子 if(dfs(d+1,maxd)) return true;move(rev[i]); //旋转第i条条子的反方向，即rev[i]条，恢复原位； }}return false;
}void solve()
{for(int maxd=1;;maxd++)if(dfs(0,maxd)) return;
}
int main()
{for(int i=4;i<8;i++) //填充E,F,G,H line，因为是有规律的就不人工初始化了; for(int j=0;j<7;j++)line[i][j]=line[rev[i]][6-j];while(scanf("%d",&a[0])==1&&a[0]){for(int i=1;i<24;i++) scanf("%d",&a[i]);if(is_solved()) printf("No moves needed\n");else solve();printf("%d\n",a[6]);}return 0;
}