python - 仅使用国际象棋骑士的 Action 从一个图 block 移动到另一个图 block 的简单算法

Question

我有一个如下所示的问题，它想通过仅使用国际象棋中骑士的移动来找到到达任意两点之间的最快方法。我首先想到的是 A* 算法或 Dijkstra 的 算法，但是，我不知道如何确保只使用马的移动。 如果您能提出更好的算法或一些提示来帮助我，我将不胜感激。谢谢。

Write a function called answer(src, dest) which takes in two parameters: the source square, on which you start, and the destination square, which is where you need to land to solve the puzzle. The function should return an integer representing the smallest number of moves it will take for you to travel from the source square to the destination square using a chess knight's moves (that is, two squares in any direction immediately followed by one square perpendicular to that direction, or vice versa, in an "L" shape). Both the source and destination squares will be an integer between 0 and 63, inclusive, and are numbered like the example chessboard below:

-------------------------| 0| 1| 2| 3| 4| 5| 6| 7|-------------------------| 8| 9|10|11|12|13|14|15|-------------------------|16|17|18|19|20|21|22|23|-------------------------|24|25|26|27|28|29|30|31|-------------------------|32|33|34|35|36|37|38|39|-------------------------|40|41|42|43|44|45|46|47|-------------------------|48|49|50|51|52|53|54|55|-------------------------|56|57|58|59|60|61|62|63|-------------------------

Answer 1

按以下方式解决问题:

第 1 步:构建一个图形，其中棋盘的每个正方形都是一个顶点。

第 2 步:恰好在有一个马从一个方格移动到另一个方格时在顶点之间放置一条边。

第 3 步:应用 Dijkstra 算法。 Dijkstra 算法是一种求两个顶点(正方形)之间的路径长度的算法。