LC: Minimum Knight Moves - spiralgo/algorithms GitHub Wiki

Minimum Knight Moves

The Essence:

The path that the knight can move on the board contains patterns. At the most minimum, the knight needs to always move towards the destination. Therefore, a traversal expanding out from the start like sonar waves as well as one going backwards from the end can be used.

When observed more carefully, the patterns actually yield a mathematical formulation, with some parts oscillating between two values, then increments of these two oscillating in the next layer. With this, a constant time mathematical calculation can be formed.

Details:

From the three approaches described here, the first two are implemented using BFS and DFS respectively. These two as well as the mathematical implementation can be found here: https://github.com/spiralgo/algorithms/pull/345