Teaching Kids Programming – Top Down Dynamic Programming Algorithm to Compute the Min Number of Knight Moves

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given two integers r and c. Given that knight is placed initially at the coordinate (0, 0) in an infinitely large chess board, return the minimum number of moves it would take to reach (r, c).

Constraints
0 ≤ r, c ≤ 300
Example 1
Input
r = 1
c = 0
Output
3
Explanation
One possible sequence of moves is (0, 0) → (2, 1) → (0, 2) → (1, 0)

In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0]. A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Return the minimum number of steps needed to move the knight to the square [x, y]. It is guaranteed the answer exists.

Example 1:
Input: x = 2, y = 1
Output: 1
Explanation: [0, 0] → [2, 1]

Example 2:
Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

Constraints:
|x| + |y| <= 300

Hints:
You can simulate the movements since the limits are low.
Is there a search algorithm applicable to this problem?
Since we want the minimum number of moves, we can use Breadth First Search.

Top DP Algorithm to Compute the Min Number of Knight Moves

If the board is finite (given sizes), we can use the Breadth First Search Algorithm to find the minimum number of moves from a Knight position to jump back to origin. However, given the board is unbounded, the search space is infite, search algorithms are not practical due to time and space (compute RAM) limitation.

We can however, use Top Down Dynamic Programming Algorithm which can be implemented easily with Recursion + Memoization. We can turn the negative coordinates to position ones, as the distance cost won’t change if the knight position is mirrored with X-axis or Y-axis.

Then, we can pick the minimum of the cost from (x-1,y-2) and (x-2,y-1) and the answer would be plus one of the less.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        @cache
        def dfs(x, y):
            if x == 0 and y == 0:
                return 0
            elif (x, y) in ((1, 1), (0, 2), (2, 0)):
                return 2
            else:
                return min(dfs(abs(x - 1), abs(y - 2)), dfs(abs(x - 2), abs(y - 1))) + 1
        return dfs(abs(x), abs(y))

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        @cache
        def dfs(x, y):
            if x == 0 and y == 0:
                return 0
            elif (x, y) in ((1, 1), (0, 2), (2, 0)):
                return 2
            else:
                return min(dfs(abs(x - 1), abs(y - 2)), dfs(abs(x - 2), abs(y - 1))) + 1
        return dfs(abs(x), abs(y))

Remember that we have to turn every coordinate into non-negative using the abs function.

–EOF (The Ultimate Computing & Technology Blog) —