The Knight and the Shortest Path

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.

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.

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

You can also try this code with Online C Compiler

Run Code

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

You can also try this code with Online C++ Compiler

Run Code

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

You can also try this code with Online Python Compiler

Run Code

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

You can also try this code with Online Java Compiler

Run Code

Output: