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+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告