大神请进！马踏棋盘问题：为何我的思路总也跑不出结果？请教！
本帖最后由 dequantianhe 于 2019-12-29 14:27 编辑各位大佬，今日老弟习题做到S1E36：快速排序 的马踏棋盘问题，经过苦思冥想自认为找到了解决的思路，但代码写完，程序跑起来，最多运行七八个小时，已然没有一个结果得出。
于是我感觉是我的逻辑有问题，但自己反复查看又找不到问题，而这个程序实现所需要的运算量极大，又不可能实际手动去校正（实际我经过了简单的尝试，也未发现问题）。
故烦请各位大佬上演看看，问题究竟在哪里！
上代码前，先简单的说一下我的思路：
整体思路：一个8*8的棋盘一共64位，最后的结果就是要按照马走日的行进方式对64位进行排序，能全部排出来就是正确结果。
1、棋盘64位小弟首先对他们进行编号，按照0~63的顺序,生命为全局变量qipannum，qipannum是本位的编号，qipannum的值只有0/1两种值，0代表尚未排序，1代表已排序。
2、先通过条件计算出每一位通过马走日的规矩可以指向的下一位的编号，得到64*8的一个数组mybe。（64个编号，最多8种可能）
3、声明变量deep，即每次遍历中已排序的棋盘位数（从0开始到63结束）；
4、定义一个全局变量result，用来存放每次遍历成功的结果。
5、声明一个64位数组test，用来存放每次已排序的棋盘位数，等test填满，deep值为63时排序成功，将test此时的值传给result，count值从0开始，代表总共得到多少种答案了。
6、最关键的遍历部分，从主函数中用for循环依次给test赋初值（0~63）,利用初值带入真正的循环函数calcu()
7、函数calcu的逻辑定义：
a、先判断deep值是否为63，是的话说明排序已完成，赋值给result后返回。
b、deep值小于63，说明排序未完成，需要进行以下操作：
利用最新以排序的值p，去遍历这个值在mybe中有多少种可以安排的下一位，下一位next要求值大于等于0，且下一位的值在棋盘qipannum的对应值不为1（即尚未被安排）
找到符合条件的next后，把第一个符合条件的next排序，赋值给p,同时设定qipannum的值为1，即标记为已排序。
再次调用自己，将新的deep值代入，如此循环遍历，直到没有合适的next后，返回，内层calcu函数执行完毕后，要设置qipannum的值为0，即准备下一次循环。
8、整个程序还是一个循环遍历的思路，直到把所有可能的组合全部遍历完毕，得到所有的可能的答案。
qipannum编号示意图(横向为x,纵向为y)：
下面把代码打一下：（部分细节还可以优化，暂且先这样）
#include<stdio.h>
int qipanxy;
int qipannum;
int result;
void getpossible(int p, int q);
void getpossible(int p, int q)
{
int i;
q=8>p+1 && p+1 >= 0 && 8>p +2 && p+2>=0?(p+1)*8+p+2:-1;
q=8>p+1 && p+1 >= 0 && 8>p - 2 && p- 2>=0?(p+1)*8+p+2:-1;
q=8>p- 1 && p- 1 >= 0 && 8>p +2 && p+2>=0?(p- 1)*8+p+2:-1;
q=8>p- 1 && p- 1 >= 0 && 8>p - 2 && p- 2>=0?(p- 1)*8+p+2:-1;
q=8>p+2 && p+2 >= 0 && 8>p +1 && p+1>=0?(p+2)*8+p+2:-1;
q=8>p+2 && p+2 >= 0 && 8>p - 1 && p- 1>=0?(p+2)*8+p+2:-1;
q=8>p- 2 && p- 2 >= 0 && 8>p +1 && p+1>=0?(p- 2)*8+p+2:-1;
q=8>p- 2 && p- 2 >= 0 && 8>p - 1 && p- 1>=0?(p- 2)*8+p+2:-1;
for(i = 0;i <8;i++)
{
if(q< 0||q>63)
{
q = -1;
}
}
}
int calcu(int p, int q, int *count, int deep);
int calcu(int p, int q, int *count, int deep)
{
int i,j,tmp,k;
if(deep == 63)
{
for(k=0;k < 64;k++)
{
result[*count] = p;
}
(*count)++;
printf("sucessfully!");
return;
}
else
{
for(j = 0; j< 8; j++)//开始遍历p数值可能对应的下一步的所有数值
{
tmp = q];
if(tmp >= 0 && qipannum != 1)
{
p= tmp;//增加新的排序数值
qipannum=1;//标记为已排序
calcu(p,q,count,deep+1);//调用自身，进行下一层排序判断
qipannum=0;//第deep+1层排序为tmp的可能性已遍历完，解除标记，为第deep+1层为下个可能的数值做准备。
}
}
}
}
int main(void)
{
int mybe;
int i,j,count = 0;
int *p = &count;
int test = {-2};
for(i = 0; i< 8;i++)
{
for(j = 0; j< 8; j++)
{
qipanxy= j;//j为x
qipanxy= i;//i为y
qipannum= i*8+j; //给qipannum赋值,这一步可能没啥必要，但不影响结果
qipannum= 0;
}
}
for(i = 0；i< 64;i++)
{
getpossible(qipanxy,mybe);
}
for(i = 0;i< 64; i++)//将mybe的结果打出
{
printf("%d对应的可能下一步的数字:",i)
for(j = 0;j< 8;j++)
{
printf("%d",mybe);
}
printf("\n");
}
for(i = 16;i< 64;i++)//i应该从0开始遍历，但小甲鱼说从16开始容易得到结果，可惜我这里尝试后还是没有结果
{
test = i;
qipannum= 1;
calcu(test,mybe,p,0);
qipannum = 0;
}
for(i = 0; i< count; i++)
{
printf("第%d种行走方案：",i);
for(j = 0;j< 64;j++)
{
printf("%d",result);
}
printf("\n");
}
return 0;
}
我先自己回复下：
代码最后一段输出结果的时候，网页显示有问题，应该是printf("%d ",result[ i ][ j ] ),实际编写的也是，但不知道为何发出来丢了【i】，请忽略这个错误。 {:10_266:}{:10_266:}{:10_266:}{:10_266:}
这帖子没人看啊？？？ 提示一下，马踏棋盘如果硬搜的话，一共要搜索63步，每步的选择数目在1-7之间，
其总共可能出现的情况的数目应该是不亚于2^63这个数量级的。仅仅深搜的话时间复杂度是不能接受的。 Croper 发表于 2019-12-30 00:38
提示一下，马踏棋盘如果硬搜的话，一共要搜索63步，每步的选择数目在1-7之间，
其总共可能出现的情况的数 ...
嗯，时间复杂度的意思是时间太长了吧，我把8*8的棋盘改成6*6的，已经得到结果了，印证了我的逻辑应该是是没问题的 各位老铁，不用回复了，问题已经解决了！谢谢大家！
页:
[1]