在八个难题中计算曼哈顿距离

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