仅使用国际象棋骑士的动作从一个图块移动到另一个图块的简单算法
Simple algorithm to move from one tile to another using only a chess knight's moves
我有一个如下所示的问题，它想通过仅使用国际象棋中骑士的走法来找到到达任意两点之间的最快方法。我的第一个想法是 A* 算法或 Dijkstra's 算法，但是，我不知道如何确保只使用骑士的移动。如果您能提出更好的算法或一些提示来帮助我，我将不胜感激。谢谢。
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|
--------------------------
对于该算法，您需要找到给定节点的所有邻居。使用 divmod https://docs.python.org/3/library/functions.html#divmod 应该很容易将 0-63 符号转换为行和列，从而使骑士移动易于计算
对于这个问题，简单地进行广度优先搜索就足够了（Dijkstra 和 BFS 对未加权图的工作方式相同）。为确保仅使用国际象棋骑士的走法，您必须以正确的方式定义走法。
请注意，国际象棋骑士向任何方向移动两个方格，然后垂直于该方向移动一个方格。这意味着它可以左右移动两个方格，然后向上或向下移动一个方格，或者向上或向下移动两个方格，然后向左或向右移动一个方格。
如果您按行 (0 - 7) 和列 (0 - 7) 而不是 0 - 63 来标识单元格，计算将会容易得多。这可以通过将单元格索引除以 8 并使用商和余数作为行和列索引。因此，如果马现在位于 (x, y) 位置，它的下一个可能位置可以是 (x - 2, y - 1), (x - 2, y + 1), (x + 2, y - 1), (x + 2, y + 1), (x - 1, y - 2), (x - 1, y + 2), (x + 1, y - 2), (x + 1, y + 2) 中的任何一个。请注意，这 8 个单元格可能不在网格内，因此请丢弃掉出棋盘的位置。
按以下方式解决问题：
第1步: 构建一个图形，其中棋盘的每个正方形都是一个顶点。
第 2 步：恰好在有一个马从一个方格移动到另一个方格时在顶点之间放置一条边。
步骤 3：应用 Dijkstra 算法。 Dijkstra算法是求两个顶点（正方形）之间的路径长度的算法。
虽然 User_Targaryen 的答案是最好的，因为它直接回答了你的问题，但如果你的目标是在最短的时间内计算出答案，我会推荐一个代数解决方案。
为了缩短算法，使用关于 x、y 和 xy 轴的反射，以便仅考虑正 (x, y)，其中 x >= y，并将起始移动放在原点，坐标 ( 0, 0).这是可能方向的一个八分圆（八分之一）。
发现解决方案的一个提示是使用方格纸或 Dijkstra 算法，限制到达第一个八分圆中的所有点最多 5 个移动，并将其显示为网格。网格的每个单元格都应标有代表最小移动次数的数字。
如果您想扩展您的问题并需要更多信息，请告诉我。
我有一个如下所示的问题，它想通过仅使用国际象棋中骑士的走法来找到到达任意两点之间的最快方法。我的第一个想法是 A* 算法或 Dijkstra's 算法，但是，我不知道如何确保只使用骑士的移动。如果您能提出更好的算法或一些提示来帮助我，我将不胜感激。谢谢。
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| --------------------------
对于该算法，您需要找到给定节点的所有邻居。使用 divmod https://docs.python.org/3/library/functions.html#divmod 应该很容易将 0-63 符号转换为行和列，从而使骑士移动易于计算
对于这个问题，简单地进行广度优先搜索就足够了（Dijkstra 和 BFS 对未加权图的工作方式相同）。为确保仅使用国际象棋骑士的走法，您必须以正确的方式定义走法。
请注意，国际象棋骑士向任何方向移动两个方格，然后垂直于该方向移动一个方格。这意味着它可以左右移动两个方格，然后向上或向下移动一个方格，或者向上或向下移动两个方格，然后向左或向右移动一个方格。
如果您按行 (0 - 7) 和列 (0 - 7) 而不是 0 - 63 来标识单元格，计算将会容易得多。这可以通过将单元格索引除以 8 并使用商和余数作为行和列索引。因此，如果马现在位于 (x, y) 位置，它的下一个可能位置可以是 (x - 2, y - 1), (x - 2, y + 1), (x + 2, y - 1), (x + 2, y + 1), (x - 1, y - 2), (x - 1, y + 2), (x + 1, y - 2), (x + 1, y + 2) 中的任何一个。请注意，这 8 个单元格可能不在网格内，因此请丢弃掉出棋盘的位置。
按以下方式解决问题：
第1步: 构建一个图形，其中棋盘的每个正方形都是一个顶点。
第 2 步：恰好在有一个马从一个方格移动到另一个方格时在顶点之间放置一条边。
步骤 3：应用 Dijkstra 算法。 Dijkstra算法是求两个顶点（正方形）之间的路径长度的算法。
虽然 User_Targaryen 的答案是最好的，因为它直接回答了你的问题，但如果你的目标是在最短的时间内计算出答案，我会推荐一个代数解决方案。
为了缩短算法，使用关于 x、y 和 xy 轴的反射，以便仅考虑正 (x, y)，其中 x >= y，并将起始移动放在原点，坐标 ( 0, 0).这是可能方向的一个八分圆（八分之一）。
发现解决方案的一个提示是使用方格纸或 Dijkstra 算法，限制到达第一个八分圆中的所有点最多 5 个移动，并将其显示为网格。网格的每个单元格都应标有代表最小移动次数的数字。
如果您想扩展您的问题并需要更多信息，请告诉我。