骑士的巡回算法
所以我必须编写这个算法（这个版本不需要在骑士开始的同一个地方结束），我让它工作，但它太慢了。 对于size = 8，它适用于起始位置x = 0和y = 0，但是如果我尝试将x和y操纵为例如2和4，则它在几分钟后不会结束。 有人可以帮忙吗？
#include #define size 8 int ruch_x[]={ -1, 1, -2, 2, -2, 2, -1, 1}; //arrays of possible knight moves, for example 2nd move is [1,2]// int ruch_y[]={ 2, 2, 1, 1, -1, -1, -2, -2}; int done(int szach[][size]) { for(int i=0;i<size;i++) { for(int j=0;j<size;j++) { if(szach[i][j]==0) return 0; } } return 1; } //licz - variable for counting knights moves// void konik(int szach[][size], int x, int y, int licz) { szach[x][y]=licz; if(licz<size*size){ for(int i=0;i=0&&x+ruch_x[i]=0&&y+ruch_y[i]<size) // checking if candidat was already visited and if it's not outside of the board// { konik(szach, x+ruch_x[i], y+ruch_y[i], licz+1);}}} if(done(szach)==1) return; //checking if whole board is filled with numbers, if yes then skip zeroing current move// szach[x][y]=0; } int main() { int i, j, x,y; printf("set x\n"); scanf("%d", &x); printf("set y\n"); scanf("%d", &y); int szach[size][size]; for(i=0;i<size;i++) { //zeroing array// for(j=0;j<size; j++) { szach[i][j]=0; }} konik(szach, x, y, 1); for(int i=0;i<size;i++) { for(int j=0;j<size; j++) { printf("%d\t",szach[j][i]); } printf("\n\n");} printf("\n"); return 0; } 简单地使用暴力可能是一个坏主意，因为对于8×8电路板，可能的序列数量可能超过10 ^ 50。
关于维基百科的骑士旅游文章有关于这个问题的正确信息，我建议从那里开始。
用于查找哈密尔顿路径的最着名的启发式方法之一是：从任何节点开始，按照图中的度数以非递减顺序对邻居进行排序。 让我们说u的骑士可以移动到p和q （即u有两个邻居），然后在你的递归中考虑最初的p如果它的可用邻居少于q 。 这通常会导致显着的优化，特别是如果图中有很多Hamilton Paths，就像在这种情况下一样。
关于你的代码。 您不需要每次都调用done（）。 如果在任何时候licz >= size*size ，那么你就知道你找到了答案。 例如，您可以存储完整的boolean done 。 这应该有所帮助，但在所有情况下都无济于事。
PS如果您的项目需要任何单一解决方案，我建议存储单个Hamilton 循环 ，对于任何x,y只需简单地移动序列以获得有效的解决方案。
这绝不是一个答案，只是一个可能有用的想法。
我记得，对于某些尺寸，简单的螺旋形图案将填充板的外边缘，并将问题简化为更简单的size减小4的问题。
您可以使用此想法来简化您的问题。 例如，填充8×3和8×5板而不是8×8板（您必须更新算法以寻找合适的结束位置）。
ile的建议似乎很好。 当我实现的时候首先要考虑图中最低度 （可能从位置移动的数量）的候选者（近似为四个角中最近的一个的标题），找到起始位置x的解决方案的运行时间= 2和y = 4从10个半小时到1分15秒。 计划的变化是：
// arrays of possible knight moves, for example 2nd move is [1,2] // rearranged so that adjacent moves differ by 45 angular degrees int ruch_x[]={ 2, 1, -1, -2, -2, -1, 1, 2}; int ruch_y[]={ 1, 2, 2, 1, -1, -2, -2, -1};
#include //licz - variable for counting knights moves// void konik(int szach[][size], int x, int y, int licz) { szach[x][y]=licz; if (licz 7) i -= 8; // checking if candidate ... if (x+ruch_x[i]>=0&&x+ruch_x[i]=0&&y+ruch_y[i]
顺便说一句，原始程序的行为没有严格定义，因为在检查x+ruch_x[i] ， y+ruch_y[i]之前检查了szach[x+ruch_x[i]][y+ruch_y[i]] y+ruch_y[i]不在板arrays之外。