8つのパズルのマンハッタン距離を計算する

Question

私はヒューリスティックな情報検索を使ってPythonの8パズルを解くプログラムに取り組んでいます。私たちが使うはずのヒューリスティックは、マンハッタンの距離です。だから、のようなボード用：

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)の2次元配列を使用しましたが、リストを使用しているので、これを実装する方法がわかりません。私が今までに得たコードは次のとおりです。

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となります。これは、goalstateがx、y座標を取得するのと同じ方法で実装します。それから、私はx-valの絶対値とx_goalとそれ以外のものをとります。しかし、2つのforループを使用して両方のリストを反復するのではなく、リストからこれを直接実行する方が、より効率的な方法がありますか？各番号のManhatten距離にわたって加算

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