package DFS.迭代加深;

import java.util.Scanner;

/**
 * https://blog.csdn.net/qq_30277239/article/details/105771948
 * 如下图所示，有一个“#”形的棋盘，上面有1,2,3三种数字各8个。
 * 给定8种操作，分别为图中的A~H。
 * 这些操作会按照图中字母和箭头所指明的方向，把一条长为8的序列循环移动1个单位。
 * 例如下图最左边的“#”形棋盘执行操作A后，会变为下图中间的“#”形棋盘，再执行操作C后会变成下图最右边的“#”形棋盘。
 * 给定一个初始状态，请使用最少的操作次数，使“#”形棋盘最中间的8个格子里的数字相同。
 * 输入格式
 * 输入包含多组测试用例。
 * 每个测试用例占一行，包含24个数字，表示将初始棋盘中的每一个位置的数字，按整体从上到下，同行从左到右的顺序依次列出。
 * 输入样例中的第一个测试用例，对应上图最左边棋盘的初始状态。
 * 当输入只包含一个“0”的行时，表示输入终止。
 * 输出格式
 * 每个测试用例输出占两行。
 * 第一行包含所有移动步骤，每步移动用大写字母“A~G”中的一个表示，字母之间没有空格，如果不需要移动则输出“No moves needed”。
 * 第二行包含一个整数，表示移动完成后，中间8个格子里的数字。
 * 如果有多种方案，则输出字典序最小的解决方案。
 * 输入样例：
 * 1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3
 * 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
 * 0
 * 输出样例：
 * AC
 * 2
 * DDHH
 * 2
 * 分析：
 * 本题同样考察IDA*，每次有八种本题的操作可以选择，一旦一开始选择了错误的方向，
 * 便可能搜索到很多无用的较深分支，因此可以在迭代加深的基础上使用估价函数。
 * 分析最终状态，最终状态是中间八个数都是同一个数字，而每次操作都会使得中间八个数中的一个数出去，
 * 外面的一个数进来，也就是改变中间的一个数字。设x是中间八个数的众数，出现了f次，
 * 则至少要经过8 - f次操作才能够把中间所有的数都变成x，这就是估价函数的定义，即f = 8 - 众数出现的次数。
 * 基本框架已经解决了，下面要解决的是如果存储和操作这个井字形棋盘。首先，按照题目的输入格式给这24个数编号，得到下面的图：
 * 0     1
 * 2     3
 * 4  5  6  7  8  9  10
 * 11    12
 * 13 14 15 16 17 18 19
 * 20    21
 * 22    23
 * 然后用个二维数组g存储各种操作会操作的数字，比如A会操作0,2,6,11,15,20,22，
 * 其他的也类似，最后得到一个八行七列的数组，每次操作只需要将对应的数组第一个数搬到末尾即可。
 * 同时，用cen[8]存储中间的8个数的下标，用q存储编号0到23这24个数的具体数值。
 * 这里还有个重要的剪枝，就是每次操作前要注意不能操作上一次的反操作，比如上一次进行了A操作，
 * 再次进行F操作就将棋盘还原了，肯定不是最优的操作，因此，用op数组存下各个操作的反操作编号，
 * 每次操作前判断下即可，dfs完恢复现场时也是用此次进行操作的反操作去恢复的。
 * 代码的实现比较简单，唯一需要注意的是数组g存储的只是各个位置的元素在q中的编号，
 * 因此进行各种操作的时候，操作的是q数组里面的值，g数组里面的编号始终是不变的。
 * 按照字典序A-H暴力搜索
 * 搜索层数非常深,范围很广
 * 但答案层数不会很深
 * 估价函数:统计中间出现次数最多的数字的次数,作为估价,
 * 比如出现了cnt次,那么8-cnt就是估价排序的...
 * 优化,上一次拉A,那么下一次不能拉F,抵消了
 */
public class 回转游戏 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            q[0] = sc.nextInt();
            if (q[0] == 0) break;
            for (int i = 1; i < N; i++) {
                q[i] = sc.nextInt();
            }
            int depth = 0;
            while (!dfs(0, depth, -2)) depth++;
            if (depth == 0) System.out.println("No moves needed");
            else {
                for (int i = 0; i < depth; i++) {
                    System.out.print((char) (path[i] + 'A'));
                }
                System.out.println();
            }
            System.out.println(q[6]);
        }
    }

    static int N = 24;
    static int[][] op = {{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}};
    static int[] option = {5, 4, 7, 6, 1, 0, 3, 2};
    static int[] center = {6, 7, 8, 11, 12, 15, 16, 17};
    static int[] q = new int[N];
    static int[] path = new int[100];

    static boolean dfs(int depth, int max_depth, int last) {
        if (depth + f() > max_depth) return false;
        if (f() == 0) return true;
        for (int i = 0; i < 8; i++) {
            if (last != option[i]) {
                option(i);
                path[depth] = i;
                if (dfs(depth + 1, max_depth, i)) return true;
                option(option[i]);
            }
        }
        return false;
    }

    static int f() {
        int[] sum = {0, 0, 0, 0};
        for (int i = 0; i < 8; i++) {
            sum[q[center[i]]]++;
        }
        int s = 0;
        for (int i = 1; i <= 3; i++) {
            s = Math.max(sum[i], s);
        }
        return 8 - s;
    }

    static void option(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;
    }
}