热门标签
热门文章
- 1编程的灵魂：数据结构+算法_程序=数据结构+算法, 是程序设计的灵魂。
- 2Flink - Table API UDF --- 用户自定义函数_flink numeric
- 35.3问题总结_divide varchar
- 4HDFS实现的高可用性以及备份机制_hdfs 关闭数据备份
- 5javaweb基于springboot开发蛋糕店甜品店交易商城平台源码_javaweb蛋糕商城源码
- 6brew cleanup 命令详解
- 7配置交换机 SSH 管理和端口安全——实验1:配置交换机基本安全和 SSH管理_中兴交换机 login block 900 attempts 30
- 8微信小程序隐私指引完整填写范本（开发者收集你选中的照片或视频信息，用于？）_开发者收集你选中的照片或视频信息,用于
- 9【总线】AXI4第四课时：握手机制详解
- 10Java的23个设计模式(ChatGPT)_java设计模式
当前位置: article > 正文
八数码问题（C++）_8数码问题c++
作者：黑客灵魂 | 2024-06-20 06:26:26
赞
踩
8数码问题c++
问题描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始状态和目标状态，找到一种最少步骤的移动方法，实现从初始状态到目标状态的转变。
例如：
输入样例：
输入棋子在棋盘的初始状态及目标状态，注第一个3×3为初始状态，第二个3×3为目标状态，且数字之间以空格分开，如：
3 1 2
4 0 5
6 7 8
0 1 2
3 4 5
6 7 8
输出样例：
输出棋盘初始状态及每步的移动结果，直到目标状态，如：
initial
3 1 2
4 0 5
6 7 8step 1
3 1 2
0 4 5
6 7 8
step 2
0 1 2
3 4 5
6 7 8
总代码
1.盲搜（无向导搜索）
采用广搜的方法，实现无向导搜索。
#include<iostream> #include<map> #include<queue> using namespace std; queue<int>Qtmp; map<int,int>pointex; map<int,int>count; map<int,int>qifazhi; map<int,int>pointdir; int resultsum[100]; int dir[4][2]={-1,0,0,1,1,0,0,-1}; int point[3][3]; int r,c; int qifa(int sum0,int end0){ int result=0; if((sum0/100000000==0)&&(end0/100000000==0)){ result++; } while((sum0%10!=0)&&(end0%10!=0)&&(sum0/10!=0)){ if(sum0%10==end0%10){ result++; } sum0=sum0/10; end0=end0/10; } return result; } int move(int u,int d) { int tmp=0; int nr=r+dir[d][0]; int nc=c+dir[d][1]; point[r][c]=point[nr][nc]; point[nr][nc]=0; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) tmp=tmp*10+point[i][j]; } return tmp; } int formulate(int s,int endsum0) { Qtmp.push(s); pointex[s]=1; count[s]=0; int number=0; while(Qtmp.size()) { int u,v; u=Qtmp.front(); Qtmp.pop(); if(u==endsum0){ return count[u]; } int minqifa=move(u,0); for(int i=0;i<4;i++) { bool fool=true; int uu=u; for(int ii=2;ii>=0;ii--) { for(int jj=2;jj>=0;jj--) { point[ii][jj]=uu%10; uu/=10; if(point[ii][jj]==0) { r=ii; c=jj; } } } if((i==0&&r==0)||(i==1&&c==2)||(i==2&&r==2)||(i==3&&c==0)){ fool=false; } if(fool) { v=move(u,i); if(!pointex[v]) { int qifatmp=qifa(v,endsum0); if(qifatmp<=minqifa){ pointex[v]=1; count[v]=count[u]+1; pointdir[v]=i; Qtmp.push(v); number++; } } } } if(number>100){ return -1; } } return -1; } int main() { int end[3][3]; int endsum=0; int beginsum=0; int result; for(int i=0;i<3;i++){ for(int j=0;j<3;j++) { cin>>point[i][j]; beginsum=beginsum*10+point[i][j]; } } for(int i=0;i<3;i++){ for(int j=0;j<3;j++) { cin>>end[i][j]; endsum=endsum*10+end[i][j]; } } result=formulate(beginsum,endsum); resultsum[result+1]=endsum; int endr0,endc0; int temp=endsum; for(int i=2;i>=0;i--) { for(int j=2;j>=0;j--) { end[i][j]=temp%10; temp/=10; if(end[i][j]==0) { endr0=i; endc0=j; } } } int tmpsum; //cout<<result<<endl; if(result==-1){ cout<<"no answer"<<endl; } if(result!=-1){ for(int i=result;i>0;i--){ if(pointdir[endsum]==0){ end[endr0][endc0]=end[endr0+1][endc0]; end[endr0+1][endc0]=0; tmpsum=end[0][0]*100000000+end[0][1]*10000000+end[0][2]*1000000+end[1][0]*100000+end[1][1]*10000+end[1][2]*1000+end[2][0]*100+end[2][1]*10+end[2][2]; resultsum[i]=tmpsum; endr0=endr0+1; } if(pointdir[endsum]==1){ end[endr0][endc0]=end[endr0][endc0-1]; end[endr0][endc0-1]=0; tmpsum=end[0][0]*100000000+end[0][1]*10000000+end[0][2]*1000000+end[1][0]*100000+end[1][1]*10000+end[1][2]*1000+end[2][0]*100+end[2][1]*10+end[2][2]; resultsum[i]=tmpsum; endc0=endc0-1; } if(pointdir[endsum]==2){ end[endr0][endc0]=end[endr0-1][endc0]; end[endr0-1][endc0]=0; tmpsum=end[0][0]*100000000+end[0][1]*10000000+end[0][2]*1000000+end[1][0]*100000+end[1][1]*10000+end[1][2]*1000+end[2][0]*100+end[2][1]*10+end[2][2]; resultsum[i]=tmpsum; endr0=endr0-1; } if(pointdir[endsum]==3){ end[endr0][endc0]=end[endr0][endc0+1]; end[endr0][endc0+1]=0; tmpsum=end[0][0]*100000000+end[0][1]*10000000+end[0][2]*1000000+end[1][0]*100000+end[1][1]*10000+end[1][2]*1000+end[2][0]*100+end[2][1]*10+end[2][2]; resultsum[i]=tmpsum; endc0=endc0+1; } endsum=tmpsum; } for(int i=1;i<result+2;i++){ if(i==1){ cout<<"initial"<<endl; } else{ cout<<"step "<<i-1<<endl; } int k=0; for(int j=100000000;j>0;j=j/10){ cout<<resultsum[i]/j<<" "; resultsum[i]=resultsum[i]-resultsum[i]/j*j; k++; if(k%3==0){ cout<<endl; } } cout<<endl; } } system("pause"); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
2.启发式搜索（有向导搜索）
新增启发函数，实现有向导搜索，大大减少搜索时间。
#include<iostream> #include<map> #include<queue> using namespace std; queue<int>Qtmp; map<int,int>pointex; map<int,int>count; map<int,int>pointdir; int resultsum[100]; int dir[4][2]={-1,0,0,1,1,0,0,-1}; int point[3][3]; int r,c; int qifa(int sum0,int end0){ int result=0; if((sum0/100000000==0)&&(end0/100000000==0)){ result++; } while((sum0%10!=0)&&(end0%10!=0)&&(sum0/10!=0)){ if(sum0%10==end0%10){ result++; } sum0=sum0/10; end0=end0/10; } return result; } int move(int u,int d) { int tmp=0; int nr=r+dir[d][0]; int nc=c+dir[d][1]; point[r][c]=point[nr][nc]; point[nr][nc]=0; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) tmp=tmp*10+point[i][j]; } return tmp; } int formulate(int s,int endsum0) { Qtmp.push(s); pointex[s]=1; count[s]=0; int number=0; while(Qtmp.size()) { int u,v; u=Qtmp.front(); Qtmp.pop(); if(u==endsum0){ return count[u]; } int minqifa=100; for(int i=0;i<4;i++) { bool fool=true; int uu=u; for(int ii=2;ii>=0;ii--) { for(int jj=2;jj>=0;jj--) { point[ii][jj]=uu%10; uu/=10; if(point[ii][jj]==0) { r=ii; c=jj; } } } if((i==0&&r==0)||(i==1&&c==2)||(i==2&&r==2)||(i==3&&c==0)){ fool=false; } if(fool) { v=move(u,i); if(!pointex[v]) { int qifatmp=qifa(v,endsum0); if(qifatmp<=minqifa){ minqifa=qifatmp; pointex[v]=1; count[v]=count[u]+1; pointdir[v]=i; Qtmp.push(v); number++; } } } } if(number>100){ return -1; } } return -1; } int main() { int end[3][3]; int endsum=0; int beginsum=0; int result; for(int i=0;i<3;i++){ for(int j=0;j<3;j++) { cin>>point[i][j]; beginsum=beginsum*10+point[i][j]; } } for(int i=0;i<3;i++){ for(int j=0;j<3;j++) { cin>>end[i][j]; endsum=endsum*10+end[i][j]; } } result=formulate(beginsum,endsum); resultsum[result+1]=endsum; int endr0,endc0; int temp=endsum; for(int i=2;i>=0;i--) { for(int j=2;j>=0;j--) { end[i][j]=temp%10; temp/=10; if(end[i][j]==0) { endr0=i; endc0=j; } } } int tmpsum; //cout<<result<<endl; if(result==-1){ cout<<"no answer"<<endl; } if(result!=-1){ for(int i=result;i>0;i--){ if(pointdir[endsum]==0){ end[endr0][endc0]=end[endr0+1][endc0]; end[endr0+1][endc0]=0; tmpsum=end[0][0]*100000000+end[0][1]*10000000+end[0][2]*1000000+end[1][0]*100000+end[1][1]*10000+end[1][2]*1000+end[2][0]*100+end[2][1]*10+end[2][2]; resultsum[i]=tmpsum; endr0=endr0+1; } if(pointdir[endsum]==1){ end[endr0][endc0]=end[endr0][endc0-1]; end[endr0][endc0-1]=0; tmpsum=end[0][0]*100000000+end[0][1]*10000000+end[0][2]*1000000+end[1][0]*100000+end[1][1]*10000+end[1][2]*1000+end[2][0]*100+end[2][1]*10+end[2][2]; resultsum[i]=tmpsum; endc0=endc0-1; } if(pointdir[endsum]==2){ end[endr0][endc0]=end[endr0-1][endc0]; end[endr0-1][endc0]=0; tmpsum=end[0][0]*100000000+end[0][1]*10000000+end[0][2]*1000000+end[1][0]*100000+end[1][1]*10000+end[1][2]*1000+end[2][0]*100+end[2][1]*10+end[2][2]; resultsum[i]=tmpsum; endr0=endr0-1; } if(pointdir[endsum]==3){ end[endr0][endc0]=end[endr0][endc0+1]; end[endr0][endc0+1]=0; tmpsum=end[0][0]*100000000+end[0][1]*10000000+end[0][2]*1000000+end[1][0]*100000+end[1][1]*10000+end[1][2]*1000+end[2][0]*100+end[2][1]*10+end[2][2]; resultsum[i]=tmpsum; endc0=endc0+1; } endsum=tmpsum; } for(int i=1;i<result+2;i++){ if(i==1){ cout<<"initial"<<endl; } else{ cout<<"step "<<i-1<<endl; } int k=0; for(int j=100000000;j>0;j=j/10){ cout<<resultsum[i]/j<<" "; resultsum[i]=resultsum[i]-resultsum[i]/j*j; k++; if(k%3==0){ cout<<endl; } } cout<<endl; } } system("pause"); return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
运行结果
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/黑客灵魂/article/detail/738899
推荐阅读
相关标签
