最近在写一个求解数字华容道的程序，用BFS可以求解3x3，但是在往上就不行了
想到了一个分治，就是数字华容道中的降阶法，5x5转4x4再转3x3，但速度还是不行
请问求解数字华容道还有什么速度快的算法？
环境: python 3.8
BFS代码:
from collections import deque, defaultdict
from typing import List
from copy import deepcopy
TARGET = [
[1, 2, 3],
[4, 5, 6],
[7, 8, -1]
] # 定义结果列表
def find_position(target: int, board: List[List[int]]):
"""
寻找一个值在二维列表中的位置。
:param target: 目标值
:param board: 二维列表
:return: 值在二维列表中的位置
"""
for x, i in enumerate(board): # 遍历board，时间复杂度O(n2)
for y, j in enumerate(i):
if j == target:
return x, y
raise ValueError
def find_next(state: str):
"""
给定当前状态，返回可以由当前状态变换而成的状态。
:param state: 当前状态字符串表示
:return: 可以由当前状态变换而成的状态list，保证长度为2-4
"""
board = eval(state) # 转列表
res = []
x, y = find_position(-1, board)
for nx, ny in ((0, 1), (0, -1), (-1, 0), (1, 0)): # 遍历四个方向
tx, ty = nx + x, ny + y
if 0 <= tx < 3 and 0 <= ty < 3: # 在范围内
temp = deepcopy(board) # 二维列表深拷贝一份
temp[x][y], temp[tx][ty] = temp[tx][ty], temp[x][y] # 移动方向上的数字
res.append(str(temp))
return res
def get_parent(board: List[List[int]]):
"""
给定一个盘面，返回运算后的父级关系哈希表。
:param board: 初始盘面，二维列表
:return: 父级关系哈希表
"""
parent = defaultdict(str)
state = str(board) # 字符串可以哈希
visited = {state} # 遍历过的状态
q = deque()
q.append(state)
parent[state] = 'None'
while q: # bfs穷举求解
state = q.popleft()
# print(state)
if state == str(TARGET):
return parent
for nxt in find_next(state):
if nxt not in visited:
q.append(nxt) # 放到待处理队列中
visited.add(nxt)
parent[nxt] = state # 记录关系
return parent
def get_list(ans: List[str]):
"""
对比每个状态，求上下状态中移动方向。
:param ans: 状态列表
:return: 移动方向列表
"""
res = []
for index, item in enumerate(ans):
if index == 0:
continue
item = eval(item)
last = eval(ans[index - 1]) # 上一个状态
lx, ly = find_position(-1, last)
# 上一个状态中空缺位置在这个状态中的数字即为移动的数字
move = item[lx][ly]
nx, ny = find_position(move, last) # 上一个状态中移动数字的位置
if lx - nx == 1:
res.append('down')
elif lx - nx == -1:
res.append('up')
elif ly - ny == 1:
res.append('right')
else:
res.append('left')
# print(last, item, res)
return res
def find_answer(parent: defaultdict, start: str):
"""
给定父级关系哈希表和初始盘面，求移动方向。
:param parent: 父级关系哈希表
:param start: 初始盘面的字符状态
:return: 数字移动方向
"""
ans = [str(TARGET)] # 状态列表
father = parent[str(TARGET)]
while father != start: # 遍历整个树，逆推还原解题过程
ans.append(father)
father = parent[father]
ans.append(str(start))
ans.reverse()
return get_list(ans)
def get_result(board: List[List[int]]):
"""
主函数，给定初始盘面，求数字移动方向。
:param board: 初始盘面
:return: 数字移动方向
"""
parent = get_parent(board)
ans = find_answer(parent, str(board))
return ans
if __name__ == '__main__':
print(get_result(
[[3, 6, 5], [2, 4, 1], [8, 7, -1]]
))
