有7个点 ， 可以给每个点编号 ， 分别为0~6 ， 故这个图共有 7！ = 5040 种状态量，这个状态量可以很灵活的实现 ， 而且要超时基本是不可能的 ， 判重方面可以适用全排列的hash ， 故内存也占极少 ， 所以适用任何一种算法。
   状态转移则可以适用
   int move[7][3] = { {1 , 5} , {0 , 2 , 6} , {1 , 3} , {2 , 4} , {3 , 5 , 6} , {0 , 4} , {1 , 4} };
   若move[j] 则表示 i点和j点可互换 ， i 点为这个游戏的空点。
   开多一个数组来存可以移动个数
   int dir[7] = {2 , 3 , 2 , 2 , 3 , 2 , 2};

#include <iostream> 
using namespace std; 

const int N = 5041; 
const int SIZE = 1000000; 

int mat[7] , fac[7] , f[N]; // fac为阶乘 ， f记录父节点 ， step数组用于记录交换对象 
char op[7] , step[N]; 
bool hash[N]; 
int dir[7] = {2 , 3 , 2 , 2 , 3 , 2 , 2}; 
int move[7][3] = { {1 , 5} , {0 , 2 , 6} , {1 , 3} , {2 , 4} , {3 , 5 , 6} , {0 , 4} , {1 , 4} }; 
struct node { 
       int state[7]; 
       int step , pos , key; //状态 ， 步数 ， 关键点 ， 关键字 
} Que[SIZE]; 

int get_key(int s[]) {     //全排列 hash ， 得到关键字 
       int ret = 0 , count; 
       for(int i=1; i < 7; i++) { 
           count = 0; 
           for(int j=0; j < i; j++) 
               count += s[j] > s[i] ? 1 : 0; 
           ret += count * fac[i]; 
       } 
       return ret; 
} 

void search(int x) { //回溯 
       if(f[x] == -1) return ; 
       search(f[x]); 
       printf("%c" , step[x]); 
} 

void solve() { 
       int key = get_key(mat); 
       hash[key] = 1; 
       if(key == 0) { 
               printf("0\n"); 
               return ; 
       } 
       f[key] = -1; 
       node T; 
       for(int i=0; i < 7; i++) T.state[i] = mat[i]; 
       T.pos = 6 , T.step = 0 , T.key = key; 
       int head = 0 , tail = 0; 
       Que[tail ++] = T; //T乃头结点 
       while(head != tail) { 
               node x1 , x2; 
               x1 = Que[head];  //循环队列， 个人习惯。。 
               head = (head + 1) % SIZE; 
               int num = dir[x1.pos]; 
               for(int i=0; i < 7; i++) 
                       x2.state[i] = x1.state[i] ; 
               int a = x1.pos; 
               int cnt; 
               for(int i=0; i < num; i++) { 
                       cnt = x2.state[move[a][i]]; 
                       swap(x2.state[a] , x2.state[move[a][i]]); 
                       x2.pos = move[a][i]; 
                       x2.step = x1.step + 1; 
                       key = get_key(x2.state); 
                       if(key == 0) { 
                               printf("%d " , x2.step); 
                               f[key] = x1.key; 
                               step[key] = cnt + 'A'; 
                               search(0); 
                               puts(""); 
                               return ; 
                       } 
                       if(!hash[key]) { 
                               hash[key] = 1; 
                               x2.key = key; 
                               f[x2.key] = x1.key; 
                               step[x2.key] = cnt + 'A'; 
                               Que[tail] = x2; 
                               tail = (tail + 1) % SIZE; 
                       } 
                       swap(x2.state[a] , x2.state[move[a][i]]); 
               } 
       } 
       printf("NO SOLUTION\n"); 
} 

void init() { //初始化 
       fac[1] = 1; 
       for(int i=2; i < 7; i++) 
               fac[i] = fac[i - 1] * i; 
       memset(hash , 0 , sizeof(hash)); 
       memset(f , -1 , sizeof f); 
} 

int main() { 
       //freopen("in.txt" , "r" , stdin); 
       int p , t; 
       scanf("%d" , &p); 
       while(p --) { 
               scanf("%d %s" , &t , op); 
               printf("%d " , t); 
               for(int i=0; i < 6; i++) 
                       mat[i] = op[i] - 'A'; 
               mat[6] = 6; 
               init(); 
               solve(); 
       } 
       return 0; 
}