簡單算法從一個瓷磚移動到另一個棋子騎士的移動

Question

我有一個下面顯示的問題，想要找到通過只使用騎士在國際象棋中移動的任何兩點之間的最快方法。我的第一個想法是給我們A*算法或Dijkstra's算法，然而，我不知道如何確保只使用騎士的移動。我會很感激，如果你可以建議一個更好的算法或只是一些提示來幫助我。謝謝。

寫被叫應答（SRC，DEST）函數，它有兩個參數：源廣場上，你開始和目的地廣場，這是你需要的土地，以解決這一難題。該函數應返回一個整數，表示使用棋子的移動將從源方塊移動到目標方塊所需的最小移動次數（也就是說，任何方向的兩個方塊緊跟着一個方塊，然後垂直於該方向或者反之亦然，呈「L」形）。源和目的地廣場將是0到63之間的整數，和編號如下面的例子棋盤：

 
------------------------- 
| 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算法是一種算法，用於查找兩個頂點（正方形）之間的路徑長度。

Answer 2

對於你需要找到所有的鄰居給定節點的算法。使用divmod https://docs.python.org/3/library/functions.html#divmod應該很容易將0-63表示法轉換爲行和列，使得騎士移動起來很容易

Answer 3

對於這個問題，只需進行寬度優先搜索就足夠了（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個單元可能不在網格內，因此請丟棄掉掉網格的位置。

Answer 4

雖然User_Targaryen的答案是最好的，因爲它直接回答你的問題，如果你的目標是計算是在最短的時間內交付答案，我會推薦一個代數解決方案。

要縮短算法，使用關於x，y和xy軸的反射，以便只考慮x> = y的正數（x，y），並將起始移動放置在原點，座標（0 ，0）。這是可能方向的八分之一（八分之一）。

發現解決方案的一個提示是使用圖紙或Dijkstra算法，限制第一個八分區中的所有點達到5個移動，並將其顯示爲網格。網格中的每個單元都應該標有代表最小移動次數的數字。

如果您想擴大您的問題並希望獲得更多信息，請告知我們。