題目鏈接

??本題是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;
}