莫欺少年穷，修魔之旅在这开始—>算法提高课题解

IDA*+迭代加深

思路：

1. 估价函数：中间八个格子最少还要移几次
2. 枚举每一层操作，该操作不能与上一层操作对立
3. 每次要记录该层是什么操作
4. 回溯的时候不要忘了恢复现场

#include<bits/stdc++.h>

using namespace std;

const int N = 24;

//每种操作所牵动的格子序号
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 opposite[8]={5,4,7,6,1,0,3,2};

//中间八个格子的序号
int center[8]={6,7,8,11,12,15,16,17};

int q[N];
int path[100];

// 8 - 当前中间八个格子一样数字最多的个数
int f()
{
    static int sum[4];

    memset(sum,0,sizeof sum);

    for(int i=0;i<8;i++) sum[q[center[i]]]++;

    return 8-max(sum[1],max(sum[2],sum[3]));
}

//实行序号为 x 的操作
void operate(int x)
{
    int t=q[op[x][0]];
    for(int i=0;i<6;i++) q[op[x][i]]=q[op[x][i+1]];
    q[op[x][6]]=t;
}

//第 u 层操作，最大操作数为 depth，上一步操作的序号
bool dfs(int u,int depth,int last)
{
    //目前操作层+估价操作层
    if(u+f()>depth) return false;

    //达成要求
    if(!f()) return true;

    //枚举八种操作
    for(int i=0;i<8;i++)

        //该操作的对立面不能是上一步操作
        if(opposite[i]!=last)
        {
            //记录这一层的操作
            path[u]=i;

            //执行该操作
            operate(i);

            //执行下一层
            if(dfs(u+1,depth,i)) return true;

            //恢复现场
            operate(opposite[i]);
        }

    return false;
}

int main()
{
    while(cin>>q[0],q[0])
    {
        for(int i=1;i<N;i++) cin>>q[i];

        int depth=0;
        while(!dfs(0,depth,-1)) depth++;

        if(!depth) cout<<"No moves needed";
        else for(int i=0;i<depth;i++) cout<<char(path[i]+'A');

        cout<<'\n'<<q[6]<<endl;
    }

    return 0;
}