Minimum Steps to reach target by a Knight

Table of Contents

Description

The problem “Minimum Steps to reach target by a Knight” states that you are given a square chess board of N x N dimensions, co-ordinates of the Knight piece, and the target cell. Find out the minimum number of steps taken by the Knight piece to reach the target cell.

Knight Steps: As per the rules of chess, a Knight moves 2 squares in one direction & 1 square in the perpendicular direction (or vice-versa).

Example

(kx,ky) = (1,1) & (tx,ty) = (15,15)

Minimum number of moves = 10

(kx,ky) = (2,8) & (tx,ty) = (8,4)

Minimum number of moves = 4

(kx,ky) = (2,8) & (tx,ty) = (8,4)

Minimum number of moves = 4

Types of Solution

Breadth First Search
Dynamic Programming

Breadth First Search

Approach

The idea is to perform BFS starting from the initial position of the Knight. We proceed to all the next cells (& their next cells) iteratively from a given position (or co-ordinates), each of the next cells is visited in Knight steps manner. The traversal is performed using BFS queue, each queue node stores the co-ordinates of the cell met during BFS traversal along with the number of steps taken to reach that particular cell. Once the target cell is popped from the BFS queue, the value of the number of steps is the required answer.

Algorithm

1. Define a class that has following data variables:
    1. x: to store x-coordinate of the cell.
    2. y: to store y-coordinate of the cell.
    3. steps: number of steps required to reach that cell starting from co-ordinates of the Knight.
2. Create a BFS queue that stores class objects as nodes.
3. Begin the Iterative BFS traversal.
4. In every step of the iterative traversal, pop a node from the queue. say,the node is front.
5. If the cell at coordinates (front.y, front.x) is the target cell, return the value of front.steps.
    1. Else, continue the iterative traversal.

Code

C++ Program to find Minimum Steps to reach target by a Knight

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

// definition of queue node
class Node
{
    public:
    // y-coordinate
    int y;
    // x-coordinate
    int x;
    // number of steps to reach (y,x)
    int steps;
    
    // constructor
    Node(int i,int j,int moves)
    {
        y = i;
        x = j;
        steps = moves;
    }
};

// traversal array along rows
int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
// traversal array along columns
int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1}; 

// BFS to return number of steps required to reach from source to target
int BFS(Node source, Node target, int N)
{
    // set to mark a cell as visited
    unordered_set <string> visited;
    // BFS queue
    queue <Node> q;
    // push the source node
    q.push(source);
    
    // BFS traversal 
    while(!q.empty())
    {
        Node front = q.front();
        q.pop(); 
        
        // if target coordinate is reached
        if(front.y == target.y && front.x == target.x)
        return front.steps;
        
        // traverse all neighbors of current cell
        for(int i=0;i<8;i++)
        {
            int next_y = front.y + dy[i];
            int next_x = front.x + dx[i];
            
            // store coordinates of a cell as string
            string search = to_string(next_y) + '|' + to_string(next_x);
            
            // move to neighbor cell if it is not visited lies within the N x N chessboard
            if(visited.find(search) == visited.end() && next_y > 0 && next_x > 0 && next_y <= N && next_x <= N)
            {
                Node next(next_y,next_x,front.steps+1);
                q.push(next);
                visited.insert(search);
            }
        }
    }
}

int main()
{
    // dimensions of the square chessboard
    int N = 8;
    // coordinates of source & target cell
    Node source(2,8,0), target(8,4,-1);
    cout<<"Number of steps : "<<BFS(source,target,N)<<endl;
    return 0;
}

Number of steps : 4

Java Program to find Minimum Steps to reach target by a Knight

import java.util.*;
import java.io.*;

class TutorialCup 
{
    // definition of queue node
    static class Node
    {
        // y-coordinate
        int y;
        // x-coordinate
        int x;
        // number of steps to reach (y,x)
        int steps;
        
        // constructor
        Node(int i,int j,int moves)
        {
            y = i;
            x = j;
            steps = moves;
        }
    };
    
    // traversal array along rows
    static int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
    // traversal array along columns
    static int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1}; 
    
    // BFS to return number of steps required to reach from source to target
    static int BFS(Node source, Node target, int N)
    {
        // set to mark a cell as visited
        HashSet <String> visited = new HashSet<>();
        // BFS queue
        Queue <Node> q = new LinkedList<>();
        // push the source node
        q.add(source);
        
        // BFS traversal 
        while(!q.isEmpty())
        {
            Node front = q.poll();
            
            // if target coordinate is reached
            if(front.y == target.y && front.x == target.x)
            return front.steps;
            
            // traverse all neighbors of current cell
            for(int i=0;i<8;i++)
            {
                int next_y = front.y + dy[i];
                int next_x = front.x + dx[i];
                
                // store coordinates of a cell as string
                String search = next_y + "|" + next_x;
                
                // move to neighbor cell if it is not visited lies within the N x N chessboard
                if(visited.contains(search) == false && next_y > 0 && next_x > 0 && next_y <= N && next_x <= N)
                {
                    Node next = new Node(next_y,next_x,front.steps+1);
                    q.add(next);
                    visited.add(search);
                }
            }
        }
        return 0;
    }
    public static void main (String[] args)
    {
        // dimensions of the square chessboard
        int N = 8;
        // coordinates of source & target cell
        Node source = new Node(2,8,0);
        Node target = new Node(8,4,-1);
        System.out.println("Number of steps : "+BFS(source,target,N));
    }
}

Number of steps : 4

Complexity Analysis

Time Complexity: T(n) = O(N^2)
Because we have a square matrix and in the worst case. Thus we may have to deal with each of the cells. And that’s how a quadratic time complexity is achieved.
Space Complexity: A(n) = O(N^2)
Here we have used BFS, because of which the algorithm has polynomial space complexity.

Dynamic Programming

Approach

Consider the points below to understand the problem approach:

Consider the assumptions made below:

The chess board is a standard N x N square.
kx & ky are the coordinates of the Knight.
tx & ty are the coordinates of the Target cell.

Non-Linear Positions : If the knight & target cell are along different rows & columns. i.e. kx not= tx & ky not= ty.

ex: (kx,ky) = (3,3) & (tx,ty) = (6,6)
Only 2 steps move towards 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)}]

Linear Positions : If the knight & target cell are along either same row or columns. i.e. either kx = tx or ky = ty.

ex: (kx,ky) = (2,4) & (tx,ty) = (7,4)
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
- (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 : If either of the Knight or Target is at the corner and [abs(kx-tx) , abs(ky-ty)] = [1,1]. Then minimum steps to reach the target will be 4.

The following code snippet denotes the base cases:

Base Cases : the base cases are discussed below: