用 A* 解决八数码问题

Description

The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as: 

 1  2  3  4 

 5  6  7  8 

 9 10 11 12 

13 14 15  x 

where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle: 

 1  2  3  4    1  2  3  4    1  2  3  4    1  2  3  4 

 5  6  7  8    5  6  7  8    5  6  7  8    5  6  7  8 

 9  x 10 12    9 10  x 12    9 10 11 12    9 10 11 12 

13 14 11 15   13 14 11 15   13 14  x 15   13 14 15  x 

           r->           d->           r-> 

The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively. 

Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and 
frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course). 

In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three 
arrangement. 

Input

You will receive a description of a configuration of the 8 puzzle. The description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle 

 1  2  3 

 x  4  6 

 7  5  8 

is described by this list: 

 1 2 3 x 4 6 7 5 8 

Output

You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line.

Sample Input

 2  3  4  1  5  x  7  6  8 

Sample Output

ullddrurdllurdruldr

 

 

 

 

1. #include <iostream>8 s% W2 b- F3 j$ Y4 o
   
2. #include <cstdio>3 _  h, ^$ P9 ?/ ?
   
3. #include <cstring>
   
4. 
   
5. using namespace std;
   
6. 9 S+ n& Q  g  R4 y
   
7. #define HEAP_PARENT(i)                        (i >> 1); n- q# z9 x0 {. O) L) c2 Q
   
8. #define HEAP_LEFT(i)                        (i << 1)
   
9. #define HEAP_RIGHT(i)                        ((i << 1) + 1)
   
10. #define HEAP_KEY(i)                                (heap[i].key)3 u: O+ O/ {; {+ T
    
11. 
    
12. const int heap_max = 400000;% U9 m4 p4 [+ F4 ^/ N+ s3 ?2 e
    
13. struct heap_data {  A$ }. b  n& m& F6 t) L9 Q  b
    
14.         int step; // depth
    
15.         int key; // f5 o, v. P/ t, \3 _' h" B
    
16.         int v; // node8 F/ m+ u1 [/ a: `
    
17.         unsigned int path[4]; // path
    
18. } heap[heap_max] = {0};" j: r$ A- F) R0 L. j# `# T" U+ K
    
19. 9 r. o  ?# L1 S& @  D5 B0 a
    
20. class class_heap {
    
21. private:
    
22.         int heap_size;6 ~1 u9 ~8 s, d$ @
    
23. 
    
24.         void swap(heap_data &arg1, heap_data &arg2)
    
25.         {
    
26.                 heap_data temp_heap;        ' J# i5 _0 ~1 r6 f- \
    
27.                 temp_heap = arg1; arg1 = arg2; arg2 = temp_heap;
    
28.         }
    
29. 
    
30.         int heap_min_up(int node)$ R) v: _, }. G! s6 \7 p/ w
    
31.         {: \1 }4 o  @  |8 k2 g3 F5 ]
    
32.                 int parent;
    
33. - E- R* q. z; a+ q- m; |
    
