http://blog.csdn.net/libin56842/article/details/23185751
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.
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
should include no spaces and start at the beginning of the line. Do not print a blank line between cases.
2 3 4 1 5 x 7 6 8
ullddrurdllurdruldr
了解了一下A*的算法,并用A*做了一下这道题,A*的关键在于F=H+G这个式子,有一定基础的人在网上随便找篇文章看下很容易便能理解其核心思想了
对于八数码这么经典的题目也不多说了,上代码
- #include <stdio.h>
- #include <string.h>
- #include <math.h>
- #include <queue>
- #include <stack>
- #include <algorithm>
- using namespace std;
- struct node
- {
- int f,h,g;
- int x,y;
- char map[5][5];
- friend bool operator< (const node &a,const node &b)
- {
- if(a.f==b.f)
- return a.g<b.g;
- return a.f>b.f;
- }
- };
- char str[100];
- node start,next;
- int hash[15];
- int pos[][2]= {{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1},{2,2}};
- bool vis[500000];
- char ans[500000];
- int pre[500000];
- int to[4][2] = {1,0,0,1,-1,0,0,-1};
- char to_c[10] = "drul";
- int check()//判断不可能的状况
- {
- int i,j,k;
- int s[20];
- int cnt = 0;
- for(i = 0; i<3; i++)
- {
- for(j = 0; j<3; j++)
- {
- s[3*i+j] = start.map[i][j];
- if(s[3*i+j] == 'x')
- continue;
- for(k = 3*i+j-1; k>=0; k--)
- {
- if(s[k] == 'x')
- continue;
- if(s[k]>s[3*i+j])
- cnt++;
- }
- }
- }
- if(cnt%2)
- return 0;
- return 1;
- }
- int solve(node a)//康托
- {
- int i,j,k;
- int s[20];
- int ans = 0;
- for(i = 0; i<3; i++)
- {
- for(j = 0; j<3; j++)
- {
- s[3*i+j] = a.map[i][j];
- int cnt = 0;
- for(k = 3*i+j-1; k>=0; k--)
- {
- if(s[k]>s[3*i+j])
- cnt++;
- }
- ans = ans+hash[i*3+j]*cnt;
- }
- }
- return ans;
- }
- int get_h(node a)//得到H值
- {
- int i,j;
- int ans = 0;
- for(i = 0; i<3; i++)
- {
- for(j = 0; j<3; j++)
- {
- if(a.map[i][j] == 'x')
- continue;
- int k = a.map[i][j]-'1';
- ans+=abs(pos[k][0]-i)+abs(pos[k][1]-j);
- }
- }
- return ans;
- }
- void bfs()
- {
- memset(vis,0,sizeof(vis));
- priority_queue<node> Q;
- start.g = 0;
- start.h = get_h(start);
- start.f = start.h;
- Q.push(start);
- while(!Q.empty())
- {
- node a = Q.top();
- Q.pop();
- int k_s = solve(a);
- for(int i = 0; i<4; i++)
- {
- next = a;
- next.x+=to[i][0];
- next.y+=to[i][1];
- if(next.x < 0 || next.y < 0 || next.x>2 || next.y > 2)
- continue;
- next.map[a.x][a.y] = a.map[next.x][next.y];
- next.map[next.x][next.y] = 'x';
- next.g+=1;
- next.h = get_h(next);
- next.f = next.g+next.h;
- int k_n = solve(next);
- if(vis[k_n])
- continue;
- vis[k_n] = true;
- Q.push(next);
- pre[k_n] = k_s;
- ans[k_n] = to_c[i];
- if(k_n == 0)
- return ;
- }
- }
- }
- int main()
- {
- int i,j,len,x,y;
- hash[0] = 1;
- for(i = 1; i<=9; i++)
- hash[i] = hash[i-1]*i;
- while(gets(str))
- {
- x = y = 0;
- len = strlen(str);
- for(i = 0; i<len; i++)
- {
- if(str[i]>='0' && str[i]<='9' || str[i]=='x')
- {
- start.map[x][y] = str[i];
- if(start.map[x][y] == 'x')
- {
- start.x = x;
- start.y = y;
- }
- y++;
- if(y==3)
- {
- y = 0;
- x++;
- }
- }
- }
- if(!check())
- {
- printf("unsolvable\n");
- continue;
- }
- int sa = solve(start);
- bfs();
- stack<int> s;
- int now = 0;
- while(sa!=now)
- {
- s.push(ans[now]);
- now = pre[now];
- }
- while(!s.empty())
- {
- putchar(s.top());
- s.pop();
- }
- printf("\n");
- }
- return 0;
- }