题目链接

  本题是2004年icpc亚洲区域赛上海赛区的H题

题意

  如下图所示形状的棋盘上分别有8个1、2、3，要往A～H方向旋转棋盘，使中间8个方格数字相同。图（a）进行A操作后变为图（b），再进行C操作后变为图（c），这正是一个目标状态（因为中间8个方格数字相同）。要求旋转次数最少。如果有多解，操作序列的字典序应尽量小。

输入格式

  输入包括不超过 30 组测试数据。每个测试数据只包括一行，包含 24 个整数，每相邻两个整数之间用 1 个空格隔开，表示这个 “#” 形棋盘的初始状态。（这些整数的排列顺序是从上至下，同一行的从左至右。）每两组测试数据之间没有换行符。输入文件以一行 0 结束。

输出格式

  对于每组测试数据，输出两行。第一行用字符 A∼H 输出操作的方法，每两个操作字符之间没有空格分开，如果不需要任何步数，输出 No moves needed。第二行输出最终状态中最中间的 8 个格子里的数字。如果有多组解，输出操作次数最少的一组解；如果仍有多组解，输出字典序最小的一组。任意相邻两组测试数据的输出之间不需输出换行符。

分析

  《算法竞赛入门经典》题解：

  本题是一个典型的状态空间搜索问题，可惜如果直接套用八数码问题的框架会超时。为什么？学完第10章的组合计数部分后会知道：8个1、8个2、8个3的全排列个数为24!/(8!*8!*8!)=9465511770。换句话说，最坏情况下最多要处理这么多结点！

  解决方法很巧妙：本题要求的是中间8个数字相同，即8个1或者8个2或者8个3。因此可以分3次求解。当目标是“中间8个数字都是1”时，2和3就没有区别了（都是“非1”），因此状态总数变成了8个1，16个“非1”的全排列个数，24!/(8!*16!)=735471，在可以接受的范围内了。

  非常好的状态空间分析思路，按这个思路写BFS，虽然较慢但能通过。用迭代加深搜索IDDFS会快一些，最优的方法还是IDA*，其启发式函数可以这样定：当前操作完成后，统计中间8个数字1、2、3数量的最大值x，则至少还需要8-x步操作。IDA*做法其实不需要进行状态空间分析，也就不用分中间8个数字都是1或者2或者3三类情况了。

AC 代码

IDA*

#include <iostream>
using namespace std;#define M 16
const int m = 8, n = 24, c[] = {6, 7, 8, 11, 12, 15, 16, 17}, f[] = {5, 4, 7, 6, 1, 0, 3, 2},idx[][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 v[n]; char a[M+1];int h() {int cnt[] = {0, 0, 0, 0}, mx = 0;for (int j=0; j<m; ++j) mx = max(mx, ++cnt[v[c[j]]]);return m - mx;
}bool IDAStar(int s, int d) {if (s == d) {for (int i=1; i<m; ++i) if (v[c[i]] != v[c[i-1]]) return false;return true;} else for (int i=0; i<m; ++i) if (s == 0 || f[i] != a[s-1]-'A') {int x = v[idx[i][0]];for (int j=1, k=m-1; j<k; ++j) v[idx[i][j-1]] = v[idx[i][j]];v[idx[i][m-2]] = x; a[s] = 'A'+i;if (s+h() < d && IDAStar(s+1, d)) return true;x = v[idx[i][m-2]];for (int j=m-2; j>0; --j) v[idx[i][j]] = v[idx[i][j-1]];v[idx[i][0]] = x;}return false;
}void solve() {for (int i=1; i<n; ++i) cin >> v[i];for (int d=0; d<M; a[++d] = 0) if (IDAStar(0, d)) {cout << (d == 0 ? "No moves needed" : a) << endl << v[c[0]] << endl;break;}
}int main() {while (cin >> v[0] && v[0]) solve();return 0;
}

分3次BFS

#include <iostream>
#include <cstring>
using namespace std;#define M 735471 // C(24,8)
const int m = 8, n = 24, c[] = {6, 7, 8, 11, 12, 15, 16, 17}, f[] = {5, 4, 7, 6, 1, 0, 3, 2},idx[][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 s[M], q[M], p[M], a[M], v[n], g[n], t, b, cc, d; char ans[50], ss[50];bool term() {for (int i=1; i<m; ++i) if (v[c[i]] != v[c[i-1]]) return false;return true;
}bool term2() {for (int i=0; i<m; ++i) if (g[c[i]] != b) return false;return true;
}void insert() {int x = 0;for (int i=0; i<n; ++i) x = x<<1 | (g[i] == b ? 1 : 0);int k = x % M;while (s[k]) {if (s[k] == x) return;k = (k+1) % M;}s[k] = x; q[t++] = k;
}void decode(int x) {for (int i=n-1; i>=0; --i) g[i] = x&1 ? b : 0, x >>= 1;
}void get_path(int f, char c, int d) {if (f) get_path(p[f], char('A'+ a[f]), d-1);ss[d] = c;
}void bfs() {memset(s, t = 0, sizeof(s)); memset(ss, 0, sizeof(ss)); memcpy(g, v, sizeof(v)); ss[0] = 'X'; a[0] = -1; insert();for (int h=0, c=t, dd=1; h<c; ++h) {int k = q[h]; decode(s[k]);for (int i=0; i<m; ++i) if (f[i] != a[h]) {int x = g[idx[i][0]];for (int j=1, k=m-1; j<k; ++j) g[idx[i][j-1]] = g[idx[i][j]];g[idx[i][m-2]] = x;if (term2()) {get_path(h, char('A'+i), dd - 1);if (dd < d || strcmp(ss, ans) < 0) memcpy(ans, ss, sizeof(ss)), cc = b, d = dd;return;}p[t] = h; a[t] = i; insert();x = g[idx[i][m-2]];for (int j=m-2; j>0; --j) g[idx[i][j]] = g[idx[i][j-1]];g[idx[i][0]] = x;}if (h+1 == c) {c = t;if (++dd > d) return;}}
}void solve() {for (int i=1; i<n; ++i) cin >> v[i];if (term()) {cout << "No moves needed" << endl << v[c[0]] << endl;return;}for (b=1, cc=0, d=50; b<4; ++b) bfs();cout << ans << endl << cc << endl;
}int main() {while (cin >> v[0] && v[0]) solve();return 0;
}