Tags:
graphs

Problem Statement:

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

- a way to get neighbors
- a way to keep track of the number of moves
- a way to know when we hit our target

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[0], cell[1]) == (target_r, target_c):
return count
for new_r, new_c in get_neighbors(cell[0], cell[1]):
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)