在八個難題中計算曼哈頓距離

Question

我正在開發一個程序來解決Python中的八謎問題，其中使用啓發式搜索。我們應該使用的啓發式是曼哈頓距離。因此，對於一個電路板，如：

State   Goal  Different Goal 
7 2 4   1 2 3   1 2 3 
5  6   8  4   4 5 6 
8 3 1   7 6 5   7 8 

曼哈頓距離將4 + 0 + 3 + 3 + 1 + 0 + 2 + 1 = 14

視覺上，它是很容易算一定數量多少空間遠的，但在Python我代表董事會作爲一個列表，所以上面的板子是[7, 2, 4, 5, 0, 6, 8, 3, 1]，目標狀態是[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]。我一直在試圖讓這個工作使用國防部，但似乎無法讓它正常工作。我的老師說使用mod將有助於弄清楚如何做到這一點。我看到的一些示例使用了一個2d數組作爲abs(x_val - x_goal) + abs(y_val - y_goal)，這是合理的，但由於我使用的是列表，我不確定如何實現這個。我目前得到的代碼是：

distance = 0 
xVal = 0 
yVal = 0 
for i in range(len(self.layoutList)): 
    pos = self.layoutList.index(i) 
    if pos i == 0 or pos i == 1 or pos i == 2: 
     xVal = pos 
     yVal = 0 
    if pos i == 3 or pos i == 4 or pos i == 5: 
     xVal = pos - 3 
     yVal = 1 
    if pos i == 6 or pos i == 7 or pos i == 8: 
     xVal = pos - 6 
     yVal = 2 

這會爲每個圖塊生成一個x，y值。所以上面代表[7, 2, 4, 5, 0, 6, 8, 3, 1]的狀態會產生(0, 0)爲7，(2, 0)爲4等等。我將以相同的方式爲目標狀態獲得x，y座標。然後，我將採取x-val-x_goal的絕對值和什麼。但有沒有更好/更有效的方式從列表直接做到這一點，而不是使用2 for循環迭代這兩個列表？

Answer 1

求和每個號碼的曼哈頓距離：

>>> board = [7, 2, 4, 5, 0, 6, 8, 3, 1] 
>>> sum(abs((val-1)%3 - i%3) + abs((val-1)//3 - i//3) 
     for i, val in enumerate(board) if val) 
14 

例如，7屬於在（從零開始）座標（0，2）=（(7-1)%3，(7-1)//3），但是在座標（0,0 ），所以爲它添加abs(0 - 0) + abs(2 - 0)。

對於非標準的目標：

>>> goal = [1, 2, 3, 8, 0, 4, 7, 6, 5] 
>>> sum(abs(b%3 - g%3) + abs(b//3 - g//3) 
     for b, g in ((board.index(i), goal.index(i)) for i in range(1, 9))) 
16