棋盘上骑士的最短路径

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 chessboard, we want to find the minimum number of steps for a knight to reach a destination position from a source position . 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:

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:

   

Here, we’ve shown the 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 .

3. Approach

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

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

algorithm KSPath(M, N, X, Y, S, T):
    // INPUT
    //    M, N = the size of the chessboard
    //    X, Y = the starting position of the knight
    //    S, T = the destination position
    // OUTPUT
    //    The shortest path from (X, Y) to (S, T)

    dx <- [-2, -1, 1, 2, -2, -1, 1, 2]
    dy <- [-1, -2, -2, -1, 1, 2, 2, 1]
    k <- make an empty queue
    k.push([X, Y])
    visited <- create 2D array of false values (size (M+1) by (N+1))
    visited[X, Y] <- True
    KMove <- create 2D array of 0, size (M+1) by (N+1)

    while k is not empty:
        z <- k.pop()
        if z[0] = S and z[1] = T:
            return KMove[z[0], z[1]]
        for i <- 0 to 7:
            new_x <- z[0] + dx[i]
            new_y <- z[1] + dy[i]
            if OnBoard(new_x, new_y, M, N) and not visited[new_x, new_y]:
                visited[new_x, new_y] <- true
                KMove[new_x, new_y] <- KMove[z[0], z[1]] + 1
                k.push([new_x, new_y])

    return -1

Here, and are two direction arrays that denote the change in the X-direction and the Y-direction. Furthermore, we created a queue and pushed the knight’s initial position .

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

Moreover, we used an array 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, function is defined. Here is the expansion of :

algorithm OnBoard(k, s, M, N):
    // INPUT
    //    k, s = the given position
    //    M, N = the size of the chessboard
    // OUTPUT
    //    Returns true if the position is withinthe chessboard, false otherwise

    if k >= 1 and k <= M and s >= 1 and s <= N:
        return true
    else:
        return false

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 , the time complexity of this algorithm will be .

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.