Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
The Knight and the Shortest Path
2.1.
Program in C
2.2.
Program in C++
2.3.
Program in Python
2.4.
Program in Java
3.
Frequently Asked Questions
3.1.
What is the time complexity and space complexity of the algorithm?
3.2.
Why do we do puzzles in interviews?
3.3.
What is a puzzle interview?
3.4.
What are some of the most typical puzzles posed during an interview?
3.5.
Will puzzles be asked in interviews all the time?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

The Knight and the Shortest Path

Author Abhay Trivedi
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Interview Puzzles

Introduction

We are given a chessboard of N x N size in the knight and the shortest path problem. We have to find the shortest distance (minimum number of steps) a knight takes to reach a given destination from a given source.

Illustration Image

For example, let's have a chessboard of size 8 × 8.

Source = (8, 1)

Destination = (1, 8)

The minimum number of steps needed is 6.

Illustration Image

The Knight and the Shortest Path

The idea is to use BFS(Breadth-first search) as the shortest path problem. Following is the entire algorithm:

  1. Create an empty queue and push(enqueue) the source cell having a distance of 0 from the source (itself).
  2. Loop till the queue is not empty:
  • Dequeue next unvisited node.
  • If the popped(dequeued) node is the destination node, return its distance.
  • Else, we mark the current node as visited. For each of eight possible movements for a knight, push each valid movement with +1 distance (The minimum distance of a node from a source is one more than the minimum distance of the parent from the source).

 

We can find all the possible positions the knight can move to from the given position by using the array that stores the relative position of knight movement from any position. 

For example, if the current position is (x, y), we can move to (x + row[i], y + col[i]) for 0 <= i <= 7 using the arrays:

row[] = [ 2, 2, -2, -2, 1, 1, -1, -1 ]

col[] = [ -1, 1, 1, -1, 2, -2, 2, -2 ]

So, from position (x, y) knight’s can move to are:

(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)

Note that in BFS, all cells having the shortest path as one are visited first, followed by their adjacent cells having the most straightforward path as 1 + 1 = 2 and so on… so if we reach any node in BFS, its shortest path = shortest path of parent + 1. So, the destination cell's first occurrence gives us the result, and we can stop our search there. The shortest path cannot exist from some other cell for which we haven't reached the given node yet. If any such path were possible, we would have already explored it.

Program in C

#include <stdio.h>

struct cell {
	int x, y;
	int dis;
};

int isInside(int x, int y, int n){
	if (x >= 1 && x <= n && y >= 1 && y <= n)
		return 1;
	return 0;
}

int minStepToReachTarget(int knightPos[], int targetPos[], int n){
	int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 };
	int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 };

	struct cell q[1001];
    int front = 1, rear = 1;
    
    struct cell tmp;
    tmp.x = knightPos[0]; tmp.y = knightPos[1]; tmp.dis = 0;
	q[rear] = tmp;
    rear++;

	struct cell t;
	int x, y;
	int visit[n + 1][n + 1];

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			visit[i][j] = 0;

	visit[knightPos[0]][knightPos[1]] = 1;

	while (front != rear){
		t = q[front];
		front++;

		// if current cell is equal to target cell then return its distance
		if (t.x == targetPos[0] && t.y == targetPos[1])
			return t.dis;

		for (int i = 0; i < 8; i++) {
			x = t.x + dx[i];
			y = t.y + dy[i];

			if (isInside(x, y, n) && !visit[x][y]) {
				visit[x][y] = 1;
				struct cell tmp;
                tmp.x = x; tmp.y = y; tmp.dis = t.dis + 1;
				q[rear] = tmp;
				rear++;
			}
		}
	}
}

int main(){
	int N = 8;
	int knightPos[] = {1, 8};
	int targetPos[] = {8, 1};
	printf("%d", minStepToReachTarget(knightPos, targetPos, N));
	return 0;
}

 

Output:

output

Program in C++

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

struct cell {
	int x, y;
	int dis;
	cell() {}
	cell(int x, int y, int dis): x(x), y(y), dis(dis){}
};

bool isInside(int x, int y, int n){
	if (x >= 1 && x <= n && y >= 1 && y <= n)
		return true;
	return false;
}

int minStepToReachTarget(int knightPos[], int targetPos[], int n){
	int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 };
	int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 };

	queue <cell> q;

	q.push(cell(knightPos[0], knightPos[1], 0));

	cell t;
	int x, y;
	bool visit[n + 1][n + 1];

	// makeing all cells unvisited
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			visit[i][j] = false;

	visit[knightPos[0]][knightPos[1]] = true;

	while(!q.empty()) {
		t = q.front();
		q.pop();

		// if current cell is equal to target cell then return its distance
		if(t.x == targetPos[0] && t.y == targetPos[1])
			return t.dis;

		for(int i = 0; i < 8; i++) {
			x = t.x + dx[i];
			y = t.y + dy[i];

			if (isInside(x, y, n) && !visit[x][y]) {
				visit[x][y] = true;
				q.push(cell(x, y, t.dis + 1));
			}
		}
	}
}

