Loop running infinitely C++ for Knight Tour Problem

Question

I'm coding the Knight Tour problem in C++. But the is running indefinitely. I checked my logic and is similar to the logic mentioned 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);

}

Can someone tell me what's wrong with this code? When I checked the intermediate status of the array it was just working fine. Is it because the algorithm is complex and hence it is running for a longer time and I'm mistaking it as an infinite loop? I checked this answer which describes how complex this problem is.

Answer 1

what you are trying to do is recursive function but you do not have exit condition so the function calls itself in a loop. You should put a return in someplace in your function according to the target of your function. for example:

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

(this is an example I don't know what is your condition)

if you want to learn more about recursive functions here are websites:

https://beginnersbook.com/2017/08/cpp-recursion/#:~:text=The%20process%20in%20which%20a,f(n)%20%3D%201.

https://www.geeksforgeeks.org/recursion/

In addition, I recommend you use your debugger to understand why and where your code get stuck.

Hope that was helpful :)