python制作一个可用广度优先算法，深度优先算法和A*算法解决九宫重排问题，要求自己输入初始状态和最终状态

好的，我可以为您提供一个Python程序，实现九宫重排问题的广度优先搜索算法、深度优先搜索算法和A*搜索算法。

其中，广度优先搜索算法和深度优先搜索算法是经典的搜索算法，A*搜索算法则是一种启发式搜索算法，它在保证完备性和最优性的前提下，能够提高搜索效率。

下面是程序的实现，其中包含了三个类，分别是`Node`、`Puzzle`和`Solver`。

- `Node`类表示状态节点，包含了当前状态、父节点、操作序列和状态评估函数等信息。
- `Puzzle`类表示九宫重排问题，包含了初始状态、目标状态和状态转移函数等信息。
- `Solver`类表示求解器，包含了广度优先搜索算法、深度优先搜索算法和A*搜索算法等方法。

程序中使用了Python的`queue`模块实现队列，以及`heapq`模块实现堆。

import queue
import heapq

class Node:
    def __init__(self, state, parent=None, action=None, cost=0, heuristic=0):
        self.state = state
        self.parent = parent
        self.action = action
        self.cost = cost
        self.heuristic = heuristic

    def __lt__(self, other):
        return self.cost + self.heuristic < other.cost + other.heuristic

class Puzzle:
    def __init__(self, start, goal):
        self.start = start
        self.goal = goal

    def actions(self, state):
        i = state.index(0)
        if i == 0:
            return [1, 3]
        elif i == 1:
            return [0, 2, 4]
        elif i == 2:
            return [1, 5]
        elif i == 3:
            return [0, 4, 6]
        elif i == 4:
            return [1, 3, 5, 7]
        elif i == 5:
            return [2, 4, 8]
        elif i == 6:
            return [3, 7]
        elif i == 7:
            return [4, 6, 8]
        elif i == 8:
            return [5, 7]

    def result(self, state, action):
        i = state.index(0)
        j = state.index(action)
        new_state = list(state)
        new_state[i], new_state[j] = new_state[j], new_state[i]
        return tuple(new_state)

    def heuristic(self, state):
        return sum(abs(i // 3 - j // 3) + abs(i % 3 - j % 3)
                   for i, j in ((state.index(i), self.goal.index(i)) for i in range(1, 9)))

class Solver:
    def __init__(self, puzzle):
        self.puzzle = puzzle

    def bfs(self):
        start_node = Node(self.puzzle.start)
        if start_node.state == self.puzzle.goal:
            return start_node
        frontier = queue.Queue()
        frontier.put(start_node)
        explored = set()
        while not frontier.empty():
            node = frontier.get()
            explored.add(node.state)
            for action in self.puzzle.actions(node.state):
                child_state = self.puzzle.result(node.state, action)
                if child_state not in explored:
                    child_node = Node(child_state, node, action, node.cost + 1)
                    if child_node.state == self.puzzle.goal:
                        return child_node
                    frontier.put(child_node)
        return None

    def dfs(self):
        start_node = Node(self.puzzle.start)
        if start_node.state == self.puzzle.goal:
            return start_node
        frontier = [start_node]
        explored = set()
        while frontier:
            node = frontier.pop()
            explored.add(node.state)
            for action in self.puzzle.actions(node.state):
                child_state = self.puzzle.result(node.state, action)
                if child_state not in explored:
                    child_node = Node(child_state, node, action, node.cost + 1)
                    if child_node.state == self.puzzle.goal:
                        return child_node
                    frontier.append(child_node)
        return None

    def astar(self):
        start_node = Node(self.puzzle.start, None, None, 0, self.puzzle.heuristic(self.puzzle.start))
        if start_node.state == self.puzzle.goal:
            return start_node
        frontier = []
        heapq.heappush(frontier, start_node)
        explored = set()
        while frontier:
            node = heapq.heappop(frontier)
            explored.add(node.state)
            for action in self.puzzle.actions(node.state):
                child_state = self.puzzle.result(node.state, action)
                if child_state not in explored:
                    child_node = Node(child_state, node, action, node.cost + 1, self.puzzle.heuristic(child_state))
                    if child_node.state == self.puzzle.goal:
                        return child_node
                    heapq.heappush(frontier, child_node)
        return None

    def solve(self, algorithm):
        if algorithm == 'bfs':
            return self.bfs()
        elif algorithm == 'dfs':
            return self.dfs()
        elif algorithm == 'astar':
            return self.astar()
        else:
            raise ValueError('Invalid algorithm')

接下来，我们可以使用以下代码进行测试：

start_state = tuple(map(int, input('Enter the start state: ').split()))
goal_state = tuple(map(int, input('Enter the goal state: ').split()))

puzzle = Puzzle(start_state, goal_state)
solver = Solver(puzzle)

algorithm = input('Enter the algorithm (bfs, dfs or astar): ')
node = solver.solve(algorithm)
if node is None:
    print('No solution found')
else:
    path = []
    while node is not None:
        path.append(node.action)
        node = node.parent
    path.reverse()
    print('Solution:', path)

在程序运行时，首先输入初始状态和目标状态，然后输入选择的算法（`bfs`表示广度优先搜索算法，`dfs`表示深度优先搜索算法，`astar`表示A*搜索算法）。

程序输出最优解的操作序列，如果找不到解，则输出`No solution found`。

注意：为了方便输入，初始状态和目标状态需要按照从左到右、从上到下的顺序，依次输入每个数字，其中0表示空格。例如，输入`1 2 3 4 5 6 7 8 0`表示初始状态为：

1 2 3
4 5 6
7 8  

输入`1 2 3 4 5 6 7 8 0`表示目标状态为：

1 2 3
4 5 6
7 8  

希望这个程序能够帮助到你。