Question

马踏棋盘问题 递归反应慢 还是我写的程序有问题

【马踏棋盘】
*问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。
*测试数据：由读者指定,可自行指定一个马的初始位置。
*实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。
#include<iostream>
#include<iomanip>
using namespace std;
void Show(int a[9][9]);
int b;
int dy[9][2] = {{0, 0}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}};

void Run(int a[9][9], int x, int y, int tot){
if(tot >= 64) {
Show(a);
return;
}
tot++;
for(int i = 1; i < 9; ++i){
int nx = x+dy[i][0], ny = y+dy[i][1];
if(!a[nx][ny] && nx > 0 && ny > 0 && nx < 9 && ny < 9){
a[nx][ny] = tot;
Run(a, nx, ny, tot);
}
}
a[x][y] = 0;
tot--;

}

void Show(int a[9][9]){
cout<<endl;
for(int i = 1; i < 9; ++i){
cout<<endl;
for(int j = 1; j < 9; ++j){
cout<<setw(3)<<a[i][j];
}
}
}

int main(){
int x, y;
int a[9][9] = {0};
cin>>x>>y;
a[x][y] = 1;
Run(a, x, y, 1);
return 0;
}这是我写的程序 可是输入总是没有反应 我感觉是不是要的时间很长 用递归的算法 反正半天没有反应
请问下这个程序是否有问题，，，，，，，

Answer 1

调试了一下，发现运行到后来就进入死循环了。
void Run(int a[9][9], int x, int y, int tot){
if(tot >= 64) {
Show(a);
return;
}
tot++;
for(int i = 1; i < 9; ++i){
int nx = x+dy[i][0], ny = y+dy[i][1];
if(!a[nx][ny] && nx > 0 && ny > 0 && nx < 9 && ny < 9){
a[nx][ny] = tot;
Run(a, nx, ny, tot);//这里
}
}
a[x][y] = 0;
tot--;//这里

}

追问

不晓得哦 有什么好的见解

追答

没有什么好方法，建棵树，然后一个节点一个节点的删除吧，不过运算量很多。

Answer 2

貌似你的算法比较慢，因为穷举的话，这个运算要接近10^60量级，所以需要考虑更好地算法。

Answer 3

a[x][y] = 0; 这句应该紧接在
Run(a, nx, ny, tot); 的后面。

Answer 4

void Show(int a[9][9]){
cout<<endl;
for(int i = 1; i < 9; ++i){
cout<<endl;
for(int j = 1; j < 9; ++j){
cout<<setw(3)<<a[i][j];
}
}
}

int main(){
int x, y;
int a[9][9] = {0};
cin>>x>>y;
a[x][y] = 1;
Run(a, x, y, 1);

Answer 5

7个

Answer 6

也简单一点或许还行