Minimum steps taken by knight to reach target
You are given a 2D matrix of size N x N which is nothing but a square chessboard. Given the starting and target positions of the knight, you are supposed to return the minimum number of steps required by the knight to reach the target position from the given starting point.

Note :

Following is the possible movements of the knight from a particular position.

Input Format :

The first line of input contains an integer 'T' representing the number of the test case. Then the test cases are as follows. The first line of each test case contains one integer ‘N’ representing the side of the square chessboard or 2D matrix. The second line contains two integers ‘SX’ and ‘SY’ representing the starting position of the knight in the chessboard. The third line contains two integers ‘TX’ and ‘TY’ representing the target position in the chessboard.

Output Format :

For each test case, return the minimum number of steps taken by the knight to reach the target position from the given starting position.

Note :

You do not need to print anything; It has already been taken care of.

Constraints :

1 ≤ T ≤ 50 1 ≤ N ≤ 100 1 ≤ SX,SY,TX,TY ≤ 100 Where ‘T’ is the number of test cases. ‘N’ is the side of the given chessboard or matrix. ‘SX’, ‘SY’, ‘TX’, ‘TY’ denotes the starting and target positions in the given chessboard. Time Limit: 1 sec

Question

Minimum steps taken by knight to reach target

You are given a 2D matrix of size N x N which is nothing but a square chessboard. Given the starting and target positions of the knight, you are supposed to return the minimum number of steps required by the knight to reach the target position from the given starting point.

Note :

Following is the possible movements of the knight from a particular position.

alt text

Input Format :

 The first line of input contains an integer 'T' representing the number of the test case. Then the test cases are as follows.

 The first line of each test case contains one integer ‘N’ representing the side of the square chessboard or 2D matrix.

 The second line contains two integers ‘SX’ and ‘SY’ representing the starting position of the knight in the chessboard.

 The third line contains two integers ‘TX’ and ‘TY’ representing the target position in the chessboard.

Output Format :

For each test case, return the minimum number of steps taken by the knight to reach the target position from the given starting position.

Note :

You do not need to print anything; It has already been taken care of.

Constraints :

1 ≤ T ≤ 50
1 ≤ N ≤ 100
1 ≤ SX,SY,TX,TY ≤ 100

Where ‘T’ is the number of test cases.
‘N’ is the side of the given chessboard or matrix.
‘SX’, ‘SY’, ‘TX’, ‘TY’ denotes the starting and target positions in the given chessboard.

Time Limit: 1 sec

Accepted Answer

Breadth-First Search

Our intuition is to think of all the positions knight can reach from the current position. This problem can be seen as the shortest path in an unweighted graph. Hence, we use BFS to solve this problem.

A knight can move to 8 positions from (x,y).

(x, y) ->

(x + 2, y + 1)

(x + 2, y - 1)

(x - 2, y + 1)

(x - 2, y - 1)

(x + 1, y + 2)

(x + 1, y - 2)

(x - 1, y + 2)

(x - 1, y - 2)

(x,y) will have an edge to the 8 neighbors defined above.

Steps are as follows :

Try all 8 possible positions where a Knight can reach from its position.
If a reachable position is not already visited and is inside the board, we push this state into the queue with a distance of 1 more than its parent state.
Finally, we return the distance of the target position, when it gets pop out from the queue.

This approach considers the implementation of Breadth-First Search for searching through cells, where each cell contains its coordinate and distance from the starting node.

Space Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ denotes the side of the chessboard.

The positions are stored in a queue and since we are using a 2D array to check if a certain cell is visited or not, so the overall space complexity will be O(N^2).

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ denotes the side of the chessboard.

In the worst-case, our approach visits each element of the given chessboard, so the overall time complexity will be O(N^2).

C++ (g++ 5.4)

/*

    Time Complexity = O(N^2)

    Space Complexity = O(N^2)

    

    Where N is the side of the chessboard.

*/



#include 



class cell

{

    public:

    int x, y;

    int distance;

    cell() {}

    cell(int x, int y, int distance)

        : x(x), y(y), distance(distance)

    {

    }

};



bool isInside(int x, int y, int n, vector>&checkVisit)

{

    if (x >= 1 && x <= n && y >= 1 && y <= n)

    {

        if(!checkVisit[x][y])

        {

            checkVisit[x][y]=true;

            return true;

        }

    }



    return false;

}



int minStepsByKnight(int n, int sx, int sy, int tx, int ty)

