You are given a rows * cols chessboard and a knight that moves like in normal chess. Currently knight is at starting position denoted by start_row th row and start_col th col, and want to reach at ending position denoted by end_row th row and end_col th col.
The goal is to calculate the minimum number of moves that the knight needs to take to get from starting position to ending position.
A knight in chess has a specific pattern of movements. Let’s plot out the ways a knight could move if we were in a grid
One way to approach this problem is to treat the available positions from a box in the chessboard to another box as a graph. All the valid movement slots are a nodes neighbors.
Given that we have to find the shortest number of hops to the target a bfs approach seems appropriate here. Here is a quick reminder of the bfs algo.
def bfs(start): visited = set() q = deque() q.append(start) visited.append(start.val) while q: cur = q.popleft() # fifo print(cur.data) for n in cur.neighbors: if (n.val not in visited): q.append(n) visted.append(n.val)
So we need a couple of modifications to the bfs algo for our original problem
For our neighbors we have 8 available moves but not all of them might be valid (ie might be out of the board)
we can have a check that checks the new positions against the grid size
0 <= new_row < num_of_rows and 0 <= new_col < num_of_cols
For keeping track of the number of moves we can enqueue the number of moves into the queue as well and increment it when a new neighbor gets processed
Putting it all together
from collections import deque DIRECTIONS = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)] def find_minimum_number_of_moves(num_row, num_col, start_r, start_c, target_r, target_c): def get_neighbors(r, c): neighbors =  for direction_r, direction_c in DIRECTIONS: new_r, new_c = r + direction_r, c + direction_c if 0 <= new_r < num_row and 0 <= new_c < num_col: neighbors.append((new_r, new_c)) return neighbors visited = set() q = deque() q.append(((start_r, start_c), 0)) visited.add((start_r, start_c)) while q: cell, count = q.popleft() # fifo if (cell, cell) == (target_r, target_c): return count for new_r, new_c in get_neighbors(cell, cell): if ((new_r, new_c) not in visited): q.append(((new_r, new_c), count + 1)) visited.add((new_r, new_c)) return -1
Time complexity will be
O(n) where n is number of items in the grid (r * c)