int main(){
	int N = 8;
	int knightPos[] = {1, 8};
	int targetPos[] = {8, 1};
	cout << minStepToReachTarget(knightPos, targetPos, N);
	return 0;
}

 

Output: 

output

Program in Python

class cell:
	def __init__(self, x = 0, y = 0, dist = 0):
		self.x = x
		self.y = y
		self.dist = dist

def isInside(x, y, n):
	if (x >= 1 and x <= n and y >= 1 and y <= n):
		return True
	return False


def minStepToReachTarget(knightpos, targetpos, N):
	dx = [2, 2, -2, -2, 1, 1, -1, -1]
	dy = [1, -1, 1, -1, 2, -2, 2, -2]

	queue = []

	queue.append(cell(knightpos[0], knightpos[1], 0))

	visited = [[False for i in range(N + 1)] for j in range(N + 1)]

	visited[knightpos[0]][knightpos[1]] = True

	while(len(queue) > 0): 
		t = queue[0]
		queue.pop(0)

		if(t.x == targetpos[0] and
		t.y == targetpos[1]):
		return t.dist

		for i in range(8):
			x = t.x + dx[i]
			y = t.y + dy[i]
			if(isInside(x, y, N) and not visited[x][y]):
				visited[x][y] = True
				queue.append(cell(x, y, t.dist + 1))


if __name__=='__main__':
	N = 8
	knightpos = [1, 8]
	targetpos = [8, 1]
	print(minStepToReachTarget(knightpos, targetpos, N))

 

Output: 

 output

Program in Java

import java.util.*;

class CN {
	static class cell {
	int x, y;
	int dis;

	public cell(int x, int y, int dis){
		this.x = x;
		this.y = y;
		this.dis = dis;
	}
}

static boolean isInside(int x, int y, int n){
	if (x >= 1 && x <= n && y >= 1 && y <= n)
		return true;
	return false;
}

static int minStepToReachTarget(int knightPos[], int targetPos[], int N){
	int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 };
	int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 };

	Vector<cell> q = new Vector<>();

	q.add(new cell(knightPos[0], knightPos[1], 0));

	cell t;
	int x, y;
	boolean visit[][] = new boolean[N + 1][N + 1];

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			visit[i][j] = false;

	visit[knightPos[0]][knightPos[1]] = true;

	while (!q.isEmpty()) {
		t = q.firstElement();
		q.remove(0);

		if (t.x == targetPos[0] && t.y == targetPos[1])
			return t.dis;

		for (int i = 0; i < 8; i++) {
			x = t.x + dx[i];
			y = t.y + dy[i];

			if (isInside(x, y, N) && !visit[x][y]) {
				visit[x][y] = true;
				q.add(new cell(x, y, t.dis + 1));
			}
		}
	}
	return Integer.MAX_VALUE;
}

	public static void main(String[] args){
    	int N = 8;
    	int knightPos[] = {1, 8};
    	int targetPos[] = {8, 1};
		System.out.println(minStepToReachTarget(knightPos, targetPos, N));
	}
}

 

Output:

output

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is the time complexity and space complexity of the algorithm?

Time complexity: O(N^2). 
In the worst case, we will visit all the cells so that the time complexity is O(N^2).
Auxiliary Space: O(N^2). 
We store the nodes in the queue. So the space Complexity is O(N^2).
Where N indicates the input size.

Why do we do puzzles in interviews?

Usually, interviewers ask puzzles to see how you go about solving a tricky problem. Most companies avoid asking it because most puzzles hinge on a single trick that a person can easily miss when having a bad or nervous day.

What is a puzzle interview?

Microsoft popularized the puzzle interview in the 1990s. Puzzle interviews ask the applicant to solve puzzles like "Why are manhole covers round?" or unusual problems like, "How would you weigh an airplane without a scale?".

What are some of the most typical puzzles posed during an interview?

Some of the most popular interview puzzles are:
Crossing the Bridge Puzzle
The Man in the Elevator Puzzle
Heaven or Hell Puzzle
Three Mislabeled Jars
Gold Bar Cut Puzzle
Man Fell in Well Puzzle
Horses on a Race Track Puzzle
Bag of Coins Puzzle

Will puzzles be asked in interviews all the time?

While most interviewers do not usually ask for puzzles, they are relatively frequent, and some interviews may even include specialized puzzle-solving parts. It is always a good idea to be prepared in case something happens.

Conclusion

This article gives information about the knight and the shortest path puzzle and how puzzles like the knight and the shortest path improve an individual's problem-solving skills. We used the concept of breadth-first traversal to reach the destination from the starting point and thus determine the closest neighbors and possible positions after every move. This way we were able to determine the number of moves the knight would take rather easily and in considerably less amount of time.

Recommended Readings:

Recommended Problems:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Do upvote our blog to help other ninjas grow.

Happy Learning!

Previous article
Monkey and the Coconut Problem
Next article
100 Prisoners with Red and Black Hats
Live masterclass