java - 骑士之旅（回溯）

Question

我正在尝试用 8*8 棋盘解决骑士的巡回问题。但是我的回溯是无限循环的。我的逻辑功能如下：-

N 为 8。

  boolean algo(int x,int y,int no_of_moves,int sol[][]){

        if(no_of_moves==N*N){
            return true;
        }

        int nextx;
        int nexty;
        for(int i=0;i<8;i++){

            nextx=x+move_x[i];
            nexty=y+move_y[i];

            if(is_valid(nextx,nexty)){
                sol[nextx][nexty]=no_of_moves;

                if(algo(nextx,nexty,no_of_moves+1,sol)){
                    return true;
                }
                else
                    sol[nextx][nexty]=-1;

            }
        }
        return false;  
    }

sol [][] 存储骑士的移动。

数组 move_x 和 move_y 存储要添加到 x 和 y 以获得骑士的下一个位置的值。

 int move_x[]={  2, 1, -1, -2, -2, -1,  1,  2 };
    int move_y[]={  1, 2,  2,  1, -1, -2, -2, -1 };

我首先将 x 传递为 0，y 传递为 0，no_of_moves 传递为 1，sol[][] 中的所有值都传递为 -1，除了 sol[0][0] 传递为 0。

并is_valid()检查nextx, 和nexty是否在棋盘内且尚未访问。

boolean is_valid(int xnext,int ynext)
    {
        if(xnext>=0 && xnext<N && ynext>=0 && ynext<N && sol[xnext][ynext]==-1)
        { 
            return true;
        }
        else 
        {
            return false; 
        }
    }

Answer 1

我看不出代码有什么问题。我怀疑它不会进入无限循环，而是进入一个需要很长时间的循环。

看看它是否适用于 5x5 板（动画）。

Answer 2

我看到你在那里使用蛮力，但这还不足以在合理的时间内解决这个问题。如果没有优化，复杂度将是O(N^(N*N))（N 是板尺寸）。因此，找到第一个解决方案可能真的需要很长时间。这就是为什么您认为它处于无限循环中的原因。

最有效的优化是Warnsdorff 的规则，该规则于 1823 年首次发布。它是一种简单的启发式规则，可让您在第一次尝试时（立即）找到解决方案。