无限循环运行 C++ 骑士巡回赛问题

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

你想做的是递归函数，但你没有退出条件，所以函数在循环中调用自己。您应该根据函数的目标在函数的某个位置放置 return 。例如：

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/

此外，我建议您使用调试器来了解代码卡住的原因和位置。

希望对您有所帮助:)

无限循环运行 C++ 骑士巡回赛问题

Loop running infinitely C++ for Knight Tour Problem

c++

algorithm

recursion

backtracking

knights-tour

无限循环 运行 C++ 骑士巡回赛问题

Loop running infinitely C++ for Knight Tour Problem

c++

algorithm

recursion

backtracking

knights-tour

无限循环运行 C++ 骑士巡回赛问题