算法

(IDA*, DFS) $O(7^k)$

本题采用 IDA* 算法，即迭代加深的 A* 算法。

估价函数：

• 统计中间8个方格中出现次数最多的数出现了多少次，记为 $k$ 次。
• 每次操作会从中间8个方格中移出一个数，再移入一个数，所以最多会减少一个不同的数。
• 因此估价函数可以设为 $8 - k$。

剪枝：

• 记录上一次的操作，本次操作避免枚举上一次的逆操作。

如何保证答案的字典序最小？

• 由于最短操作步数是一定的，因此每一步枚举时先枚举字典序小的操作即可。

时间复杂度

假设答案最少需要 $k$ 步，每次需要枚举 $7$ 种不同操作（除了上一步的逆操作），因此最坏情况下需要枚举 $7^k$ 种方案。但加入启发函数后，实际枚举到的状态数很少。

C++ 代码

/*
      0     1
      2     3
4  5  6  7  8  9  10
      11    12
13 14 15 16 17 18 19
      20    21
      22    23
*/

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 24;

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

int path[100];

int f()
{
    static int sum[4];
    memset(sum, 0, sizeof sum);
    for (int i = 0; i < 8; i ++ ) sum[q[center[i]]] ++ ;

    int s = 0;
    for (int i = 1; i <= 3; i ++ ) s = max(s, sum[i]);
    return 8 - s;
}

bool check()
{
    for (int i = 1; i < 8; i ++ )
        if (q[center[i]] != q[center[0]])
            return false;
    return true;
}

void operation(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 depth, int max_depth, int last)
{
    if (depth + f() > max_depth) return false;
    if (check()) return true;

    for (int i = 0; i < 8; i ++ )
    {
        if (opposite[i] == last) continue;
        operation(i);
        path[depth] = i;
        if (dfs(depth + 1, max_depth, i)) return true;
        operation(opposite[i]);
    }

    return false;
}

int main()
{
    while (scanf("%d", &q[0]), q[0])
    {
        for (int i = 1; i < N; i ++ ) scanf("%d", &q[i]);
        int depth = 0;
        while (!dfs(0, depth, -1))
        {
            depth ++ ;
        }
        if (!depth) printf("No moves needed");
        for (int i = 0; i < depth; i ++ ) printf("%c", 'A' + path[i]);
        printf("\n%d\n", q[6]);
    }

    return 0;
}