用 A* 解决八数码问题DescriptionThe 15-puzzle has been around for over 100 years even if you dont
用 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
?
?
?
?
#include <iostream>8 s% W2 b- F3 j$ Y4 o
#include <cstdio>3 _??h, ^$ P9 ?/ ?
#include <cstring>
using namespace std;
9 S+ n& Q??g??R4 y
#define HEAP_PARENT(i)? ? ? ? ? ? ? ? ? ? ? ? (i >> 1); n- q# z9 x0 {. O) L) c2 Q
#define HEAP_LEFT(i)? ? ? ? ? ? ? ? ? ? ? ? (i << 1)
#define HEAP_RIGHT(i)? ? ? ? ? ? ? ? ? ? ? ? ((i << 1) + 1)
#define HEAP_KEY(i)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (heap[i].key)3 u: O+ O/ {; {+ T
const int heap_max = 400000;% U9 m4 p4 [+ F4 ^/ N+ s3 ?2 e
struct heap_data {??A$ }. b??n& m& F6 t) L9 Q??b
? ? ? ? int step; // depth
? ? ? ? int key; // f5 o, v. P/ t, \3 _' h" B
? ? ? ? int v; // node8 F/ m+ u1 [/ a: `
? ? ? ? unsigned int path[4]; // path
} heap[heap_max] = {0};" j: r$ A- F) R0 L. j# `# T" U+ K
9 r. o???# L1 S& @??D5 B0 a
class class_heap {
private:
? ? ? ? int heap_size;6 ~1 u9 ~8 s, d$ @
? ? ? ? void swap(heap_data &arg1, heap_data &arg2)
? ? ? ? {
? ? ? ? ? ? ? ? heap_data temp_heap;? ? ? ??' J# i5 _0 ~1 r6 f- \
? ? ? ? ? ? ? ? temp_heap = arg1; arg1 = arg2; arg2 = temp_heap;
? ? ? ? }
? ? ? ? int heap_min_up(int node)$ R) v: _, }. G! s6 \7 p/ w
? ? ? ? {: \1 }4 o??@??|8 k2 g3 F5 ]
? ? ? ? ? ? ? ? int parent;
- E- R* q. z; a+ q- m; |
? ? ? ? ? ? ? ? parent = HEAP_PARENT(node);% ???I! b) g( P+ y6 V3 w( g
? ? ? ? ? ? ? ? if (node > 1 && HEAP_KEY(parent) > HEAP_KEY(node)) {% o5 a1 i/ j8 m! M& w/ h" V6 ~% b
? ? ? ? ? ? ? ? ? ? ? ? swap(heap[parent], heap[node]);. K, R??`8 l: g: K) {
? ? ? ? ? ? ? ? ? ? ? ? return heap_min_up(parent);: t2 F9 `* [2 K* Y4 ~. C- {
? ? ? ? ? ? ? ? }?
? ? ? ? ? ? ? ? return node;
? ? ? ? }
? ? ? ? int heap_min_down(int node)
? ? ? ? {
? ? ? ? ? ? ? ? int left, right;
? ? ? ? ? ? ? ? int smallest = node;( l" d??t3 R) u5 x
? ? ? ? ? ? ? ? left = HEAP_LEFT(node);! I1 P8 ]+ r- b5 h+ e: D# f
? ? ? ? ? ? ? ? right = HEAP_RIGHT(node);- ~??o& P. {- h* N. m
? ? ? ? ? ? ? ? if (left <= heap_size && HEAP_KEY(left) < HEAP_KEY(node)) {
? ? ? ? ? ? ? ? ? ? ? ? smallest = left;
? ? ? ? ? ? ? ? }9 b3 I. \- X: R% C, i
? ? ? ? ? ? ? ? if (right <= heap_size && HEAP_KEY(right) < HEAP_KEY(smallest)) {" C6 o( c1 N5 N; t/ z
? ? ? ? ? ? ? ? ? ? ? ? smallest = right;$ ~" S# E. C! R; ]3 m
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (smallest != node) {
? ? ? ? ? ? ? ? ? ? ? ? smallest = 0;' M/ Y. ^" t- Q??x
? ? ? ? ? ? ? ? ? ? ? ? if (left <= heap_size) {7 A* k??X( e+ l
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? smallest = left;
? ? ? ? ? ? ? ? ? ? ? ? }??R7 W) p# a2 X
? ? ? ? ? ? ? ? ? ? ? ? if (right <= heap_size && HEAP_KEY(right) < HEAP_KEY(left)) {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? smallest = right;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? if (smallest) {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? swap(heap[smallest], heap[node]);7 L4 D6 I4 E' o. E; T
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? return heap_min_down(smallest);
? ? ? ? ? ? ? ? ? ? ? ? }/ i" V) y8 e8 N" K; `??d5 f2 e1 k
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return node;* o/ ?+ {: ]: {???
? ? ? ? }
2 y. g$ I% L0 B% L( C( F4 w
public:" C: u! Z9 C( v
? ? ? ? class_heap() { heap_size = 0; }2 Y: _4 R# |: C$ n
/ j- }* e3 i( }
? ? ? ? void insert(heap_data key)
? ? ? ? {; h/ X& Q' {7 y1 O- ?& G" O
? ? ? ? ? ? ? ? heap[++heap_size] = key;/ K+ `2 F( @??r' V! n/ \: {
? ? ? ? ? ? ? ? heap_min_up(heap_size);
? ? ? ? }
? ? ? ? heap_data extract_min()??s0 ^: M7 L! t) a8 t
? ? ? ? {
? ? ? ? ? ? ? ? heap_data result = heap[1];
? ? ? ? ? ? ? ? swap(heap[1], heap[heap_size--]);
? ? ? ? ? ? ? ? heap_min_down(1);+ t1 w0 h- ^$ N* h+ h/ k& {3 B, H
? ? ? ? ? ? ? ? return result;
? ? ? ? }6 _! L1 z9 g1 I
( U7 Z+ H! N3 R) R( A8 `% k
? ? ? ? bool empty()
? ? ? ? {9 C$ P( T' x, [6 q: i
? ? ? ? ? ? ? ? return (heap_size == 0);
? ? ? ? }1 N4 [# g' t) {: x6 O2 I
};5 |5 y; U6 r: K( e2 x
class_heap heap_table;
bool hash[400000] = {0};- t! b% r! Z, I7 v
const int dstst = 123456780;4 L3 \; X. i6 ?
const int table[10] = {0, 100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1};. ?, l- h; `. q6 N. @9 `/ s
const int markl[10][5] = {??' D! W7 i9 @0 N' v. s- Q
? ? ? ? {0, 0, 0, 0, 0},/ b( {- e/ u% m$ `+ l2 q: W
? ? ? ? {0, 2, 0, 0, 4},
? ? ? ? {0, 3, 1, 0, 5},' [- `3 w/ d% q, ?8 }# ?
? ? ? ? {0, 0, 2, 0, 6},9 {; X' `8 w( \5 E$ O. n$ j) ^
? ? ? ? {0, 5, 0, 1, 7},
? ? ? ? {0, 6, 4, 2, 8},
? ? ? ? {0, 0, 5, 3, 9}," t7 B1 ~) i8 \??I- |2 Y
? ? ? ? {0, 8, 0, 4, 0},
? ? ? ? {0, 9, 7, 5, 0},- J! w' f5 C2 l0 g6 z??s
? ? ? ? {0, 0, 8, 6, 0}0 C6 L; x: F, E+ t
};* l9 Z: A. Y" }9 J0 k* a1 ^??a9 L
const char markc[5] = {0, 'r', 'l', 'u', 'd'};
const int fac[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
1 S. z2 g1 D8 w0 \6 @+ W
int calc_hash(int key)
{6 j# d4 F& }) \, D- u??|4 J
? ? ? ? int result = 0;! U. v( ~! ^0 B' r& ^6 R+ R
? ? ? ? int decode[10] = {0};' s1 h+ T6 [" P2 g" M2 H
? ? ? ? for (int i = 9; i > 0; --i) {
? ? ? ? ? ? ? ? decode[i] = key % 10;
? ? ? ? ? ? ? ? key /= 10;# a/ D9 v+ ~9 X3 O
? ? ? ? }7 H' C??h/ u??|) ^) ?
? ? ? ? for (int i = 1; i <= 9; ++i) {+ t4 V3 p2 g, L, `7 q0 m( J
? ? ? ? ? ? ? ? for (int j = i + 1; j <= 9; ++j) {# u" `$ T; F% U5 G2 k( ]
? ? ? ? ? ? ? ? ? ? ? ? if (decode[j] < decode[i]) {8 N+ X4 l: I; `5 T3 B) |8 G
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? result += fac[9 - i];8 [0 G. M$ v8 j
? ? ? ? ? ? ? ? ? ? ? ? }! B( U; g( [- g
? ? ? ? ? ? ? ? }? ? ? ? ? ? ? ??. }8 C5 U3 x1 [1 p2 g4 ?
? ? ? ? }' Q, ?8 i& @0 O% E* D5 I
? ? ? ? return result;4 v% N' W5 z# r; i4 L
}9 z! Q/ v- M8 i& q# i2 M
1 i1 o, g* g5 Q2 o, M& F, A* Z
int calc_h(int key)
{$ i. F* [' z3 w: K7 @: o
? ? ? ? int key1, key2, result;. _, e# h# y! U# L6 n' t& e
8 ?. o* w- i??]$ ]/ U
? ? ? ? key1 = dstst; key2 = key; result = 0;
? ? ? ? for (int i = 1; i <= 9; ++i) {; V6 `6 h; d2 m! z- O
? ? ? ? ? ? ? ? if ((key1 % 10 != key2 % 10) && (key2 % 10 != 0)) {% s8 ~3 S??A1 b5 }: y1 q+ l+ S# }
? ? ? ? ? ? ? ? ? ? ? ? ++result;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? key1 /= 10;$ z* j+ T4 A0 U3 z2 E; t
? ? ? ? ? ? ? ? key2 /= 10;
? ? ? ? }9 h: ]7 [/ m+ q- V
? ? ? ? return result;1 N3 @( D) H. P: F5 l/ @
}
void expand_node(heap_data old_state)
{
? ? ? ? int i, n, k, t, h;+ R! I' T3 R* V! A/ D, i8 Y$ h
? ? ? ? int decode[10] = {0};
? ? ? ? heap_data new_state;
& G, _5 B& d2 h" e2 @/ \
? ? ? ? t = old_state.v;
? ? ? ? for (i = 9; i > 0; --i) {- O. h/ i: [/ ?1 B0 \) V+ k' k
? ? ? ? ? ? ? ? decode[i] = t % 10;7 |$ x" v# @1 S5 r% n/ B
? ? ? ? ? ? ? ? t /= 10;
? ? ? ? ? ? ? ? if (decode[i] == 0) {
? ? ? ? ? ? ? ? ? ? ? ? k = i;& [/ D. D$ s5 h2 E
? ? ? ? ? ? ? ? }
? ? ? ? }??P' j1 S* ]$ b: ~( O
? ? ? ? for (i = 1; i <= 4; ++i) {7 b! X% b! m. O+ H1 o
? ? ? ? ? ? ? ? n = markl[k][i];* e. C4 N5 O4 ^! Q$ s3 M
? ? ? ? ? ? ? ? if (n != 0) {) p8 y1 @0 E$ `, X. z' J3 v+ p- a2 |' I
? ? ? ? ? ? ? ? ? ? ? ? t = old_state.v;
? ? ? ? ? ? ? ? ? ? ? ? t -= table[n] * decode[n];( r$ }* [0 k??[+ |( ]
? ? ? ? ? ? ? ? ? ? ? ? t += table[k] * decode[n];? ? ? ? ? ? ? ? ? ? ? ??) I0 |??D3 a3 @# c
? ? ? ? ? ? ? ? ? ? ? ? h = calc_hash(t);
? ? ? ? ? ? ? ? ? ? ? ? if (!hash[h]) {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? new_state.v = t;. l! t1 f' p( U
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? new_state.key = old_state.step + calc_h(t);? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? new_state.step = old_state.step + 1;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? memcpy(new_state.path, old_state.path, 16);
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? new_state.path[old_state.step / 16] |= ((i - 1) << old_state.step % 16 * 2);
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? hash[h] = true;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? heap_table.insert(new_state);% H??l4 q0 a8 |5 }) A+ ^9 ^! x
? ? ? ? ? ? ? ? ? ? ? ? }# ?: _9 e& |2 Y' R( H9 k
? ? ? ? ? ? ? ? }
? ? ? ? }( A+ A( m8 @. K' C, X5 D. @( m
}
+ g, }3 M7 Y; k/ o: m% F
void astar_search()7 E8 [( s4 ^* P+ m, ?1 n
{
? ? ? ? heap_data node;1 a" v6 c# |% A. ?5 ]7 K
? ? ? ? int flag = false;
? ? ? ? while (!heap_table.empty()) {; A7 n6 `+ r! z; p
? ? ? ? ? ? ? ? node = heap_table.extract_min();3 y" m- j( U, g% ~1 J5 {( W; Y, v
? ? ? ? ? ? ? ? if (node.v == dstst) {" W, ]2 }0 w. S8 w
? ? ? ? ? ? ? ? ? ? ? ? for (int i = 0; i < node.step; ++i) {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? cout<<markc[node.path[i / 16] % 4 + 1];
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? node.path[i / 16] >>= 2;. ]??a- {3 y/ ^' f% I' C
? ? ? ? ? ? ? ? ? ? ? ? }$ n$ `( H6 ?# I' a??T4 K
? ? ? ? ? ? ? ? ? ? ? ? flag = true;
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? } else {- X4 f" N" ?5 q
? ? ? ? ? ? ? ? ? ? ? ? expand_node(node);
? ? ? ? ? ? ? ? }/ x+ Y$ t) j0 c% W& [* Q6 i: N$ X
? ? ? ? }* ?/ M6 L+ n: m& U
? ? ? ? if (!flag) {
? ? ? ? ? ? ? ? cout<<"unsolvable"<<endl;# O7 y4 a1 i. I8 P0 m# C8 f* g8 i
? ? ? ? }4 ~/ i9 " b) L+ T2 Z# v! p( C
}
int main()
{
? ? ? ? int src = 0;6 r! \5 ]3 {: {
? ? ? ? char ch;% l0 `8 c! ]. {$ O# b+ I" u* u, t; V$ m" y
? ? ? ? heap_data srcst;
? ? ? ? for (int i = 1; i <= 9; ++i) {
? ? ? ? ? ? ? ? cin>>ch;5 j3 I, e& Q4 a2 }' G5 i# s
? ? ? ? ? ? ? ? if (ch != 'x') {
? ? ? ? ? ? ? ? ? ? ? ? ch -= '0';
? ? ? ? ? ? ? ? ? ? ? ? src += table[i] * ch;
? ? ? ? ? ? ? ? }
? ? ? ? }
? ? ? ? hash[calc_hash(src)] = true;9 Z2 s+ N& x& e+ M- e! g
? ? ? ? srcst.v = src;?8 w" Q- z2 g- H1 A, D2 O) d8 z( m
? ? ? ? srcst.key = calc_h(src);?( I+ P??]3 e7 ]/ }3 R$ x
? ? ? ? srcst.step = 0;?
? ? ? ? memset(srcst.path, 0, 16);
? ? ? ? heap_table.insert(srcst);4 X6 s8 I/ I??o( b% q
? ? ? ? astar_search();
? ? ? ? return 0;
}
?
?
?
?
?
?
?
?
?
?
?
?
?
?
