c++ - 循环无限运行C++以解决Knight Tour问题

Question

我正在用C++编写Knight Tour问题。但是无限期运行。我检查了我的逻辑，并类似于here提到的逻辑

#include<bits/stdc++.h>
using namespace std;

bool isvalid(vector<vector<int>>board,int i,int j)
{
    return i >= 0 && j >= 0 && i < 8 && j < 8 ;
};

bool checkcompletion(vector<vector<int>>board)
{
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
            if(board[i][j]==0)
                return false;
    }
    return true;
}
int tour(vector<vector<int>>board,int i,int j,int steps)
{
    //CHECK IF IT IS A VALID STEP IF NOT VALID THEN RETURN 0
    if(!isvalid(board,i,j))
    {
        return 0;
    }

    //CHECK IF THAT PLACE IS ALREADY VISITED(MOVED OUT OF ISVALID AS THAT FUNCTION ME 
    //GET A OUT OF BOUND REQUEST WHICH WILL CAUSE SEGMENTATION FAULT)
    // cout<<i<<" "<<j<<endl;
    if(board[i][j]!=0) return 0;

    //CHECK IF ALL ARE MARKED FOR TERMINATION
    if(steps==64)return 1;
    //if(checkcompletion(board)) return 1;


    //BACKTRACKING IDEA VARIABLE
    board[i][j]=++steps;

    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
        {
            if(board[i][j]>9)
                cout<<" "<<board[i][j]<<" ";
            else
                cout<<" "<<board[i][j]<<"  ";
        } 
        cout<<"\n";
    }
    cout<<"================================\n";
    tour(board,i+2,j+1,steps);
    tour(board,i+1,j+2,steps);
     tour(board,i-1,j+2,steps);
     tour(board,i-2,j+1,steps);
    tour(board,i-2,j-1,steps);
    tour(board,i-1,j-2,steps);
   tour(board,i+1,j-2,steps);
    tour(board,i+2,j-1,steps);
    
    

    board[i][j]=0;
}

int main()
{
    //for marking the visited part as well as noting the number os steps
    vector<vector<int>>board (8,vector<int>(8,0));
    int steps = 0;

    //MADE steps =1 for 0,0
    //board[0][0]=++steps;
    //initil position 0,0
    tour(board,0,0,steps);

}

有人可以告诉我这段代码有什么问题吗？当我检查阵列的中间状态时，它工作正常。是因为算法复杂，因此运行时间更长，我误认为它是无限循环吗？
我检查了 answer，它描述了此问题的复杂程度。

Answer 1

您试图做的是递归函数，但是您没有退出条件，因此该函数会在循环中自行调用。您应该根据函数的目标将 yield 放在函数的某个位置。例如:

if (tour(board, i + 2, j + 1, steps) == 0)
{
    return steps;
}

(这是一个示例，我不知道您的情况如何)
如果您想了解有关递归函数的更多信息，请访问以下网站:
https://beginnersbook.com/2017/08/cpp-recursion/#:~:text=The%20process%20in%20which%20a,f(n)%20%3D%201。
https://www.geeksforgeeks.org/recursion/
另外，我建议您使用调试器来了解代码为什么以及在哪里卡住。
希望对您有所帮助:)