BFS（五）：八数码难题 （POJ 1077）

BFS（五）：八数码难题 （POJ 1077）

Eight

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）编程思路1。

       1）定义结点

      用数组来表示棋盘的布局，如果将棋盘上的格子从左上角到右下角按0到8编号，就可用一维数组board[9]来顺序表示棋盘上棋子的数字，空格用“9”表示，数组元素的下标是格子编号。为方便处理，状态结点还包括该布局的空格位置space，否则需要查找“9”在数组中的位置才能确定空格的位置。另外，为节约存储空间，将数组类型定义为char（每个元素只占一个字节存储空间，还是可以存储整数1~9）。因此在程序中，定义状态结点为结构数据类型：

struct node{   

       char board[9];  

       char space;    //  空格所在位置

};

      2）状态空间

      由于棋盘有9个格子，每种布局可以看成是数字1~9的一个排列，因此全部的布局数应为9！（362880）种。为了便于判断两种布局是否为同一种布局，可以编写一个函数int hash(const char *s)把数字1~9的排列映射为一个整数num（0<=num<=(9!-1)）。例如，排列“123456789”映射为0、“213456789”映射为1、“132456789”映射为2、“231456789”映射为3、…、“987654312”映射为362878、“987654321”映射为362879。

      这样，每种状态就可以对应一个整数。反过来说，0~ (9!-1)之间的任一整数，也可以唯一对应一种状态。因此，判断两个状态结点cur和nst是否为同一种状态，只需判断 hash(cur.board)和hash(nst.board)是否相等即可，无需对两个格局数组的每个元素进行交互比较。

       为保存状态空间，定义三个全局数据：

      char visited[MAXN]; // visited[i]=1表示状态i被访问过；为0，表示未被访问

       int parent[MAXN];  // parent[i]=k 表示状态结点i是由结点k扩展来的

      char move[MAXN]; // move[i]=d 表示状态结点i是由结点k按照方式d扩展来的

      3）结点扩展规则

      棋子向空格移动实际上是空格向相反方向移动。设空格当前位置是cur.space ，则结点cur的扩展规则为：

      空格向上移动，cur.space=cur.space-3；空格向左移动，cur.space=cur.space-1；空格向右移动，cur.space=cur.space+1；空格向下移动，cur.space=cur.space+3。

设向上移动k=0、向左移动k=1、向右移动k=2、向下移动k=3，则上述规则可归纳为一条：空格移动后的位置为cur.space=cur.space-5+2*(k+1)。为此，定义一个数组

             const char md[4] = {'u', 'l', 'r', 'd'};

表示这四种移动方向。

      空格的位置cur.space<3，不能上移；空格的位置cur.space>5，不能下移；空格的位置cur.space是3的倍数，不能左移；空格的位置cur.space+1是3的倍数，不能右移。

      4）搜索策略

      将初始状态start放入队列中，求出start对应的hash值k = hash(start.board)，并置   parent[k] = -1、visited[k] = 1。

      ① 从队列头取一个结点，按照向上、向左、向右和向下的顺序，检查移动空格后是否可以产生新的状态nst。

      ② 如果移动空格后有新状态产生，则检查新状态nst是否已在队列中出现过（visited[hash(nst.board)]== 1），是则放弃，返回①。

      ③ 如果新状态nst未在队列中出现过，就将它加入队列，再检查新状态是否目标状态（hash(nst.board)==0），如果是，则找到解，搜索结束；否则返回①。

      （2）源程序1。

#include<iostream>

#include<queue>

using namespace std;

struct node{   

       char board[9];  

       char space;  // 空格所在位置

};

const int MAXN = 362880;

int fact[]={ 1, 1,2,6,24,120,720,5040,40320};

//  对应  0！,1！,2！,3！,4！,5！,6！,7！,8！

int hash(const char *s)

// 把1..9的排列*s 映射为数字 0..(9!-1)

{   

       int i, j, temp, num;   

       num = 0;   

       for (i = 0; i < 9-1; i++)

       {     

           temp = 0; 

           for (j = i + 1; j < 9; j++)

          {

              if (s[j] < s[i])

                  temp++;       

          }

          num += fact[9-i-1] * temp;

       }

       return num;

}

char visited[MAXN];

int parent[MAXN];

char move[MAXN];

const char md[4] = {'u', 'l', 'r', 'd'};

void BFS(const node & start)

{   

   int k, i;

   node cur, nst;   

   for(k=0; k<MAXN; ++k) 

       visited[k] = 0;  

   k = hash(start.board);

   parent[k] = -1;  

   visited[k] = 1;  

   queue <node> que; 

   que.push(start);  

   while(!que.empty())

   {

       cur = que.front();  

       que.pop();     

       for(i=0; i<4; ++i)

          {    

          if(!(i==0 && cur.space<3 || i==1 && cur.space%3==0 || i==2 && cur.space%3==2 ||i==3 && cur.space>5))

            {  

              nst = cur;          

              nst.space = cur.space-5+2*(i+1);      

              nst.board[cur.space]=nst.board[nst.space];

                      nst.board[nst.space]=9;

              k = hash(nst.board);   

              if(visited[k] != 1)

                      {   

                move[k] = i;      

                visited[k] = 1;       

                parent[k] = hash(cur.board);         

                if(k == 0)  //目标结点hash值为0    

                   return;           

                que.push(nst);             

                      }          

                }  

          } 

   }

}

void print_path()

