## 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**(k****x-tx)** , abs**(k****y-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**:

*table[abs(kx – tx)][abs(ky – ty)]*= minimum number of steps to reach from knight’s position (kx,ky) to target position (tx,ty).*table[abs(kx – tx)][abs(ky – ty)]*= table[abs(ky – ty)][abs(kx – tx)].

### 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[0][0]; 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[2][1] = 1; table[1][2] = 1; table[1][1] = 2; table[2][0] = 2; table[0][2] = 2; table[1][0] = 3; table[0][1] = 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[0][0]; 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[20][20]; // Base Cases table[2][1] = 1; table[1][2] = 1; table[1][1] = 2; table[2][0] = 2; table[0][2] = 2; table[1][0] = 3; table[0][1] = 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

- 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. - Space Complexity: A(n) = O[abs(
**(kx-tx)*(ky-ty)**)]

where,

- (kx,ky) = position of Knight
- (tx,ty) = position of Target cell