Stuck at minimum knight's move to reach the end position

Question

I am solving this question:

Find the minimum number of steps required by the knight to move from the starting position to the end position in a nXn chess board. If the path does not exists, then return -1

I have written the below code:

def is_position_safe(n, cur_row, cur_col):
    if 0 <= cur_row < n and 0 <= cur_col < n:
        return True
    else:
        return False


def min_moves(n, cur_row, cur_col, end_row, end_col, visited):
    if cur_row == end_row and cur_col == end_col:
        return 0

    key = tuple([cur_row, cur_col])

    visited_temp = visited.copy()
    if is_position_safe(n, cur_row, cur_col) and key not in visited:
        visited_temp.append(key)
        d1 = min_moves(n, cur_row - 2, cur_col - 1, end_row, end_col, visited_temp)
        d2 = min_moves(n, cur_row - 2, cur_col + 1, end_row, end_col, visited_temp)
        d3 = min_moves(n, cur_row - 1, cur_col - 2, end_row, end_col, visited_temp)
        d4 = min_moves(n, cur_row - 1, cur_col + 2, end_row, end_col, visited_temp)
        d5 = min_moves(n, cur_row + 1, cur_col - 2, end_row, end_col, visited_temp)
        d6 = min_moves(n, cur_row + 1, cur_col + 2, end_row, end_col, visited_temp)
        d7 = min_moves(n, cur_row + 2, cur_col - 1, end_row, end_col, visited_temp)
        d8 = min_moves(n, cur_row + 2, cur_col + 1, end_row, end_col, visited_temp)

        return  min(d1, d2, d3, d4, d5, d6, d6, d7, d8) + 1
    else:
        return float('inf')


def min_knight_moves(n, cur_row, cur_col, end_row, end_col):
    result = min_moves(n, cur_row, cur_col, end_row, end_col, [])

    if result != float('inf'):
        return result
    else:
        return -1

print(min_knight_moves(10, 9, 9, 6, 3))

It is not working in some cases. Example, for the above one it is returning me 5, but the actual answer is 3.

I am not able to understand where I am doing wrong. Could anybody please help me.

P.S.: I know there are existing solutions out there, by using BFS, but I was trying this problem with recursion. I am not quite sure, where I am wrong. Appreciate your help. Thanks!

An issue: when you calculate `d1`, you modify `visited` and `memo`. It affects the following calculations of `d2`, ... — Damien, Apr 13 '22 at 12:16

Tomer Geva · Accepted Answer · 2022-04-13T20:13:52.013

Memoization might not be the best case since a knight can reach a certain spot from different paths and for each path there is a different visited set. Therefore I would suggest creating a visited_temp = visited.copy() and forward that into the recursion without uaing the memoization.

visited_temp = visited.copy()
    if is_position_safe(n, cur_row, cur_col) and key not in visited:
        visited_temp.append(key)
        d1 = min_moves(n, cur_row - 2, cur_col - 1, end_row, end_col, visited_temp)
        d2 = min_moves(n, cur_row - 2, cur_col + 1, end_row, end_col, visited_temp)
        d3 = min_moves(n, cur_row - 1, cur_col - 2, end_row, end_col, visited_temp)
        d4 = min_moves(n, cur_row - 1, cur_col + 2, end_row, end_col, visited_temp)
        d5 = min_moves(n, cur_row + 1, cur_col - 2, end_row, end_col, visited_temp)
        d6 = min_moves(n, cur_row + 1, cur_col + 2, end_row, end_col, visited_temp)
        d7 = min_moves(n, cur_row + 2, cur_col - 1, end_row, end_col, visited_temp)
        d8 = min_moves(n, cur_row + 2, cur_col + 1, end_row, end_col, visited_temp)

        return  min(d1, d2, d3, d4, d5, d6, d6, d7, d8) + 1
    else:
        return float('inf')

This problem is also known as the self avoiding walk problem. I have posted a DFS solution without memoization to the self avoiding walk here but I chose DFS only since all the possible paths were the objective. Self avoiding walk can not have memoization since, as I said, each path has it's own visited set.

Note that since you want with DFS by recursion instead of BFS, your runtime will grow exponentially since you will have to compute all paths before deciding. I you chose the BFS approach you could stop one you reached the destination due tovthe nature of the BFS.

Running the suggested solution

on a 10X10 grid takes a very long time due to the exponential blowup in the runtime so for the following similar example on a lower grid we get:

print(min_knight_moves(5, 4,  4, 2, 0))  # 2

For a grid size 6 or more I killed the run before it ended since it takes so long, recursion in this problem is not a good method for doing this

I tried with this approach, but it is not working unfortunately. I have added `visited` so that I can avoid the loops. In the new code I have popped the last visited position also, but still not helping. — renderMeLater, Apr 13 '22 at 18:32
@renderMeLater Your modified code should work, assuming you wait long enough. I tested on some examples on grids with size of 5 and it seemed to work — Tomer Geva, Apr 13 '22 at 20:17
Yes, because of the exponential time complexity. It's almost `8^n`. — renderMeLater, Apr 15 '22 at 18:00

Stuck at minimum knight's move to reach the end position

1 Answers1

Running the suggested solution