{ 

   int n, u;  

   char path[1000]; 

   n = 1;   

   path[0] = move[0];

   u = parent[0];  

   while(parent[u] != -1)

   {      

      path[n] = move[u]; 

      ++n;    

      u = parent[u];

   }  

   for(int i=n-1; i>=0; --i)

   {       

       cout<<md[path[i]];

   }

   cout<<endl;

}

int main()

{  

   node start; 

   char ch;

   int i;

   for(i=0; i<9; ++i)

   {    

      cin>>ch;    

      if(ch == 'x')

         {   

         start.board[i] = 9;   

         start.space = i;   

         }    

      else      

         start.board[i] = ch - '0';  

   }   

    for (i = 0; start.board[i] == i+1 && i < 9; ++i) ;

    if (i == 9) cout<<endl;

    else

     {

              BFS(start);   

              if(visited[0] == 1)  

                   print_path(); 

               else     

                   cout<<"unsolvable"<<endl;

    }

    return 0;

}

      将上面的源程序提交给POJ系统，系统显示的评测结果是：Accept，Memory为3844K、Time为 782MS。

      （3）编程思路2。

      状态空间的表示、结点的扩展规则与编程思路1中的方法基本相同。但结点稍作修改，定义为： struct state { char a[N]; }; 不再定义空格的位置，并且程序中空格用“0”表示。对于某一当前状态cur，执行一个循环 for (i = 0; cur.a[i] && i < N; ++i) ;后，就可以确定空格位置 space=i。

      定义全局数组 state Q[MAXN+1]来作为一个队列使用，全局数组char vis[MAXN]来表示状态结点是否被访问，其中vis[i]=0，表示状态i未被访问过；vis[i]=1，表示状态i是正向扩展（从初始状态开始）来访问过的；vis[i]=2，表示状态i是反向扩展（从目标状态开始）来访问过的。全局数组foot p[MAXN]用来存储访问过的每种状态的访问足迹， 其中，p[nt].k = ct表示状态nt是由状态结点ct扩展来的，p[nt].d = i（i为0~3之一）表示状态nt是由状态结点ct按方式i扩展来的。

      用front和rear变量指示队列的队头和队尾。初始化时，初始状态start和目标状态goal均入队。

            Q[front = 1] = start;

            Q[rear = 2] = goal;

            vis[hash(start)] = 1;   // 1 代表正向

            vis[hash(goal)] = 2;   // 2 代表反向

      （4）源程序2。

#include <iostream>

using namespace std;

# define N 9   

# define MAXN 362880

struct foot  { int k; char d;};

struct state { char a[N]; };

const char md[4] = {'u', 'l', 'r', 'd'};

const int fact[9] = {1, 1, 2, 6, 24, 120, 720, 720*7, 720*56};

state Q[MAXN+1];

char vis[MAXN];

foot p[MAXN];

int hash(state s)

// 把状态s中的0..8的排列映射为数字 0..(9!-1)

{   

       int i, j, temp, num;   

       num = 0;   

       for (i = 0; i < 9-1; i++)

       {     

            temp = 0; 

            for (j = i + 1; j < 9; j++)

           {

               if (s.a[j] < s.a[i])

               temp++;       

           }

           num += fact[8-i] * temp;

       }

       return num;

}

void print_path(int x, char f)

{

    if (p[x].k == 0) return ;

    if (f)  cout<< md[3-p[x].d];

    print_path(p[x].k, f);

    if (!f) cout<< md[p[x].d];

}

void bfs(state start, state goal)

{

    char t;

    state cur, nst;

    int front, rear, i;

    int space, ct, nt;

    Q[front = 1] = start;

    Q[rear = 2] = goal;

    vis[hash(start)] = 1;  // 1 代表正向

    vis[hash(goal)] = 2;   // 2 代表反向

    while (front <= rear)

    {

        cur = Q[front++];

        ct = hash(cur);

        for (i = 0; cur.a[i] && i < N; ++i) ;

        space=i;

        for (i = 0; i < 4; ++i)

        {

            if(!(i==0 && space<3 || i==1 && space%3==0 || i==2 && space%3==2 ||i==3 && space>5))

            {

                 nst = cur;

                 nst.a[space] = cur.a[space-5+2*(i+1)];

                nst.a[space-5+2*(i+1)] = 0;

                nt = hash(nst);

                if (!vis[nt])

                {

                    Q[++rear] = nst;

                    p[nt].k = ct;

                    p[nt].d = i;

                    vis[nt] = vis[ct];

                }

                else if (vis[ct] != vis[nt])

                {

                    t = (vis[ct]==1 ? 1:0);

                    print_path(t ? ct:nt, 0);

                    cout<< md[t ? i:3-i];

                    print_path(t ? nt:ct, 1);

                    cout<<endl;

                    return ;

                }

            }

        }

     }

       cout<<"unsolvable"<<endl;

}

int main()

{

    char i, ch;

    state start, goal;

    for (i = 0; i < N; ++i)

    {

        cin>>ch;

        start.a[i] = (ch=='x' ? 0:ch-'0');

    }

    goal.a[8] = 0;

    for (i = 0; i < N-1; ++i)

        goal.a[i] = i + 1;

    for (i = 0; start.a[i] == goal.a[i] && i < N; ++i) ;

    if (i == N)

              cout<<endl;

    else

              bfs(start, goal);

    return 0;

}

      将上面的源程序提交给POJ系统，系统显示的评测结果是：Accept，Memory为3420K、Time为 16MS 。从系统返回的评测结果看，采用双向广度优先搜索算法，搜索效率大幅提高。

原文链接:https://www.cnblogs.com/cs-whut/p/11162663.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有