/*
在这题中,不断的移动可能导致某些子树的深度很深,但是根据直觉,答案应该在比较浅的地方,所以可以用迭代加深来做,
同时可以加入一个估值函数,于是就变成IDA*。
估值函数:每次拉动一次,只会改变区域内的一个值,所以先找出这个区域内个数最多的数字,记个数为cnt,那么估值函数就是8-cnt
做法:
整个框架是IDA*,从0开始枚举层数,然后在每一层搜索时计算估价函数,如果当前层加上估价函数大于目前最优解则return;
否则遍历8个操作,有一个技巧就是给8个操作编号。
A(0) B(1)
0 1
2 3
H(7) 4 5 6 7 8 9 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 <iostream>
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 opp[8] = {5 , 4 , 7 , 6 , 1 , 0 , 3 , 2};//操作的逆操作
int center[8] = {6 , 7 , 8 , 11 , 12 , 15 , 16 , 17};//中间8个
int q[N];
int path[N];
int f()
{
int sum[4] = {0};
for(int i = 0 ; i < 8 ; i++) sum[q[center[i]]]++;
int res = 0;
for(int i = 1 ; i <= 3 ; i++) res = max(res , sum[i]);
return 8 - res;
}
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;
}
bool dfs(int u , int max_path , int last)
{
if(u + f() > max_path) return false;
if(!f()) return true;
for(int i = 0 ; i < 8 ; i++)
{
if(opp[i] == last) continue;
operate(i);
path[u] = i;
if(dfs(u + 1 , max_path , i)) return true;
operate(opp[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++) printf("%c" , path[i] + 'A');
}
cout << endl << q[6] << endl;
}
return 0;
}