在Python中找到解决8数码问题的步数的程序

假设我们有一个3×3的棋盘，所有数字的范围都在0到8之间，并且没有重复的数字。现在，我们可以将0与其4个邻居之一交换，并且我们正在尝试解决它以获得所有排列的序列，我们必须找到达到目标所需的最少步数。

因此，如果输入为

3	1	2
4	7	5
6	8	0

那么输出将是4

为了解决这个问题，我们将遵循以下步骤：

• 定义一个函数find_next()，它将接受节点
• 移动：一个定义为将每个值映射到列表的移动列表{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：节点的第一个值
• 对于移动中的每个移动，执行以下操作
  • new_node：从节点创建的新列表
  • 交换new_node [move]和new_node [pos_0]
  • 将新节点的一个新元组插入结果的末尾
• 返回结果
• 定义一个函数get_paths()，它将接受字典
• 计数：0
• 无限制地执行以下操作
  • current_nodes：值与cnt相同的列表
  • 如果current_nodes的大小与0相同，则
    • 返回-1
  • 对于当前节点中的每个节点，执行以下操作：
    • next_moves：查找下一个节点
    • 对于下一个移动中的每个移动，执行以下操作：
    • 如果移动不存在于字典中，则
      • dict [move]：=cnt +1
    • 如果移动与(0,1,2,3,4,5,6,7,8)相同，则
      • 返回cnt +1
    • 计数：=cnt +1
• 从主方法执行以下操作：
• 字典：一个新的映射，flatten：一个新的列表
• 对于i从0到棋盘的行数遍历，执行以下操作：
  • flatten：= flatten + board [i]
• flatten：一个副本
• dict [flatten]：= 0
• 如果flatten与(0,1,2,3,4,5,6,7,8)相同，则
  • 返回0
• 返回get_paths(dict)

让我们看一下以下实现，以更好地理解

更多Python相关文章，请阅读：Python 教程

示例

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

输入

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

输出

4