Minimum steps to reach target by a Knight

Given a square chessboard of n x n size, the position of the Knight and the position of a target are given. We need to find out the minimum steps a Knight will take to reach the target position.

Examples:

Input:
Knight
knightPosition: (1, 3) , targetPosition: (5, 0)
Output: 3
Explanation: In above diagram Knight takes 3 step to reach
from (1, 3) to (5, 0)
(1, 3) -> (3, 4) -> (4, 2) -> (5, 0)

Try it on GfG Practice

This problem can be seen as the shortest path in an unweighted graph. Therefore, BFS is an appropriate algorithm to solve this problem.

Steps:

Start with the knight's initial position and mark it as visited.
Initialize a queue for BFS, where each entry stores the knight's current position and the distance from the starting position.
Explore all 8 possible moves a knight can make from its current position.
For each move:
Check if the new position is within the board boundaries.
Check if the position has not been visited yet.
If valid, push this new position into the queue with a distance 1 more than its parent.
During BFS, if the current position is the target position, return the distance of that position.
Repeat until the target is found or all possible positions are explored.

C++

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

// structure for storing a cell's data
struct cell {
    int x, y, dis;
    cell() : x(0), y(0), dis(0) {} 
    cell(int x, int y, int dis) : x(x), y(y), dis(dis) {}
};

// Utility method to check if (x, y) is inside the board
bool isInside(int x, int y, int n) {
    return x >= 1 && x <= n && y >= 1 && y <= n;
}

// Method to return the minimum steps to reach target
int minSteps(int knightPos[], int targetPos[], int n) {
    
    // x and y direction where a knight can move
    int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 };
    int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 };

    // queue for storing knight's states
    queue<cell> q;

    // push starting position of knight with 0 distance
    q.push(cell(knightPos[0], knightPos[1], 0));

    cell t;
    int x, y;
    
    // Visit array initialized to false
    vector<vector<bool>> visit(n + 1, vector<bool>(n + 1, false));

    // visit starting position
    visit[knightPos[0]][knightPos[1]] = true;

    // loop until queue is empty
    while (!q.empty()) {
        t = q.front();
        q.pop();

        // if target is reached, return the distance
        if (t.x == targetPos[0] && t.y == targetPos[1])
            return t.dis;

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

            // if the position is valid and not visited, push it to queue
            if (isInside(x, y, n) && !visit[x][y]) {
                visit[x][y] = true;
                q.push(cell(x, y, t.dis + 1));
            }
        }
    }

    // if no path found, return -1
    return -1;
}

int main() {
    int n = 30;
    int knightPos[] = { 1, 1 };
    int targetPos[] = { 30, 30 };
    cout << minSteps(knightPos, targetPos, n);
    return 0;
}

Java

import java.util.*;

// Class to store the cell's data
class Cell {
    int x, y, dis;

    // Default constructor
    Cell() {
        this.x = 0;
        this.y = 0;
        this.dis = 0;
    }

    // Parameterized constructor
    Cell(int x, int y, int dis) {
        this.x = x;
        this.y = y;
        this.dis = dis;
    }
}

public class Solution {

    // Utility method to check if (x, y) is inside the board
    static boolean isInside(int x, int y, int n) {
        return x >= 1 && x <= n && y >= 1 && y <= n;
    }

    // Method to return the minimum steps to reach target
    static int minSteps(int[] knightPos, int[] targetPos, int n) {
        
        // x and y direction where a knight can move
        int[] dx = { -2, -1, 1, 2, -2, -1, 1, 2 };
        int[] dy = { -1, -2, -2, -1, 1, 2, 2, 1 };

        // Queue for storing knight's states
        Queue<Cell> q = new LinkedList<>();

        // Push starting position of knight with 0 distance
        q.add(new Cell(knightPos[0], knightPos[1], 0));

        Cell t;
        int x, y;

        // Visit array initialized to false
        boolean[][] visit = new boolean[n + 1][n + 1];

        // Visit starting position
        visit[knightPos[0]][knightPos[1]] = true;

        // Loop until queue is empty
        while (!q.isEmpty()) {
            t = q.poll();

            // If target is reached, return the distance
            if (t.x == targetPos[0] && t.y == targetPos[1])
                return t.dis;

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

                // If the position is valid and not visited, 
                // push it to the queue
                if (isInside(x, y, n) && !visit[x][y]) {
                    visit[x][y] = true;
                    q.add(new Cell(x, y, t.dis + 1));
                }
            }
        }

        // If no path found, return -1
        return -1;
    }

    // Driver code
    public static void main(String[] args) {
        int n = 30;
        int[] knightPos = { 1, 1 };
        int[] targetPos = { 30, 30 };
        System.out.println(minSteps(knightPos, targetPos, n));
    }
}

Python

# structure for storing a cell's data
class Cell:
    def __init__(self, x=0, y=0, dis=0):
        self.x = x
        self.y = y
        self.dis = dis

# Utility method to check if (x, y) is inside the board
def isInside(x, y, n):
    return 1 <= x <= n and 1 <= y <= n