34.                 parent = HEAP_PARENT(node);% ?  I! b) g( P+ y6 V3 w( g
    
35.                 if (node > 1 && HEAP_KEY(parent) > HEAP_KEY(node)) {% o5 a1 i/ j8 m! M& w/ h" V6 ~% b
    
36.                         swap(heap[parent], heap[node]);. K, R  `8 l: g: K) {
    
37.                         return heap_min_up(parent);: t2 F9 `* [2 K* Y4 ~. C- {
    
38.                 } 
    
39.                 return node;
    
40.         }
    
41. 
    
42.         int heap_min_down(int node)
    
43.         {
    
44.                 int left, right;
    
45.                 int smallest = node;( l" d  t3 R) u5 x
    
46. 
    
47.                 left = HEAP_LEFT(node);! I1 P8 ]+ r- b5 h+ e: D# f
    
48.                 right = HEAP_RIGHT(node);- ~  o& P. {- h* N. m
    
49.                 if (left <= heap_size && HEAP_KEY(left) < HEAP_KEY(node)) {
    
50.                         smallest = left;
    
51.                 }9 b3 I. \- X: R% C, i
    
52.                 if (right <= heap_size && HEAP_KEY(right) < HEAP_KEY(smallest)) {" C6 o( c1 N5 N; t/ z
    
53.                         smallest = right;$ ~" S# E. C! R; ]3 m
    
54.                 }
    
55.                 if (smallest != node) {
    
56.                         smallest = 0;' M/ Y. ^" t- Q  x
    
57.                         if (left <= heap_size) {7 A* k  X( e+ l
    
58.                                 smallest = left;
    
59.                         }  R7 W) p# a2 X
    
60.                         if (right <= heap_size && HEAP_KEY(right) < HEAP_KEY(left)) {
    
61.                                 smallest = right;
    
62.                         }
    
63.                         if (smallest) {
    
64.                                 swap(heap[smallest], heap[node]);7 L4 D6 I4 E' o. E; T
    
65.                                 return heap_min_down(smallest);
    
66.                         }/ i" V) y8 e8 N" K; `  d5 f2 e1 k
    
67.                 }
    
68.                 return node;* o/ ?+ {: ]: {  ?
    
69.         }
    
70. 2 y. g$ I% L0 B% L( C( F4 w
    
71. public:" C: u! Z9 C( v
    
72.         class_heap() { heap_size = 0; }2 Y: _4 R# |: C$ n
    
73. / j- }* e3 i( }
    
74.         void insert(heap_data key)
    
75.         {; h/ X& Q' {7 y1 O- ?& G" O
    
76.                 heap[++heap_size] = key;/ K+ `2 F( @  r' V! n/ \: {
    
77.                 heap_min_up(heap_size);
    
78.         }
    
79. 
    
80.         heap_data extract_min()  s0 ^: M7 L! t) a8 t
    
81.         {
    
82.                 heap_data result = heap[1];
    
83. 
    
84.                 swap(heap[1], heap[heap_size--]);
    
85.                 heap_min_down(1);+ t1 w0 h- ^$ N* h+ h/ k& {3 B, H
    
86.                 return result;
    
87.         }6 _! L1 z9 g1 I
    
88. ( U7 Z+ H! N3 R) R( A8 `% k
    
89.         bool empty()
    
90.         {9 C$ P( T' x, [6 q: i
    
91.                 return (heap_size == 0);
    
92.         }1 N4 [# g' t) {: x6 O2 I
    
93. };5 |5 y; U6 r: K( e2 x
    
94. 
    
95. class_heap heap_table;
    
96. bool hash[400000] = {0};- t! b% r! Z, I7 v
    
97. const int dstst = 123456780;4 L3 \; X. i6 ?
    
98. const int table[10] = {0, 100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1};. ?, l- h; `. q6 N. @9 `/ s
    
99. const int markl[10][5] = {  ' D! W7 i9 @0 N' v. s- Q
    
100.         {0, 0, 0, 0, 0},/ b( {- e/ u% m$ `+ l2 q: W
     
101.         {0, 2, 0, 0, 4},
     
102.         {0, 3, 1, 0, 5},' [- `3 w/ d% q, ?8 }# ?
     
103.         {0, 0, 2, 0, 6},9 {; X' `8 w( \5 E$ O. n$ j) ^
     
104.         {0, 5, 0, 1, 7},
     
105.         {0, 6, 4, 2, 8},
     
106.         {0, 0, 5, 3, 9}," t7 B1 ~) i8 \  I- |2 Y
     
107.         {0, 8, 0, 4, 0},
     
108.         {0, 9, 7, 5, 0},- J! w' f5 C2 l0 g6 z  s
     
109.         {0, 0, 8, 6, 0}0 C6 L; x: F, E+ t
     
110. };* l9 Z: A. Y" }9 J0 k* a1 ^  a9 L
     
111. const char markc[5] = {0, 'r', 'l', 'u', 'd'};
     
112. const int fac[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
     
113. 1 S. z2 g1 D8 w0 \6 @+ W
     
114. int calc_hash(int key)
     
115. {6 j# d4 F& }) \, D- u  |4 J
     
116.         int result = 0;! U. v( ~! ^0 B' r& ^6 R+ R
     
117.         int decode[10] = {0};' s1 h+ T6 [" P2 g" M2 H
     
118. 
     
119.         for (int i = 9; i > 0; --i) {
     
120.                 decode[i] = key % 10;
     
121.                 key /= 10;# a/ D9 v+ ~9 X3 O
     
122.         }7 H' C  h/ u  |) ^) ?
     
123.         for (int i = 1; i <= 9; ++i) {+ t4 V3 p2 g, L, `7 q0 m( J
     
124.                 for (int j = i + 1; j <= 9; ++j) {# u" `$ T; F% U5 G2 k( ]
     
125.                         if (decode[j] < decode[i]) {8 N+ X4 l: I; `5 T3 B) |8 G
     
126.                                 result += fac[9 - i];8 [0 G. M$ v8 j
     
127.                         }! B( U; g( [- g
     
128.                 }                . }8 C5 U3 x1 [1 p2 g4 ?
     
129.         }' Q, ?8 i& @0 O% E* D5 I
     
130.         return result;4 v% N' W5 z# r; i4 L
     
131. }9 z! Q/ v- M8 i& q# i2 M
     
132. 1 i1 o, g* g5 Q2 o, M& F, A* Z
     
133. int calc_h(int key)
     
134. {$ i. F* [' z3 w: K7 @: o
     
135.         int key1, key2, result;. _, e# h# y! U# L6 n' t& e
     
136. 8 ?. o* w- i  ]$ ]/ U
     
137.         key1 = dstst; key2 = key; result = 0;
     
138.         for (int i = 1; i <= 9; ++i) {; V6 `6 h; d2 m! z- O
     
139.                 if ((key1 % 10 != key2 % 10) && (key2 % 10 != 0)) {% s8 ~3 S  A1 b5 }: y1 q+ l+ S# }
     
140.                         ++result;
     
141.                 }
     
142.                 key1 /= 10;$ z* j+ T4 A0 U3 z2 E; t
     
143.                 key2 /= 10;
     
144.         }9 h: ]7 [/ m+ q- V
     
145.         return result;1 N3 @( D) H. P: F5 l/ @
     
146. }
     
147. 
     
148. void expand_node(heap_data old_state)
     
149. {
     
150.         int i, n, k, t, h;+ R! I' T3 R* V! A/ D, i8 Y$ h
     
151.         int decode[10] = {0};
     
152.         heap_data new_state;
     
153. & G, _5 B& d2 h" e2 @/ \
     
154.         t = old_state.v;
     
155.         for (i = 9; i > 0; --i) {- O. h/ i: [/ ?1 B0 \) V+ k' k
     
156.                 decode[i] = t % 10;7 |$ x" v# @1 S5 r% n/ B
     
157.                 t /= 10;
     
158.                 if (decode[i] == 0) {
     
159.                         k = i;& [/ D. D$ s5 h2 E
     
160.                 }
     
161.         }  P' j1 S* ]$ b: ~( O
     
162.         for (i = 1; i <= 4; ++i) {7 b! X% b! m. O+ H1 o
     
163.                 n = markl[k][i];* e. C4 N5 O4 ^! Q$ s3 M
     
164.                 if (n != 0) {) p8 y1 @0 E$ `, X. z' J3 v+ p- a2 |' I
     
165.                         t = old_state.v;
     
166.                         t -= table[n] * decode[n];( r$ }* [0 k  [+ |( ]
     
167.                         t += table[k] * decode[n];                        ) I0 |  D3 a3 @# c
     
168.                         h = calc_hash(t);
     
169.                         if (!hash[h]) {
     
170.                                 new_state.v = t;. l! t1 f' p( U
     
171.                                 new_state.key = old_state.step + calc_h(t);                                
     
172.                                 new_state.step = old_state.step + 1;
     
173.                                 memcpy(new_state.path, old_state.path, 16);
     
174.                                 new_state.path[old_state.step / 16] |= ((i - 1) << old_state.step % 16 * 2);
     
175.                                 hash[h] = true;
     
176.                                 heap_table.insert(new_state);% H  l4 q0 a8 |5 }) A+ ^9 ^! x
     
177.                         }# ?: _9 e& |2 Y' R( H9 k
     
178.                 }
     
179.         }( A+ A( m8 @. K' C, X5 D. @( m
     
180. }
     
181. + g, }3 M7 Y; k/ o: m% F
     
182. void astar_search()7 E8 [( s4 ^* P+ m, ?1 n
     
183. {
     
184.         heap_data node;1 a" v6 c# |% A. ?5 ]7 K
     
185.         int flag = false;
     
186. 
     
187.         while (!heap_table.empty()) {; A7 n6 `+ r! z; p
     
188.                 node = heap_table.extract_min();3 y" m- j( U, g% ~1 J5 {( W; Y, v
     
189.                 if (node.v == dstst) {" W, ]2 }0 w. S8 w
     
190.                         for (int i = 0; i < node.step; ++i) {
     
191.                                 cout<<markc[node.path[i / 16] % 4 + 1];
     
192.                                 node.path[i / 16] >>= 2;. ]  a- {3 y/ ^' f% I' C
     
193.                         }$ n$ `( H6 ?# I' a  T4 K
     
194.                         flag = true;
     
195.                         break;
     
196.                 } else {- X4 f" N" ?5 q
     
197.                         expand_node(node);
     
198.                 }/ x+ Y$ t) j0 c% W& [* Q6 i: N$ X
     
199.         }* ?/ M6 L+ n: m& U
     
200.         if (!flag) {
     
201.                 cout<<"unsolvable"<<endl;# O7 y4 a1 i. I8 P0 m# C8 f* g8 i
     
202.         }4 ~/ i9 \" b) L+ T2 Z# v! p( C
     
203. }
     
204. 
     
205. int main()
     
206. {
     
207.         int src = 0;6 r! \5 ]3 {: {
     
208.         char ch;% l0 `8 c! ]. {$ O# b+ I" u* u, t; V$ m" y
     
209.         heap_data srcst;
     
210. 
     
211.         for (int i = 1; i <= 9; ++i) {
     
212.                 cin>>ch;5 j3 I, e& Q4 a2 }' G5 i# s
     
213.                 if (ch != 'x') {
     
214.                         ch -= '0';
     
215.                         src += table[i] * ch;
     
216.                 }
     
217.         }
     
218.         hash[calc_hash(src)] = true;9 Z2 s+ N& x& e+ M- e! g
     
219.         srcst.v = src; 8 w" Q- z2 g- H1 A, D2 O) d8 z( m
     
220.         srcst.key = calc_h(src); ( I+ P  ]3 e7 ]/ }3 R$ x
     
221.         srcst.step = 0; 
     
222.         memset(srcst.path, 0, 16);
     
223.         heap_table.insert(srcst);4 X6 s8 I/ I  o( b% q
     
224.         astar_search();
     
225.         return 0;
     
226. }