資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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
- 如果move不在字典中，則
- 從主方法執行以下操作：
- 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+ 瀏覽量
廣告