# Minimum Steps to reach target by a Knight

Difficulty Level Hard
Breadth First Search Dynamic Programming Graph Queue

## 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

### 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

// 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);
}
}
}
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

1. 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.
2. Space Complexity: A(n) = O(N^2)
Here we have used BFS, because of which the algorithm has polynomial space complexity.
Clone a Binary Tree with Random Pointers

## Dynamic Programming

### Approach

Consider the points below to understand the problem approach:

1. The chess board is a standard N x N square.
2. kx & ky are the coordinates of the Knight.
3. 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.

1. ex: (kx,ky) = (3,3) & (tx,ty) = (6,6)
2. Only 2 steps move towards the target, which are:
• (3,3) -> (4,5)  and (3,3) -> (5,4)
3. 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.

1. ex: (kx,ky) = (2,4) & (tx,ty) = (7,4)
2. 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
3. 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:

The following code snippet denotes the base cases:

The Dynamic Programming Equation using tabulation becomes:

1. table[abs(kx – tx)][abs(ky – ty)] = minimum number of steps to reach from knight’s position (kx,ky) to target position (tx,ty).
2. table[abs(kx – tx)][abs(ky – ty)] = table[abs(ky – ty)][abs(kx – tx)].
Longest Subarray Having Count of 1s One More than Count of 0s

### Algorithm

```1. Define the solution for corner cases. i.e. when the knight or target are at 4 corners of the board and difference in their positions are (1,1). The minimum number of moves from source to target is 4. These positions are depicted below:
2. Define the base cases as discussed below:
1. when the Knight & target are at adjacent squares (along the same row/column), minimum number of moves required to reach the destination is 3.
2. when the Knight & target are at adjacent squares but lie diagonally to each other, minimum number of moves required to reach the destinations is 2.
3. when Knight & target are at positions as depicted in the image, minimum number of moves required to reach destination is 1.
4. If the Knight & target are at same position, minimum number of moves required is 0.
3. For any other case, refer Linear Positions & Non-Linear Positions in the approach section.```

### Code

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

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

int minStepsRecur(int kx, int ky, int tx, int ty, vector<vector<int>>& table)
{
// when Knight & Target are at same position
if (kx == tx && ky == ty)
return table;

else
{
// if value in the table has been calculated already
if (table[abs(kx - tx)][abs(ky - ty)] != 0)
return table[abs(kx - tx)][abs(ky - ty)];

// Linear Positions
/* Knight can move to -->2 different squares<-- that goes towards the Target */

// Non-Linear Positions
/* Knight can move to 4 different squares that
goes towards the Target of which -->2 are equivalent<-- */

// For every position of Knight & Target
// there are 2 different positions i.e. (x1,y1) & (x2,y2), the Knight can move to.
else
{

int x1, y1, x2, y2;

// the values of (x1,y1) & (x2,y2) depend upon relative positions of Knight & Target
// (x1,y1) & (x2,y2) are midway between (kx,ky) & (tx,ty)
// Their calculations are made accordingly
if (kx <= tx)
{
if (ky <= ty)
{
x1 = kx + 2;
y1 = ky + 1;
x2 = kx + 1;
y2 = ky + 2;
}
else
{
x1 = kx + 2;
y1 = ky - 1;
x2 = kx + 1;
y2 = ky - 2;
}
}

else
{
if (ky <= ty)
{
x1 = kx - 2;
y1 = ky + 1;
x2 = kx - 1;
y2 = ky + 2;
}
else
{
x1 = kx - 2;
y1 = ky - 1;
x2 = kx - 1;
y2 = ky - 2;
}
}

// The minimum steps from (kx,ky) to (tx,ty) = 1 + minimum of steps from (x1, y1) to (x2, y2).
table[abs(kx - tx)][abs(ky - ty)] = 1 + min(minStepsRecur(x1, y1, tx, ty, table),minStepsRecur(x2, y2, tx, ty, table));

// exchanging the coordinates x with y of both knight and target will result in same min moves.
table[abs(ky - ty)][abs(kx - tx)] = table[abs(kx - tx)][abs(ky - ty)];

return table[abs(kx - tx)][abs(ky - ty)];
}
}
}

