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, coordinates 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 viceversa).
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 coordinates), each of the next cells is visited in Knight steps manner. The traversal is performed using BFS queue, each queue node stores the coordinates 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 xcoordinate of the cell. 2. y: to store ycoordinate of the cell. 3. steps: number of steps required to reach that cell starting from coordinates 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: // ycoordinate int y; // xcoordinate 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 { // ycoordinate int y; // xcoordinate 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.
NonLinear 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(kxtx) , abs(kyty)] = [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 & NonLinear 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 */ // NonLinear 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 & NonLinear 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 */ // NonLinear 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 & NonLinear 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( (kxtx)*(kyty) )]
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( (kxtx)*(kyty) )]
where,
 (kx,ky) = position of Knight
 (tx,ty) = position of Target cell