{

    //    x and y direction, where a knight can move.

    int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};

    int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};



    //    Queue for storing position of knight in the given chess board.

    queue positions;



    //    Push starting position of knight with 0 distance.

    positions.push(cell(sx, sy, 0));



    int x, y;



    vector>checkVisit(n+1,vector(n+1,false));



    checkVisit[sx][sy] = true;



    //    Loop untill we have one element in queue.

    while (!positions.empty())

    {



        cell temp = positions.front();

        positions.pop();



        //    If current cell is equal to target cell, return its distance.

        if (temp.x == tx && temp.y == ty)

        {

            return temp.distance;

        }

        //    Loop for all reachable positions.

        for (int i = 0; i < 8; i++)

        {

            x = temp.x + dx[i];

            y = temp.y + dy[i];



            //    If reachable state is not yet visited and inside board, push that state into queue.

            if (isInside(x, y, n,checkVisit))

            {

                positions.push(cell(x, y, temp.distance + 1));

            }

        }

    }

}

Java (SE 1.8)

/*

    Time Complexity = O(N^2)

    Space Complexity = O(N^2)



    Where N is the side of the chessboard.

*/



import java.util.Queue;

import java.util.ArrayList;

import java.util.LinkedList;



class Cell 

{

    public int x, y;

    public int distance;

    Cell(int x, int y, int distance) 

    {

        this.x = x;

        this.y = y;

        this.distance = distance;

    }

}







public class Solution 

{

    private static boolean isInside(int x, int y, int n, ArrayList> checkVisit) 

    {

        if (x >= 1 && x <= n && y >= 1 && y <= n) 

        {

            if (!checkVisit.get(x).get(y)) 

            {

                checkVisit.get(x).set(y, true);

                return true;

            }

        }



        return false;

    }



    public static int minStepsByKnight(int n, int sx, int sy, int tx, int ty) 

    {

        //    x and y direction, where a knight can move.

        int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2};

        int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1};



        //    Queue for storing position of knight in the given chess board.

        Queue positions = new LinkedList();



        //    Push starting position of knight with 0 distance.

        positions.add(new Cell(sx, sy, 0));



        int x, y;



        ArrayList> checkVisit = new ArrayList>(n + 1);



        for (int i = 0 ; i < n + 1; i++) 

        {

            checkVisit.add(new ArrayList(n + 1));



            for (int j = 0; j < n + 1; j++) 

            {

                checkVisit.get(i).add(false);

            }

        }



        checkVisit.get(sx).set(sy, true);



        //    Loop untill we have one element in queue.

        while (!positions.isEmpty()) 

        {



            Cell temp = positions.remove();



            //    If current Cell is equal to target Cell, return its distance.

            if (temp.x == tx && temp.y == ty) 

            {

                return temp.distance;

            }



            //    Loop for all reachable positions.

            for (int i = 0; i < 8; i++) 

            {

                x = temp.x + dx[i];

                y = temp.y + dy[i];



                //    If reachable state is not yet visited and inside board, push that state into queue.

                if (isInside(x, y, n, checkVisit)) 

                {

                    positions.add(new Cell(x, y, temp.distance + 1));

                }

            }

        }

        return -1;

    }

}

Accepted Answer

Dynamic Programming

Take a close look at the positions of the knight and the target and how will it get affected in different cases:

First of all, let’s talk about the non-linear positions where the knight and the target cells are along different rows and columns (i.e. sx != tx & sy != ty). For example if (sx,sy) = (3,3) and (tx,ty) = (6,6) then only 2 steps are required to reach the target, which are: (3,3) -> (4,5) and (3,3) -> (5,4). So, using dynamic programming, minSteps{(3,3) to (6,6)} = 1 + [minSteps((4,5) to (6,6)) or minSteps((5,4) to (6,6))].

Secondly, if the positions are linear which means if the knight and the target cell are along either same row or columns. i.e. either kx = tx or ky = ty. For example (sx,ky) = (2,4) and (tx,ty) = (7,4) then there are in total 4 steps move towards the target, which are: (2,4) -> (4,5) and (2,4) -> (4,3), both these steps are equivalent and (2,4) -> (3,6) and (2,4) -> (3,2), both these steps are equivalent. So, using dynamic programming, minSteps((2,4) to (7,4)) = 1 + min[minSteps((2,4) to (4,5)) , minSteps((2,4) to (3,6))].

Corner Cases will be if either of the Knight or the target cell is at the corner position and [abs(sx-tx) , abs(sy-ty)] = [1,1]. Then the minimum steps to reach the target will be 4.

The steps are as follows:

