【题意】：八数码问题

【题解】：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