Pythonで8パズルを解くためのステップ数を見つけるプログラム

すべての数字が0から8の範囲にあり、繰り返しの数字がない3x3ボードがあるとします。これで、0を4つの隣接ノードのいずれかと交換できます。これを解決して、すべての配置されたシーケンスを取得しようとしています。目標に到達するために必要な最小ステップ数を見つける必要があります。

したがって、入力が次のような場合

その場合、出力は4になります

これを解決するには、次の手順に従います-

• 関数find_next（）を定義します。これはノードを取ります
• moves：=各値に対応するリストとしてmovesを定義するマップ{0：[1、3]、1：[0、2、4]、2：[1、5]、3：[0、4 、6]、4：[1、3、5、7]、5：[2、4、8]、6：[3、7]、7：[4、6、8]、8：[5、7 ]、}
• 結果：=新しいリスト
• pos_0：=ノードの最初の値
• moves [pos_0]の各移動について、実行します
  • new_node：=ノードからの新しいリスト
  • new_node[move]とnew_node[pos_0]を入れ替えます
  • 結果の最後にnew_nodeから新しいタプルを挿入します
• 結果を返す
• 関数get_paths（）を定義します。これには口述が必要です
• cnt：=0
• 次のことを無限に行います。
  • current_nodes：=値がcntと同じリスト
  • current_nodesのサイズが0と同じ場合、
    • 戻り値-1
  • current_nodesのノードごとに、
    を実行します。
    • next_moves：=find_next（node）
    • next_movesの移動ごとに、実行します
      • dictにmoveが存在しない場合は、
        • dict [move]：=cnt + 1
      • 移動が（0、1、2、3、4、5、6、7、8）と同じ場合、
        • return cnt + 1
      • cnt：=cnt + 1
• メインの方法から次の手順を実行します。
• dict：=新しいマップ、フラット化：=新しいリスト
• ボードの行数が0から行数の範囲のiについては、
  • フラット化：=フラット化+ボード[i]
• flatten：=flattenのコピー
• dict [flatten]：=0
• flattenが（0、1、2、3、4、5、6、7、8）と同じ場合、
  • 0を返す
• return get_paths（dict）

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, board):
      dict = {}
      flatten = []
      for i in range(len(board)):
         flatten += board[i]
      flatten = tuple(flatten)

      dict[flatten] = 0

      if flatten == (0, 1, 2, 3, 4, 5, 6, 7, 8):
         return 0

      return self.get_paths(dict)

   def get_paths(self, dict):
      cnt = 0
      while True:
         current_nodes = [x for x in dict if dict[x] == cnt]
         if len(current_nodes) == 0:
            return -1

         for node in current_nodes:
            next_moves = self.find_next(node)
            for move in next_moves:
               if move not in dict:
                  dict[move] = cnt + 1
               if move == (0, 1, 2, 3, 4, 5, 6, 7, 8):
                  return cnt + 1
         cnt += 1

   def find_next(self, node):
      moves = {
         0: [1, 3],
         1: [0, 2, 4],
         2: [1, 5],
         3: [0, 4, 6],
         4: [1, 3, 5, 7],
         5: [2, 4, 8],
         6: [3, 7],
         7: [4, 6, 8],
         8: [5, 7],
      }

      results = []
      pos_0 = node.index(0)
      for move in moves[pos_0]:
         new_node = list(node)
         new_node[move], new_node[pos_0] = new_node[pos_0], new_node[move]
         results.append(tuple(new_node))

      return results
ob = Solution()
matrix = [
   [3, 1, 2],
   [4, 7, 5],
   [6, 8, 0]
]
print(ob.solve(matrix))

入力

matrix = [  
[3, 1, 2],  
[4, 7, 5],  
[6, 8, 0] ]

出力

4