首页 > 代码库 > Eight(经典题,八数码)
Eight(经典题,八数码)
Eight
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 20993 Accepted Submission(s): 5634
Special Judge
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
//就是类似九宫格那个游戏，不过这里9个格子大小都相等
//学了比较多的东西，才懂怎么做
这里我用的的是 A*+逆序数剪枝+hash判重 做的
A*其实也好理解，就是 bfs 升级版
这个博客写的很详细 http://www.cppblog.com/mythit/archive/2009/04/19/80492.aspx
因为，无论怎么移动，逆序数的奇偶性是不变的，所以用这个能剪枝
最大的问题就是怎么判重了，最多不过 9！种情况么，362880 ，每种情况对应一个数字，用一个 vis[ ]就能判重了,然后hash 判重就好理解了
还有许多方法，推荐一篇博客 http://www.cnblogs.com/goodness/archive/2010/05/04/1727141.html 有兴趣可以看看
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <iostream> 7 #include <queue> 8 #include <map> 9 #include <vector> 10 using namespace std; 11 12 const int maxn=4e5+10;// 400010 最多不超过这么多状态 362880 13 const int hash_[9]={1,1,2,6,24,120,720,5040,40320}; 14 struct Node 15 { 16 int state[3][3]; 17 int x,y; 18 int g,h; //g代表已耗费,h代表估计耗费 19 int hash_num; //这个状态的 hash 值 20 bool operator < (const Node PP) const 21 { 22 //return g+h > PP.g+PP.h; 23 //1638ms 24 return h==PP.h ? g>PP.g : h>PP.h; 25 //686ms 26 } 27 }star,ans; 28 29 int dx[4]={1,-1,0,0}; 30 int dy[4]={0,0,1,-1}; 31 char op_c[8]={"durl"}; 32 struct Node2 33 { 34 int pre_hash; 35 char op; 36 }p[maxn]; 37 int vis[maxn]; 38 39 40 int count_hash(Node p)//获得hash值,计算的是 0-8 排列的hash 41 { 42 int i,j,k,hash_num=0; 43 for (i=0;i<9;i++) 44 { 45 k=0; 46 for (j=0;j<i;j++) 47 { 48 if (p.state[j/3][j%3]>p.state[i/3][i%3]) 49 k++; 50 } 51 hash_num+=k*hash_[i]; 52 } 53 return hash_num; 54 } 55 56 int count_h(Node p)//注意位置，要细致 57 { 58 int i,all=0; 59 for (i=0;i<9;i++) 60 { 61 int e=p.state[i/3][i%3]; 62 if (e) 63 { 64 e-=1; 65 all+=abs(i/3-e/3)+abs(i%3-e%3); 66 } 67 } 68 return all; 69 } 70 71 72 void print(int h) 73 { 74 if (p[h].pre_hash==-1) return; 75 print(p[h].pre_hash); 76 printf("%c",p[h].op); 77 } 78 79 void A_star() 80 { 81 int i; 82 83 star.hash_num = count_hash(star); 84 star.g=0; 85 star.h=count_h(star); 86 87 memset(vis,0,sizeof(vis)); 88 vis[star.hash_num]=1; 89 p[star.hash_num].pre_hash=-1; //头节点 90 91 priority_queue <Node> Q; 92 Q.push(star); 93 94 Node e,n; 95 int xx,yy; 96 97 if (star.hash_num==ans.hash_num)//这个不能丢 98 { 99 printf("\n");100 return;101 }102 while (!Q.empty())103 {104 e=Q.top();105 Q.pop();106 107 for (i=0;i<4;i++)108 {109 xx=e.x+dx[i];110 yy=e.y+dy[i];111 if (xx<0||yy<0||xx>=3||yy>=3) continue;112 113 n=e;114 n.x=xx;115 n.y=yy;116 swap(n.state[xx][yy],n.state[e.x][e.y]);117 n.g++;118 n.h=count_h(n);119 n.hash_num=count_hash(n);120 121 if (vis[n.hash_num]) continue;122 123 p[n.hash_num].pre_hash=e.hash_num; //记录这个状态的的父 hash124 p[n.hash_num].op=op_c[i]; //记录怎么由父hash移动来的125 126 vis[n.hash_num]=1;127 if (n.hash_num==ans.hash_num)//说明到了128 {129 print(n.hash_num);130 printf("\n");131 return;132 }133 Q.push(n);134 }135 }136 }137 138 int main()139 {140 char str[30];141 int i;142 143 for(i=0;i<9;i++) //终点144 ans.state[i/3][i%3]=(i+1)%9;145 ans.hash_num=count_hash(ans); //终点146 147 while(gets(str))148 {149 int i;150 int len=strlen(str);151 152 int j=0;153 for(i=0,j=0;i<len;i++)154 {155 if(str[i]==‘ ‘)continue;156 if(str[i]==‘x‘)157 {158 star.state[j/3][j%3]=0;159 star.x=j/3;160 star.y=j%3;161 }162 else star.state[j/3][j%3]=str[i]-‘0‘;163 j++; // j/3 记录行数164 }165 166 //判断逆序数167 int temp [9],k=0;168 for (i=0;i<9;i++)169 temp[i]=star.state[i/3][i%3];170 for (i=0;i<9;i++)171 {172 if (temp[i]==0) continue;173 for (int j=0;j<i;j++)174 if (temp[j]>temp[i]) k++;175 }176 if (k%2)177 printf("unsolvable\n");178 else179 A_star();180 }181 return 0;182 }183 184 /*//错在这，浪费我2小时，才找出来！ == 竟然不报错，而且是全局变量，第一次也不会错！！！185 186 for (i=0,j=0;i<len;i++)187 {188 if (str[i]==‘ ‘)continue;189 else if (str[i]==‘x‘)190 {191 star.x=j/3;192 star.y=j%3;193 star.state[j/3][j%3]==0;194 }195 else star.state[j/3][j%3]=str[i]-‘0‘;196 j++;197 }198 */
Eight(经典题,八数码)