Firstly, constitute the solution for corner cases. i.e. when the knight or target is at 4 corners of the board and the difference in their positions are (1,1). The minimum number of moves from source to target is 4. These positions are depicted below:
To define base cases:
When the Knight and the target cell are at adjacent squares (along the same row/column), the minimum number of moves required to reach the destination is 3.
When the Knight and the target cell are at adjacent squares but lie diagonally to each other, the minimum number of moves required to reach the destinations is 2.
When Knight and the target cell are at positions as depicted in the image, the minimum number of moves required to reach the destination is 1.
If the Knight and the target cell are in the same position, the minimum number of moves required is 0.

The Dynamic Programming Equation becomes:

dp[abs(sx – tx)][abs(sy – ty)] = minimum number of steps to reach from knight’s position (sx,sy) to target position (tx,ty).
dp[abs(sx – tx)][abs(sy – ty)] =dp[abs(sy – ty)][abs(sx – tx)].

Space Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ denotes the side of the chessboard.

The size of the dynamic programming table will be of size N X N, so the overall space complexity will be O(N^2).

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ denotes the side of the chessboard.

We are filling 2-d dp matrix that can cost N^2 and we are dealing with only the cells which come in the submatrix formed by the starting and destination cell that will take time O(abs( (SX - TX)*(SY - TY) )). So, the overall time complexity will be O(N^2)

C++ (g++ 5.4)

/*

    Time Complexity = O(N^2)

    Space Complexity = O(N^2)



    Where N is the side of the chessboard.

*/



int minSteps(int sx, int sy, int tx, int ty, vector>&dp)

{

    //    If knight is on the target position return 0.

    if (sx == tx && sy == ty)

    {

        return dp[0][0];

    }

    else

    {



        //    If already calculated then return that value taking the absolute difference.

        if (dp[abs(sx - tx)][abs(sy - ty)] != 0)

        {

            return dp[abs(sx - tx)][abs(sy - ty)];

        }

        else

        {



            //    There will be two distinct positions from the knight towards a target.

            int x1, y1, x2, y2;



            //    (x1, y1) and (x2, y2) are two positions there can be different according to situation. From position of knight, the chess board can be divided into four blocks i.e.. N-E, E-S, S-W, W-N .

            if (sx <= tx)

            {

                if (sy <= ty)

                {

                    x1 = sx + 2;

                    y1 = sy + 1;

                    x2 = sx + 1;

                    y2 = sy + 2;

                }

                else

                {

                    x1 = sx + 2;

                    y1 = sy - 1;

                    x2 = sx + 1;

                    y2 = sy - 2;

                }

            }

            else

            {

                if (sy <= ty)

                {

                    x1 = sx - 2;

                    y1 = sy + 1;

                    x2 = sx - 1;

                    y2 = sy + 2;

                }

                else

                {

                    x1 = sx - 2;

                    y1 = sy - 1;

                    x2 = sx - 1;

                    y2 = sy - 2;

                }

            }



            //    Result will be, 1 + minimum of steps required from (x1, y1) and (x2, y2).

            dp[abs(sx - tx)][abs(sy - ty)] = min(minSteps(x1, y1, tx, ty,dp), minSteps(x2, y2, tx, ty,dp)) + 1;



            //    Exchanging the coordinates x with y of both knight and target will result in same ans.

            dp[abs(sy - ty)][abs(sx - tx)] = dp[abs(sx - tx)][abs(sy - ty)];



            return dp[abs(sx - tx)][abs(sy - ty)];

        }

    }

}



int minStepsByKnight(int n, int sx, int sy, int tx, int ty)

{



    vector> dp(n, vector(n, 0));



    //    The four corner points for which the minimum steps is 4.

    if ((sx == 1 && sy == 1 && tx == 2 && ty == 2) || (sx == 2 && sy == 2 && tx == 1 && ty == 1))

    {

        return 4;

    }

    else if ((sx == 1 && sy == n && tx == 2 && ty == n - 1) || (sx == 2 && sy == n - 1 && tx == 1 && ty == n))

    {

        return 4;

    }

    else if ((sx == n && sy == 1 && tx == n - 1 && ty == 2) || (sx == n - 1 && sy == 2 && tx == n && ty == 1))

    {

        return 4;

    }

    else if ((sx == n && sy == n && tx == n - 1 && ty == n - 1) || (sx == n - 1 && sy == n - 1 && tx == n && ty == n))

    {

        return 4;

    }

    else

    {

        //    dp[a][b], here a, b is the difference of sx & tx and sy & ty respectively.

        dp[1][0] = 3;

        dp[0][1] = 3;

        dp[1][1] = 2;

        dp[2][0] = 2;

        dp[0][2] = 2;

        dp[2][1] = 1;

        dp[1][2] = 1;



        return minSteps(sx, sy, tx, ty, dp);

    }

}