# Method to return the minimum steps to reach target
def minSteps(knightPos, targetPos, n):
    # x and y direction where a knight can move
    dx = [-2, -1, 1, 2, -2, -1, 1, 2]
    dy = [-1, -2, -2, -1, 1, 2, 2, 1]

    # queue for storing knight's states
    q = []

    # push starting position of knight with 0 distance
    q.append(Cell(knightPos[0], knightPos[1], 0))

    visit = [[False] * (n + 1) for _ in range(n + 1)]

    # visit starting position
    visit[knightPos[0]][knightPos[1]] = True

    # loop until queue is empty
    while q:
        t = q.pop(0)

        # if target is reached, return the distance
        if t.x == targetPos[0] and t.y == targetPos[1]:
            return t.dis

        # explore all reachable positions
        for i in range(8):
            x = t.x + dx[i]
            y = t.y + dy[i]

            # if the position is valid and not visited, push it to queue
            if isInside(x, y, n) and not visit[x][y]:
                visit[x][y] = True
                q.append(Cell(x, y, t.dis + 1))

    # if no path found, return -1
    return -1

# Driver code
if __name__ == '__main__':
    n = 30
    knightPos = [1, 1]
    targetPos = [30, 30]
    print(minSteps(knightPos, targetPos, n))

using System;
using System.Collections.Generic;

// Class to store a cell's data
class Cell
{
    public int x, y, dis;
    public Cell() { x = 0; y = 0; dis = 0; } // Default constructor
    public Cell(int x, int y, int dis) { this.x = x; this.y = y; this.dis = dis; }
}

class Solution
{
    // Utility method to check if (x, y) is inside the board
    static bool IsInside(int x, int y, int n)
    {
        return x >= 1 && x <= n && y >= 1 && y <= n;
    }

    // Method to return the minimum steps to reach target
    static int MinSteps(int[] knightPos, int[] targetPos, int n)
    {
        // x and y directions where a knight can move
        int[] dx = { -2, -1, 1, 2, -2, -1, 1, 2 };
        int[] dy = { -1, -2, -2, -1, 1, 2, 2, 1 };

        // Queue for storing knight's states
        Queue<Cell> q = new Queue<Cell>();

        // Push starting position of knight with 0 distance
        q.Enqueue(new Cell(knightPos[0], knightPos[1], 0));

        Cell t;
        int x, y;

        // Visit array initialized to false
        bool[,] visit = new bool[n + 1, n + 1];

        // Visit starting position
        visit[knightPos[0], knightPos[1]] = true;

        // Loop until queue is empty
        while (q.Count > 0)
        {
            t = q.Dequeue();

            // If target is reached, return the distance
            if (t.x == targetPos[0] && t.y == targetPos[1])
                return t.dis;

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

                // If the position is valid and not visited, push it to queue
                if (IsInside(x, y, n) && !visit[x, y])
                {
                    visit[x, y] = true;
                    q.Enqueue(new Cell(x, y, t.dis + 1));
                }
            }
        }

        // If no path found, return -1
        return -1;
    }

    // Driver code
    static void Main()
    {
        int n = 30;
        int[] knightPos = { 1, 1 };
        int[] targetPos = { 30, 30 };
        Console.WriteLine(MinSteps(knightPos, targetPos, n));
    }
}

JavaScript

// structure for storing a cell's data
class Cell {
    constructor(x, y, dis) {
        this.x = x;
        this.y = y;
        this.dis = dis;
    }
}

// Utility method to check if (x, y) is inside the board
function isInside(x, y, n) {
    return x >= 1 && x <= n && y >= 1 && y <= n;
}

// Method to return the minimum steps to reach target
function minSteps(knightPos, targetPos, n) {
    // x and y direction where a knight can move
    const dx = [-2, -1, 1, 2, -2, -1, 1, 2];
    const dy = [-1, -2, -2, -1, 1, 2, 2, 1];

    // queue for storing knight's states
    const q = [];

    // push starting position of knight with 0 distance
    q.push(new Cell(knightPos[0], knightPos[1], 0));

    let t;
    let x, y;
    
    // Visit array initialized to false
    const visit = Array.from({ length: n + 1 }, () => Array(n + 1).fill(false));

    // visit starting position
    visit[knightPos[0]][knightPos[1]] = true;

    // loop until queue is empty
    while (q.length > 0) {
        t = q.shift();

        // if target is reached, return the distance
        if (t.x === targetPos[0] && t.y === targetPos[1])
            return t.dis;

        // explore all reachable positions
        for (let i = 0; i < 8; i++) {
            x = t.x + dx[i];
            y = t.y + dy[i];

            // if the position is valid and not visited, push it to queue
            if (isInside(x, y, n) && !visit[x][y]) {
                visit[x][y] = true;
                q.push(new Cell(x, y, t.dis + 1));
            }
        }
    }

    // if no path found, return -1
    return -1;
}

// Driver code
const n = 30;
const knightPos = [1, 1];
const targetPos = [30, 30];
console.log(minSteps(knightPos, targetPos, n));

Output

Time complexity: O(n²)
Auxiliary Space: O(n²)

Related Articles:

Minimum steps to reach target by a Knight | Set 2

Minimum steps to reach target by a Knight | Set 1

Explore