Minimum steps to reach target by a Knight in a Chess Board

Given a square chessboard of N x N size, and given any source point, (X1, Y1) and destination point, (X2, Y2) on the chessboard, we need to find whether a Knight can move to the destination or not from the source point.

Example:

In the above diagram, Knight takes 3 steps to reach the destination where T denotes the destination in the chessboard.

Every position in the chessboard is defined by a Coordinate.

class Coordinate {
    int x, y;
    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

This problem can be seen as the shortest path in an unweighted graph. Therefore we use BFS to solve this problem. We try all 8 possible positions where a Knight can reach from its position. If the reachable position is not already visited and is inside the board, we push this state into a queue with distance 1 more than its parent state. Finally, we return distance of the target position, when it gets to pop out from queue. The below code implements BFS for searching through cells, where each cell contains its coordinate and distance from the starting node.

import java.util.Queue;
import java.util.LinkedList;

class Coordinate {
    int x, y;

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

public class Solution {
    public int knight(int N, int M, int x1, int y1, int x2, int y2) {

        // The 8 positions a knight could move to for the current position.
        int[] dx = {-1, -2, -1, -2, 1, 2, 1, 2};
        int[] dy = {-2, -1, 2, 1, -2, -1, 2, 1};

        boolean[][] isVisited = new boolean[N + 1][M + 1];
        Queue<Coordinate> queue = new LinkedList<>();
        queue.add(new Coordinate(x1, y1));
        isVisited[x1][y1] = true;
        int moveCount = 0;

        // BFS to find the minimum number of steps.
        while (!queue.isEmpty()) {
            int nodesAtCurrentBreadth = queue.size();
            // Iterate over the coordinates at current breadth, as
            // moveCount would be increased by 1 per breadth level.
            for (int count = 0; count < nodesAtCurrentBreadth; count++) {
                Coordinate currPos = queue.remove();
                if (currPos.x == x2 && currPos.y == y2) {
                    return moveCount;
                }
                for (int i = 0; i < dx.length; i++) {
                    int newX = currPos.x + dx[i];
                    int newY = currPos.y + dy[i];
                    if (isValid(newX, newY, N, M) && !isVisited[newX][newY]) {
                        queue.add(new Coordinate(newX, newY));
                        isVisited[newX][newY] = true;
                    }
                }
            }
            moveCount++;
        }
        return -1;
    }

    private boolean isValid(int x, int y, int N, int M) {
        if (x <= 0 || y <= 0 || x > N || y > M) {
            return false;
        }
        return true;
    }
}

Complexity Analysis:

  • Time complexity: O(N2).
    At worst case, all the cells will be visited so time complexity is O(N2).

Categories: BFS

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s