[FIXED] Why is my code giving segmentation fault error?

Issue

Step By Knight problem:

Given a square chessboard, the initial position of Knight and position of a target. Find out the minimum steps a Knight will take to reach the target position.

Note: The initial and the target position coordinates of Knight have been given according to 1-base indexing.

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


class Solution 
{
    public:
    //Function to find out minimum steps Knight needs to reach target position.
    int ans = -1;
    
    
    void func(int x, int y, int fr, int fc, int N, int cnt){
        if(x > N || y > N || x < 1 || y < 1){
            return;
        }
        if(x == fr && y == fc){
            if(ans > cnt){
                ans = cnt;
                
            }
            return;
        }
        func(x + 2, y - 1, fr, fc, N, cnt + 1);
        func(x + 2, y + 1, fr, fc, N, cnt + 1);
        func(x - 1, y + 2, fr, fc, N, cnt + 1);
        func(x + 1, y + 2, fr, fc, N, cnt + 1);
        func(x - 2, y + 1, fr, fc, N, cnt + 1);
        func(x - 2, y - 1, fr, fc, N, cnt + 1);
        func(x - 1, y - 2, fr, fc, N, cnt + 1);
        func(x + 1, y - 2, fr, fc, N, cnt + 1);
        
        return;
    }
    
    int minStepToReachTarget(vector<int>&KnightPos,vector<int>&TargetPos,int N)
    {
        int cnt = 0;
       
        func(KnightPos[0], KnightPos[1], TargetPos[0], TargetPos[1], N, cnt);
        return ans;
    }
};


int main(){
    int tc;
    cin >> tc;
    while(tc--){
        vector<int>KnightPos(2);
        vector<int>TargetPos(2);
        int N;
        cin >> N;
        cin >> KnightPos[0] >> KnightPos[1];
        cin >> TargetPos[0] >> TargetPos[1];
        Solution obj;
        int ans = obj.minStepToReachTarget(KnightPos, TargetPos, N);
        cout << ans <<"\n";
    }
    return 0;
}  

INPUT 1

6

4 5

1 1

OUTPUT

Runtime Error

Segmentation Fault (SIGSEGV)

Learn More about Seg Fault

Solution

Your issue is a stack overflow because each level of recursion has no knowledge of what positions have already been checked. Consider this simple example to illustrate:

• The knight makes a move of +2,-1, and you make a recursive call to test this new position.
• While checking this position, the function will test a move of -2,+1

Do you see the problem? These two cases above will oscillate forever, adding more to the stack as you recurse, until you run out of stack and the operating system terminates your process.

Now, it's not enough to simply remember what the last move is and exclude that, because a knight can make multiple moves in succession before arriving back at the same point.

The solution is to create a "board" containing a value for each possible co-ordinate that represents whether that has been visited or not. When you make a move to a valid square, if it is already marked as visited then you must return immediately. Otherwise, you can mark it as visited and continue checking.

Because you probably want to search all possible combinations of moves, then you should also mark the square as not visited before you return from your function.

You can declare your "board" like this:

std::vector<bool> visited(N * N);

And you can index like this:

visited[(y-1)*N + x-1] = true;

For ease, let's store this in the Solution class along with the answer, and make some adjustments:

class Solution 
{
public:
    int minStepToReachTarget(vector<int>& KnightPos, vector<int>& TargetPos, int N)
    {
        ans = -1;
        visited.resize(N * N, false);
        func(KnightPos[0], KnightPos[1], TargetPos[0], TargetPos[1], N, 0);
        return ans;
    }

private:
    void func(int x, int y, int fr, int fc, int N, int cnt);

    int ans;
    vector<bool> visited;
};

Now, the function itself:

void func(int x, int y, int fr, int fc, int N, int cnt)
{
    if(x > N || y > N || x < 1 || y < 1)
    {
        return;
    }

    // Target reached
    if(x == fr && y == fc) {
        ans = cnt;
        return;
    }

    // Prune futile searches
    cnt++;
    if (ans >= 0 && ans <= cnt) return;

    // Search
    int vidx = (y - 1) * N + x - 1;
    if (!visited[vidx])
    {
        visited[vidx] = true;
        func(x + 2, y - 1, fr, fc, N, cnt);
        func(x + 2, y + 1, fr, fc, N, cnt);
        func(x - 1, y + 2, fr, fc, N, cnt);
        func(x + 1, y + 2, fr, fc, N, cnt);
        func(x - 2, y + 1, fr, fc, N, cnt);
        func(x - 2, y - 1, fr, fc, N, cnt);
        func(x - 1, y - 2, fr, fc, N, cnt);
        func(x + 1, y - 2, fr, fc, N, cnt);
        visited[vidx] = false;
    }
}

Notice how the visited flags are being used here.

Also note a couple of extra important changes from above:

    // Target reached
    if(x == fr && y == fc) {
        ans = cnt;
        return;
    }

    // Prune futile searches
    cnt++;
    if (ans >= 0 && ans <= cnt) return;

The first bit simplifies your target-reached scenario. Quite simply, if you reach the target, you know that it's the best answer so far. How? Because of the second bit...

The second bit increments your step count and then checks if this can possibly produce a better answer than what we have already. If not, we stop searching. Such searching would be futile because even if you ultimately reach the target it will not be the shortest path. You should avoid such searches, because they can blow out your execution time by an insane amount.

Answered By - paddy

Answer Checked By - Cary Denson (PHPFixing Admin)