Problem 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, several descriptions of configuration of the 8 puzzle. One 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. Do not print a blank line between cases.

 

Sample Input

 

Sample Output

 

#include <iostream>

#include <string>

#include <string.h>

#include <map>

#include <stdio.h>

#include <algorithm>

#include <queue>

#include <vector>

#include <math.h>

#include <set>

#define Max(a,b) ((a)>(b)?(a):(b))

#pragma comment(linker, "/STACK:16777216")

using namespace std ;

typedef long long LL ;

const int fac[] = {,,,,,,,,} ;

const int d[][] = {{,},{-,},{,},{,-}} ; //四个方向

const char direction[] = {'d','u','r','l'} ;     //输出记录

const int end_pos[][] = {{,},{,},{,},{,},

                                 {,},{,},{,},

                                 {,},{,},{,}}  ;  //最后状态  123

                                                        //          456

                                                        //          78X

class Node{

    public :

        char mat[][] ;

        int  x ;

        int  y ;

        int  h ;  //h(x)=递归层数

        int  g ;  //g(x)=曼哈顿距离和

        int  f ;  //估价函数 f(x) = g(x)+ h(x)

        int  id ; //hash值,用于判重,利用排列序列的康拓展开

        int  G() ;//求g（x）

        int  cango() ; //剪枝，为什么逆序数必须是偶数，网上很多人问这个问题。

                       //我的解答： 与X（空白）交换的Y ，编号（index）相差为偶数，即在[ index[X] + 1 .index[Y]-1 ] 区间的数为偶数 ；

                       // 交换前  ，设  [ index[X] + 1 .index[Y]-1 ](zh) ，〉Y有a个，<Y 有b个 ，则a+b为偶数 ；

                       // 交换后  ，逆序数相较之前 +b -a  ,即| 逆序数交换前 -逆序数交换后 | 为偶数 。

                       // 也就是说无论何种交换，逆序数的变化差值为偶数 ，而最终的状态12345678X   。 (X可看作为9) ，逆序数为0。

                       // 即只能从逆序数为偶数的状态转移  。

        int  Hash() ;  // 求id

        void out() ;

        Node(){};

        Node(vector<char>) ;

        friend bool operator < (const Node &A ,const Node &B){

             if(A.f != B.f)

                return A.f > B.f ;

             else

                return A.g > B.g ;

        }             //建堆，使用C++ STL 优先队列 ，f(x)=g(x)+h（x） , f(x)小的优先级别大，也就是说与最后的状态差异小的优先考虑

};

Node::Node(vector<char>s){

    int i , j ;

    for(int k =  ;k < s.size() ;k++){

       i = k/ ;

       j = k% ;

       if(s[k] == 'x'){

           this->x = i ;

           this->y = j ;

       }

       mat[i][j] = s[k] ;

    }

}

int Node::G(){

    int sum =  ;

    for(int i =  ;i <=  ;i++){

      for(int j =  ;j <=  ;j++){

         if(mat[i][j]=='x')

           continue ;

         int n = mat[i][j] - '' ;

         sum = sum + abs(i-end_pos[n][]) + abs(j - end_pos[n][]) ;

      }

    }

    return  sum ;

}

int Node::cango(){

    char num[] ;

    int n =  ,sum = ;

    for(int i =  ;i <= ;i++){

        for(int j =  ;j <=  ;j++){

            if(mat[i][j] != 'x')

               num[++n] = mat[i][j] ;

        }

    }

    for(int i =  ;i <= n ;i++){

        for(int j = ;j < i ;j++){

            if(num[j] > num[i])

               sum++ ;

        }

    }

    return (sum&) ==  ;

}

int Node::Hash(){

    char num[] ;

    int n =  ,sum ,index =  ;

    for(int i =  ;i <= ;i++){

        for(int j =  ;j <=  ;j++)

               num[n++] = mat[i][j] ;

    }

    for(int i =  ;i < n ;i++){

        sum =  ;

        for(int j = ;j < i ;j++){

            if(num[j] > num[i])

               sum++ ;

        }

        index += fac[i]*sum ;

    }

    return  index ;

}

void Node::out(){

    for(int i =  ;i <=  ;i++){

        for(int j =  ;j <=  ;j++)

            putchar(mat[i][j]) ;

        puts("") ;

    }

}

int father[]  ;

class App{

  private :

    bool visited[] ;

    Node start ;

    char opet[] ;

  public :

    App(){}

    App(class Node) ;

    int cango(int ,int) ;

    int A_star() ;

    void out() ;

};

App::App(class Node s){

    start = s ;

    start.h =  ;

    start.g = start.G() ;

    start.f = start.g + start.h ;

    start.id = start.Hash() ;

    memset(visited,,sizeof(visited)) ;

    visited[start.id] =  ;

}

int App::cango(int x ,int y){

    return <=x&&x<=&&<=y&&y<= ;

}

int App::A_star(){

    if(start.id == )

        return  ;

    if(!start.cango())

        return  ;

    priority_queue<Node>que ;

    que.push(start) ;

    while(!que.empty()){

        Node now =que.top() ;

        que.pop() ;

        if(now.id == )

           return  ;

        for(int i =  ;i <  ;i++){

           int x = now.x + d[i][] ;

           int y = now.y + d[i][] ;

           if(!cango(x,y))

             continue ;

           Node next = now ;

           next.x = x ;

           next.y = y ;

           swap(next.mat[now.x][now.y],next.mat[next.x][next.y]) ;

           next.id = next.Hash() ;

           if(visited[next.id])

              continue ;

           visited[next.id] =  ;

           if(!next.cango())

              continue ;

           next.g = next.G() ;

           next.h = now.h +  ;

           next.f = next.g + next.h ;

           father[next.id] = now.id ;

           opet[next.id] = direction[i] ;

           que.push(next) ;

        }

    }

    return  ;

}

void App::out(){

    if(A_star()==)

       puts("unsolvable") ;

    else{

        vector<char>ans ;

        ans.clear() ;

        int i =  ;

        while(start.id != i){

            ans.push_back(opet[i]) ;

            i = father[i] ;

        }

        for(int i = ans.size()- ;i >=  ;i--)

           putchar(ans[i]) ;

        puts("") ;

    }

}

int main(){

   char str[] ;

   vector<char> s ;

   while(gets(str)){

       s.clear() ;

       for(int i =  ;i < strlen(str) ;i++){

           if(str[i] != ' ')

               s.push_back(str[i]) ;

       }

       Node start ;

       start = Node(s) ;

       App app = App(start)  ;

       app.out() ;

   }

   return  ;

}

其中 f(n) 是从初始点经由节点n到目标点的估价函数，

g(n) 是在状态空间中从初始节点到n节点的实际代价，

h(n) 是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：

估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。

如果 估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。