【题意】：八数码问题
【题解】：IDA*，用每个数字到目标位置的哈曼顿路长来做估价函数，奇偶判断有没有可行解。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "cstdlib"
5 #include "queue"
6 using namespace std;
7 #define SIZE 3
8 const int dx[] = {-1, 0, 0, 1};
9 const int dy[] = {0, -1, 1, 0};
10 char op[] = {'u', 'l', 'r', 'd'};
11 int goal_state[10][2] = {{0,0}, {1,1}, {1,2}, {1,3}, {2,1}, {2,2}, {2,3}, {3,1}, {3,2}, {3,3}};
12 int bound;
13 char a[10];
14 bool flag;
15 char solution[1000];
16
17 struct Eight {
18 char board[4][4];
19 int x, y;
20 };
21
22 int h(char board[][4]) {
23 int cost = 0;
24 for(int i = 1; i <= SIZE; i++)
25 for(int j = 1; j <= SIZE; j++)
26 if(board[i][j]) cost += abs(i - goal_state[board[i][j]][0]) + abs(j - goal_state[board[i][j]][1]);
27 return cost;
28 }
29
30 bool solvable() {
31 int cnt = 0;
32 for(int i = 1; i <= 9; i++)
33 for(int j = 1; j < i; j++)
34 if(a[j] < a[i] && a[j]) cnt++;
35 if(cnt & 1) return false;
36 return true;
37 }
38
39 bool check(int x, int y) {
40 if(x >= 1 && x <= SIZE && y >= 1 && y <= SIZE) return true;
41 return false;
42 }
43
44 bool dfs(Eight now, int dv, char pre) {
45 if(h(now.board) == 0) {
46 solution[dv] = 0;
47 return true;
48 }
49 for(int i = 0; i < 4; i++) {
50 if(i + pre == 3) continue;//与上一步相反的移动
51 Eight next = now;
52 next.x += dx[i], next.y += dy[i];
53 if(check(next.x, next.y)) {
54 solution[dv] = op[i];
55 swap(next.board[next.x][next.y], next.board[now.x][now.y]);
56 if(h(next.board) + dv >= bound) continue;
57 if(dfs(next, dv + 1, i)) return true;
58 }
59 }
60 return false;
61 }
62
63 void IDA_star(Eight st) {
64 bound = h(st.board);
65 for(bound = h(st.board); !dfs(st, 0, -10); bound++);
66 puts(solution);
67 }
68
69 int main() {
70 int sx, sy;
71 char c[2];
72 while(1) {
73 Eight st;
74 for(int i = 1; i <= SIZE; i++) {
75 for(int j = 1; j <= SIZE; j++) {
76 if(scanf("%s", c) == EOF) return 0;
77 if(c[0] == 'x') {
78 st.board[i][j] = 0;
79 st.x = i, st.y = j;
80 } else st.board[i][j] = c[0] - '0';
81 a[(i - 1) * SIZE + j] = st.board[i][j];
82 }
83 }
84 if(solvable()) IDA_star(st);
85 else printf("unsolvable\n");
86 }
87 return 0;
88 }
89