Java (SE 1.8)

/*

    Time Complexity = O(N^2)

    Space Complexity = O(N^2)



    Where N is the side of the chessboard.

*/





import java.util.ArrayList;



public class Solution 

{

    private static int minSteps(int sx, int sy, int tx, int ty, ArrayList> dp) 

    {



        //    If knight is on the target position return 0.

        if (sx == tx && sy == ty) 

        {

            return dp.get(0).get(0);

        } 

        else 

        {



            //    If already calculated then return that value taking the absolute difference.

            if (dp.get(Math.abs(sx - tx)).get(Math.abs(sy - ty)) != 0) 

            {

                return dp.get(Math.abs(sx - tx)).get(Math.abs(sy - ty));

            } 

            else 

            {



                //    There will be two distinct positions from the knight towards a target.

                int x1, y1, x2, y2;



                //    (x1, y1) and (x2, y2) are two positions there can be different according to situation. From position of knight, the chess board can be divided into four blocks i.e.. N-E, E-S, S-W, W-N .

                if (sx <= tx) 

                {

                    if (sy <= ty) 

                    {

                        x1 = sx + 2;

                        y1 = sy + 1;

                        x2 = sx + 1;

                        y2 = sy + 2;

                    } 

                    else 

                    {

                        x1 = sx + 2;

                        y1 = sy - 1;

                        x2 = sx + 1;

                        y2 = sy - 2;

                    }

                } 

                else 

                {

                    if (sy <= ty) 

                    {

                        x1 = sx - 2;

                        y1 = sy + 1;

                        x2 = sx - 1;

                        y2 = sy + 2;

                    } 

                    else 

                    {

                        x1 = sx - 2;

                        y1 = sy - 1;

                        x2 = sx - 1;

                        y2 = sy - 2;

                    }

                }



                //    Result will be, 1 + minimum of steps required from (x1, y1) and (x2, y2).

                dp.get(Math.abs(sx - tx)).set(Math.abs(sy - ty), Math.min(minSteps(x1, y1, tx, ty, dp), minSteps(x2, y2, tx, ty, dp)) + 1);



                //    Exchanging the coordinates x with y of both knight and target will result in same ans.

                dp.get(Math.abs(sy - ty)).set(Math.abs(sx - tx), dp.get(Math.abs(sx - tx)).get(Math.abs(sy - ty)));



                return dp.get(Math.abs(sx - tx)).get(Math.abs(sy - ty));

            }

        }

    }



    public static int minStepsByKnight(int n, int sx, int sy, int tx, int ty) 

    {



        ArrayList> dp = new ArrayList>(n);



        for (int i = 0 ; i < n; i++) 

        {

            dp.add(new ArrayList(n));



            for (int j = 0; j < n; j++) 

            {

                dp.get(i).add(0);

            }

        }



        //    The four corner points for which the minimum steps is 4.

        if ((sx == 1 && sy == 1 && tx == 2 && ty == 2) || (sx == 2 && sy == 2 && tx == 1 && ty == 1)) 

        {

            return 4;

        } 

        else if ((sx == 1 && sy == n && tx == 2 && ty == n - 1) || (sx == 2 && sy == n - 1 && tx == 1 && ty == n)) 

        {

            return 4;

        } 

        else if ((sx == n && sy == 1 && tx == n - 1 && ty == 2) || (sx == n - 1 && sy == 2 && tx == n && ty == 1)) 

        {

            return 4;

        } 

        else if ((sx == n && sy == n && tx == n - 1 && ty == n - 1) || (sx == n - 1 && sy == n - 1 && tx == n && ty == n)) 

        {

            return 4;

        } 

        else 

        {

            //    dp[a][b], here a, b is the difference of sx & tx and sy & ty respectively.

            dp.get(1).set(0, 3);

            dp.get(0).set(1, 3);

            dp.get(1).set(1, 2);

            dp.get(2).set(0, 2);

            dp.get(0).set(2, 2);

            dp.get(2).set(1, 1);

            dp.get(1).set(2, 1);



            return minSteps(sx, sy, tx, ty, dp);

        }

    }

}

You are given a 2D matrix of size N x N which is nothing but a square chessboard. Given the starting and target positions of the knight, you are supposed to return the minimum number of steps required by the knight to reach the target position from the given starting point.

Note :

Input Format :

Output Format :

Note :

Constraints :

Top IQVIA SDE-2 interview questions & answers

Popular interview questions of SDE-2