计算八大难题中的曼哈顿距离

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让它工作，但似乎不能让它正常工作。我的老师说，使用mod将有助于弄清楚如何做到这一点。我看过的一些例子使用了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]的状态将为7生成(0, 0)，为4生成(2, 0)，依此类推。我将以同样的方式实现目标状态，以获得该状态的x，y坐标。然后我取x-val - x_goal的绝对值，诸如此类。但是，有没有一种更好/更有效的方法直接从列表中执行此操作，而不是使用2for循环来迭代两个列表？

Answer 1

对每个数字的Manhatten距离求和：

>>> 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