c - 骑士之旅算法

Question

所以我必须编写这个算法(这个版本不需要在骑士开始的同一位置结束)，并且我让它工作，但它太慢了。它适用于起始位置 x=0 和 y=0(大小=8)，但如果我尝试将 x 和 y 操纵为例如 2 和 4，它不会在几分钟后结束。有人可以帮忙吗？

#include <stdio.h>
#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<=7;i++){ //loop that checks every possible knight move//
            if(szach[x+ruch_x[i]][y+ruch_y[i]]==0&&x+ruch_x[i]>=0&&x+ruch_x[i]<size&&y+ruch_y[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;
}

Answer 1

简单地暴力破解可能不是一个好主意，因为对于 8x8 板来说，可能的序列数量可能超过 10^50。

Knight's tour维基百科上的文章有关于这个问题的不错的信息，我建议从那里开始。

查找哈密顿路径的最著名的启发式之一如下:从任何节点 u 中，按相邻节点在图中的度数以非降序排列。假设从 u 骑士可以移动到 p 和 q (即 u 有两个邻居)，然后如果递归的可用邻居少于 q，则首先考虑 p。这通常会导致显着的优化，特别是如果图形具有大量汉密尔顿路径(如本例所示)。

关于你的代码。你不需要每次都调用done()。如果在任何时候 licz >= size*size，那么您就知道您找到了答案。例如，您可以存储全局 bool 值完成。这应该会有一点帮助，但并不是在所有情况下都有帮助。

附注如果您的项目需要任何单一解决方案，我建议存储单个汉密尔顿循环，并且对于任何x,y只需简单地移动获得有效解决方案的顺序。