简单马踏棋盘设计(C++)
从某点出发不重复地遍历完成整个棋盘输出遍历点的先后：
就以9*10的象棋棋盘为例：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define row 9
#define col 10
bool chess[row][col];//棋盘
int choose[2][8]={{1,2,1,-2,-1,2,-1,-2},{2,1,-2,1,2,-1,-2,-1}};//方向选择
typedef struct{
int s[row*col][11];
int top;
}mystack;
inline bool valid(int x,int y,int info){//对于给定的x,y,info是否符合要求
int delta_x=choose[0][info];
int delta_y=choose[1][info];
if(x+delta_x<0||x+delta_x>=row||y+delta_y<0||y+delta_y>=col||chess[x+delta_x][y+delta_y]==true) return false;
else return true;
}
void getpath(mystack &ch,int hx,int hy,int maxsize)
{int number=0;
int loop=1;
hx--;hy--;
memset(chess,false,sizeof(chess));
chess[hx][hy]=true;
int rank[2][8];//存放依照出路个数排的：路径号；出路个数；
ch.top=1;
ch.s[0][8]=hx;ch.s[0][9]=hy;ch.s[0][10]=-1;
int top,x,y,num,cmd,t;
while(ch.top!=0){loop++;
if(ch.top==row*col-1){//发现一个解
printf("第%d次循环第%d个解：\n",loop++,1+number++);
int help=0;//换行器
int y;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
for( y=0;y<row*col;y++){
if(ch.s[y][8]==i&&ch.s[y][9]==j){
printf("%d \t",y+1);help++;break;
}
}
if(y==row*col){
printf("%d\t",90);help++;
}
if(help%10==0){printf("\n");}
}
}
}
top=ch.top-1;num=0;
if(ch.s[top][10]==-1){//开始分配方向(依照出路个数)
ch.s[top][10]=0;
x=ch.s[top][8];y=ch.s[top][9];
for(int i=0;i<8;i++){
if(valid(x,y,i)){chess[x+choose[0][i]][y+choose[1][i]]=true;cmd=0;//假设，最后还要//还原
for(int j=0;j<8;j++){
if(valid(x+choose[0][i],y+choose[1][i],j)){cmd++;}
}
if(cmd){
rank[0][num]=i;rank[1][num++]=cmd;
}
chess[x+choose[0][i]][y+choose[1][i]]=false;
}
//printf("%d\n",num);
}
if(number==maxsize) return;
if(num){
for(int i=0;i<num-1;i++){//先简单选择排序
for(int j=i+1;j<num;j++){
if(rank[1][j]>rank[1][i]){
t=rank[1][j];rank[1][j]=rank[1][i];rank[1][i]=t;
t=rank[0][j];rank[0][j]=rank[0][i];rank[0][i]=t;
}
}
}
ch.s[top][10]=num;
for(int i=0;i<num;i++){
//printf("%d ",rank[1][i]);
ch.s[top][i]=rank[0][i];
}
//printf("\n");
x=ch.s[top][8];y=ch.s[top][9];num=ch.s[top][10];
num=ch.s[top][num-1];ch.s[top][10]--;
top=ch.top-1;
ch.s[top+1][8]=x+choose[0][num];ch.s[top+1][9]=y+choose[1][num];ch.s[top+1][10]=-1;
chess[x+choose[0][num]][y+choose[1][num]]=true;
ch.top++;
}
}
else {
x=ch.s[top][8];y=ch.s[top][9];num=ch.s[top][10];//printf("%d %d ",top,num);
if(num){//printf("%d %d\n",num,top);
num=ch.s[top][num-1];ch.s[top][10]--;
ch.s[top+1][8]=x+choose[0][num];ch.s[top+1][9]=y+choose[1][num];ch.s[top+1][10]=-1;
chess[x+choose[0][num]][y+choose[1][num]]=true;
//printf("%d %d\n",x+choose[0][num],y+choose[1][num]);
ch.top++;
}
}
if(top!=ch.top-2&&ch.s[top][10]==0){
x=ch.s[top][8];y=ch.s[top][9];chess[x][y]=false;//退格
ch.top--;//没有可行解
top--;
}
}
}
int main()
{
mystack s;
int hx,hy,maxsize;
printf("请输入起点,最大解个数\n");scanf("%d%d%d",&hx,&hy,&maxsize);
getpath(s,hx,hy,maxsize);
}
运行效果：
请输入起点,最大解个数
3 4 5
第90次循环第1个解：
42 39 2 35 50 17 14 21 32 19
3 36 41 46 15 34 51 18 13 22
40 43 38 1 68 49 16 33 20 31
37 4 45 70 47 58 67 52 23 12
44 79 74 81 72 69 48 59 30 53
5 86 71 84 75 82 57 66 11 24
78 89 80 73 62 65 60 27 54 29
87 6 85 76 83 8 63 56 25 10
90 77 88 7 64 61 26 9 28 55
第99次循环第2个解：
42 39 2 35 50 17 14 21 32 19
3 36 41 46 15 34 51 18 13 22
40 43 38 1 68 49 16 33 20 31
37 4 45 70 47 58 67 52 23 12
44 79 74 81 72 69 48 59 30 53
5 90 71 84 75 82 57 66 11 24
78 87 80 73 62 65 60 27 54 29
89 6 85 76 83 8 63 56 25 10
86 77 88 7 64 61 26 9 28 55
第110次循环第3个解：
42 39 2 35 50 17 14 21 32 19
3 36 41 46 15 34 51 18 13 22
40 43 38 1 68 49 16 33 20 31
37 4 45 70 47 58 67 52 23 12
44 79 74 81 72 69 48 59 30 53
5 88 71 84 75 82 57 66 11 24
78 85 80 73 62 65 60 27 54 29
89 6 87 76 83 8 63 56 25 10
86 77 90 7 64 61 26 9 28 55
第119次循环第4个解：
42 39 2 35 50 17 14 21 32 19
3 36 41 46 15 34 51 18 13 22
40 43 38 1 68 49 16 33 20 31
37 4 45 70 47 58 67 52 23 12
44 79 74 81 72 69 48 59 30 53
5 88 71 84 75 82 57 66 11 24
78 85 80 73 62 65 60 27 54 29
87 6 89 76 83 8 63 56 25 10
90 77 86 7 64 61 26 9 28 55
第132次循环第5个解：
42 39 2 35 50 17 14 21 32 19
3 36 41 46 15 34 51 18 13 22
40 43 38 1 68 49 16 33 20 31
37 4 45 70 47 58 67 52 23 12
44 79 74 81 72 69 48 59 30 53
5 86 71 88 75 82 57 66 11 24
78 89 80 73 62 65 60 27 54 29
85 6 87 76 83 8 63 56 25 10
90 77 84 7 64 61 26 9 28 55
Process returned 0 (0x0) execution time : 4.406 s
Press any key to continue.
本文地址：https://blog.csdn.net/undergraduate_/article/details/107288356