Python程序：求解8数码难题的步数

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

所以，如果输入像这样：

3
1
2
4
7
5
6
8
0

那么输出将是4

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

  • 定义一个函数find_next()。它将接收节点作为输入
  • 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 := 节点的第一个值
  • 对于moves[pos_0]中的每个移动，执行以下操作：
    • new_node := 从node创建一个新的列表
    • 交换new_node[move]和new_node[pos_0]
    • 将一个新的元组从new_node插入到results的末尾
  • 返回results
  • 定义一个函数get_paths()。它将接收字典作为输入
  • cnt := 0
  • 无限循环执行以下操作：
    • current_nodes := 一个列表，其值为cnt
    • 如果current_nodes的大小为0，则
      • 返回-1
    • 对于current_nodes中的每个节点，执行以下操作：
      • next_moves := find_next(node)
      • 对于next_moves中的每个移动，执行以下操作：
        • 如果move不在字典中，则
          • dict[move] := cnt + 1
        • 如果move等于(0, 1, 2, 3, 4, 5, 6, 7, 8)，则
          • 返回cnt + 1
        • cnt := cnt + 1
  • 从主方法执行以下操作：
  • dict := 一个新的映射，flatten := 一个新的列表
  • 对于从0到棋盘行数的每个i，执行以下操作：
    • flatten := flatten + board[i]
  • flatten := flatten的副本
  • dict[flatten] := 0
  • 如果flatten等于(0, 1, 2, 3, 4, 5, 6, 7, 8)，则
    • 返回0
  • 返回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

更新于: 2020年12月2日

13K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告