数据结构
网络
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+ 浏览量
广告