Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

1. Overview

In this tutorial, we’ll discuss the knight’s shortest path problem on a chessboard. Furthermore, we’ll explain the problem statement and provide an efficient solution.

2. Problem Statement

Given a standard M \times N chessboard, we want to find the minimum number of steps for a knight to reach a destination position \mathbf{(S, T)} from a source position \mathbf{(X, Y)}. Here, the source and destination position of the knight on a chessboard is known.

Now let’s take a look at the possible movements of a knight from a random position on a chessboard:

fdgfdhg

On a chessboard, a knight can move two ways. It can either move one square horizontally and two squares vertically, or one square vertically and two squares horizontally. Hence, from a given position (X, Y), the possible moves 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)\]

Here, we’ve shown the 8 possible positions on a chessboard a knight can move from a given initial position. At any point in time, a knight can’t go out of the chessboard. Finally, if there is a situation that the knight can’t reach the destination from the given initial position, we’ll return -1.

3. Approach

In order to solve this problem, first, we’ll convert the chessboard to a knight’s graph:

download-1

In a knight’s graph, each box on a chessboard denotes a vertex. Each vertex corresponds to the position of a knight on a chessboard. Each edge represents a legal move of a knight. Hence, we can apply any searching algorithm to find the shortest path from one point to another in order to solve the knight’s shortest path problem. We’re using Breadth-First Search (BFS) algorithm here.

Initially, we’ll position a knight randomly on a chessboard. From the initial point, we’ll aim to explore all possible 8 positions. If all the possible positions which can be reached from the initial position are not visited, we enqueue this state into a queue. Moreover, we increase the number of moves by \mathsf{1} from the last state in the queue.

At each new position, we’ll check if the current position of the knight is the destination position or not. If the current position is not the destination, we’ll pop the current position from the queue and enqueue the possible positions a knight can move from the current position.

We’ll continue until we reach the destination position or explore all the possible positions on a chessboard.

4. Pseudocode

Let’s look at the pseudocode now:

Rendered by QuickLaTeX.com

Here, \mathbf{dx[]} and \mathbf{dy[]} are two direction arrays that denote the change in the X-direction and the Y-direction. Furthermore, we created a queue k and pushed the knight’s initial position (X, Y).

Initially, we created an array visited[] to decide whether a given position on a chessboard is already explored or not.  In the beginning, we initialized it to False in order to depict all the positions are unexplored. When we start the iteration, we make the knight’s initial position in the visited[] array as True.

Moreover, we used an array KMove[] in order to store the number of steps required for a knight to reach the destination position. We run the algorithm until the queue is empty or the destination is reached.

To check whether a given position is inside the chessboard or not, OnBoard() function is defined. Here is the expansion of \mathbf{OnBoard()}:

Rendered by QuickLaTeX.com

Finally, let’s talk about the time complexity of the pseudocode. So the main complexity of this pseudocode is visiting the chessboard cells to reach the destination. If the dimension of the given chessboard is M \times N, the time complexity of this algorithm will be \mathbf{\mathcal{O}(MN)}.

5. Conclusion

In this tutorial, we discussed the knight’s shortest path problem on a chessboard. We presented a BFS based approach for solving this problem with pseudocode.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!