int minSteps(int kx, int ky, int tx, int ty, int n)
{
// Corner Cases
if ((kx == 1 && ky == 1 && tx == 2 && ty == 2) || (kx == 2 && ky == 2 && tx == 1 && ty == 1))
return 4;

else if ((kx == 1 && ky == n && tx == 2 && ty == n - 1) || (kx == 2 && ky == n - 1 && tx == 1 && ty == n))
return 4;

else if ((kx == n && ky == 1 && tx == n - 1 && ty == 2) || (kx == n - 1 && ky == 2 && tx == n && ty == 1))
return 4;

else if ((kx == n && ky == n && tx == n - 1 && ty == n - 1) || (kx == n - 1 && ky == n - 1 && tx == n && ty == n))
return 4;

else
{
vector <int> row(20,0);
vector <vector<int>> table;

for(int i=0; i<20; i++)
table.push_back(row);

// Base Cases
table = 1;
table = 1;

table = 2;
table = 2;
table = 2;

table = 3;
table = 3;

// Linear & Non-Linear positions
return minStepsRecur(kx, ky, tx, ty, table);
}
}

int main()
{
int n = 8;
int kx = 2, ky = 8, tx = 8, ty = 4;

cout<<"Number of steps : "<<minSteps(kx,ky,tx,ty,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
{
static int minStepsRecur(int kx, int ky, int tx, int ty, int [][] table)
{
// when Knight & Target are at same position
if (kx == tx && ky == ty)
return table;

else
{
// if value in the table has been calculated already
if (table[Math.abs(kx - tx)][Math.abs(ky - ty)] != 0)
return table[Math.abs(kx - tx)][Math.abs(ky - ty)];

// Linear Positions
/* Knight can move to -->2 different squares<-- that goes towards the Target */

// Non-Linear Positions
/* Knight can move to 4 different squares that
goes towards the Target of which -->2 are equivalent<-- */

// For every position of Knight & Target
// there are 2 different positions i.e. (x1,y1) & (x2,y2), the Knight can move to.
else
{

int x1, y1, x2, y2;

// the values of (x1,y1) & (x2,y2) depend upon relative positions of Knight & Target
// (x1,y1) & (x2,y2) are midway between (kx,ky) & (tx,ty)
// Their calculations are made accordingly
if (kx <= tx)
{
if (ky <= ty)
{
x1 = kx + 2;
y1 = ky + 1;
x2 = kx + 1;
y2 = ky + 2;
}
else
{
x1 = kx + 2;
y1 = ky - 1;
x2 = kx + 1;
y2 = ky - 2;
}
}

else
{
if (ky <= ty)
{
x1 = kx - 2;
y1 = ky + 1;
x2 = kx - 1;
y2 = ky + 2;
}
else
{
x1 = kx - 2;
y1 = ky - 1;
x2 = kx - 1;
y2 = ky - 2;
}
}

// The minimum steps from (kx,ky) to (tx,ty) = 1 + minimum of steps from (x1, y1) to (x2, y2).
table[Math.abs(kx - tx)][Math.abs(ky - ty)] = 1 + Math.min(minStepsRecur(x1, y1, tx, ty, table),minStepsRecur(x2, y2, tx, ty, table));

// exchanging the coordinates x with y of both knight and target will result in same min moves.
table[Math.abs(ky - ty)][Math.abs(kx - tx)] = table[Math.abs(kx - tx)][Math.abs(ky - ty)];

return table[Math.abs(kx - tx)][Math.abs(ky - ty)];
}
}
}

static int minSteps(int kx, int ky, int tx, int ty, int n)
{
// Corner Cases
if ((kx == 1 && ky == 1 && tx == 2 && ty == 2) || (kx == 2 && ky == 2 && tx == 1 && ty == 1))
return 4;

else if ((kx == 1 && ky == n && tx == 2 && ty == n - 1) || (kx == 2 && ky == n - 1 && tx == 1 && ty == n))
return 4;

else if ((kx == n && ky == 1 && tx == n - 1 && ty == 2) || (kx == n - 1 && ky == 2 && tx == n && ty == 1))
return 4;

else if ((kx == n && ky == n && tx == n - 1 && ty == n - 1) || (kx == n - 1 && ky == n - 1 && tx == n && ty == n))
return 4;

else
{
int [][] table = new int;

// Base Cases
table = 1;
table = 1;

table = 2;
table = 2;
table = 2;

table = 3;
table = 3;

// Linear & Non-Linear positions
return minStepsRecur(kx, ky, tx, ty, table);
}
}

public static void main (String[] args)
{
int n = 8;
int kx = 2, ky = 8, tx = 8, ty = 4;

System.out.println("Number of steps : "+minSteps(kx,ky,tx,ty,n));
}
}```
`Number of steps : 4`

### Complexity Analysis

1. Time Complexity: T(n) = O[abs( (kx-tx)*(ky-ty) )]
Because we are dealing with only the cells which come in the submatrix formed by starting and destination cell. So, even though this solution also has quadratic time complexity similar to the above solution.
2. Space Complexity: A(n) = O[abs( (kx-tx)*(ky-ty) )]