Question

. 编写程序求解骑士巡游问题：在n行n列的棋盘上（如n=5），假设一位骑士（按象棋中“马走日”的行走法）从

Answer 1

这个是我之前做的算法，但然我也是参考了网上提供的思想来做的。这个思想很广泛。把你输入的一个点为第一步，接着搜他可走8个方向中每一个可走的点，并记录这样可走的点的位置。再把这些记录的点再搜他可走的8个方向，但这些只要记录8个方向中可走方向的数目。接着就走方向最少的一条路。这样难走的路在前面已经走了，后面的路就好走很多了，一般都能找到方向。当然还有递归这种算法，但高维度的递归是没有意议的，电脑是算不出来的或着用很长时间才能算出来。下面是我的算法

#include<iostream>
using namespace std;
//定义棋盘的大小
#define N 8
#define LOSE 0
#define SUCCEED 1

void printknightgo(); //输出结果
int knightgo(int x,int y); //运算走法

int chessboard[8][8] = { 0 }; //建立棋盘

void main(){

int x,y;
cout<<"请输入坐标"<<endl;
cin>>x>>y; //输入坐标
if(knightgo(x,y)){ //开始运算走法，如果成功则返回成功，否则返回失败
cout<<"成功完成"<<endl;

}
else{
cout<<"失败"<<endl;

}
printknightgo(); //输出结果
}

//输出结果的算法
void printknightgo(){
for(int i = 0;i < N; i++){
for(int j = 0;j < N;j++){
cout<<chessboard[i][j]<<"\t";
}
cout<<endl;
}
}

int knightgo(int x,int y){
chessboard[x][y] = 1;//将第一步标为1
int step;//走的步数
int nextx[8] = {-1,1,-2,2,-2,2,-1,1};//走的X的步法
int nexty[8] = {2,2,1,1,-1,-1,-2,-2};//走的Y的步法
int recordNextx[8]={0};//记住下步可走X的位置，并用count来记数
int recordNexty[8]={0};//记住下步可走Y的位置，并用count来记数
int tempx,tempy;//用于临时记住X和Y
int i,j;//临时计数变量
int count = 0;//记住可循环的个数
int exist[8]={0};//第2次找8个方向每个可走的记录
for(int step = 2;step <=N*N;step++){//把输进来或循环的位置，找下一个能走的位置,并记住这些位置和可走的个数
for(i = 0;i < 8;i++){ //把上次记录重置0;
recordNextx[i] = 0;
recordNexty[i] = 0;
exist[i] = 0;
}

count = 0;
for(i = 0;i < 8;i++){//第一次循环，找可走的个位置，并记录可走方向的个数
tempx = x + nextx[i];//tempx为临时记录X
tempy = y + nexty[i];//tempy为临时记录Y
if(chessboard[tempx][tempy] == 0 && tempx >= 0 && tempx < N && tempy >= 0 && tempy < N){//当这个位置没走过和不走出盘外时，才能记录
recordNextx[count] = tempx;
recordNexty[count] = tempy;//记录可走方向的x,y坐标
count++; //记录可以走的方向的个数
}
}

//把记住的位置,找他们的下个能走位置的个数,就是重复上面循环，只需记录可走方向的个数

if(count == 0){//如果没有出路则返回失败
return LOSE;
}

else {//如果只有一条路，则走这一条路
if(count == 1){
x = recordNextx[0];//因为可走方向只有一个，所记录中就有recordNext(x,y)[0];
y = recordNexty[0];
chessboard[x][y] = step; //把第几步写入这个棋盘的位置
}

else{//有多条路可以走的话
for(j = 0;j < count;j++){//第一个点记录的可走的方向，并找出们下一个方向可以走的的方向的个数
for(i = 0;i < 8;i++){//找第2个点8个方向可走的方向
tempx = recordNextx[j] + nextx[i];
tempy = recordNexty[j] + nexty[i];
if(chessboard[tempx][tempy] == 0 && tempx >= 0 && tempx < N && tempy >= 0 && tempy < N){//当这个位置没走过和不走出盘外时，才能记录
exist[j]++;//记录第2个点可走方向的个数
}
}
}
//找最方向个数最小的一条路
int min = exist[0];
int last = 0;//用于记住，recordNext(x,y)中可走方向中，能走方向数目最小的一个方向
for(i = 1;i < count;i++){//找出方向数目最小的数和方向
if(exist[i]<min){
min = exist[i];
last = i;
}
}

x = recordNextx[last];//将这个方向给x,y;
y = recordNexty[last];
chessboard[x][y] = step; //将这个步数写出这个棋盘
}

}
}

return SUCCEED;
}

Answer 2

给你个思路吧，把棋盘格子看成矩阵，可以用二维数组形式储存，让起始点（骑士）找到横坐标＋－2，纵坐标＋－1或者纵坐标＋－2，横坐标＋－1的位置，可设置函数，在函数中设置循环，先找是否有横坐标＋2点，存在的话再找纵坐标＋1点，返回1成功，失败则返回0，应该可以用递归函数来写