帮我写一个关于python八数码问题的深度与广度搜索及启发式算法代码

好的，下面是代码：

# -*- coding: utf-8 -*-

import copy
import heapq


# 八数码问题的状态类
class State:
    def __init__(self, board, steps=0, is_goal=False):
        self.board = board
        self.steps = steps
        self.is_goal = is_goal
        self.score = self.calc_score()

    # 计算当前状态的评分
    def calc_score(self):
        score = self.steps
        for i in range(3):
            for j in range(3):
                num = self.board[i][j]
                if num == 0:
                    continue
                goal_i, goal_j = (num - 1) // 3, (num - 1) % 3
                score += abs(i - goal_i) + abs(j - goal_j)
        return score

    # 打印当前状态
    def __repr__(self):
        return '\n'.join([' '.join(map(str, row)) for row in self.board])


# 判断状态是否合法
def is_valid_state(state):
    nums = set()
    for i in range(3):
        for j in range(3):
            num = state.board[i][j]
            if num not in nums:
                nums.add(num)
            else:
                return False
    return True


# 获取下一步可能的状态
def get_next_states(state):
    states = []
    for i in range(3):
        for j in range(3):
            if state.board[i][j] == 0:
                if i > 0:
                    new_board = copy.deepcopy(state.board)
                    new_board[i][j], new_board[i-1][j] = new_board[i-1][j], new_board[i][j]
                    new_state = State(new_board, steps=state.steps+1)
                    if is_valid_state(new_state):
                        states.append(new_state)
                if i < 2:
                    new_board = copy.deepcopy(state.board)
                    new_board[i][j], new_board[i+1][j] = new_board[i+1][j], new_board[i][j]
                    new_state = State(new_board, steps=state.steps+1)
                    if is_valid_state(new_state):
                        states.append(new_state)
                if j > 0:
                    new_board = copy.deepcopy(state.board)
                    new_board[i][j], new_board[i][j-1] = new_board[i][j-1], new_board[i][j]
                    new_state = State(new_board, steps=state.steps+1)
                    if is_valid_state(new_state):
                        states.append(new_state)
                if j < 2:
                    new_board = copy.deepcopy(state.board)
                    new_board[i][j], new_board[i][j+1] = new_board[i][j+1], new_board[i][j]
                    new_state = State(new_board, steps=state.steps+1)
                    if is_valid_state(new_state):
                        states.append(new_state)
    return states


# 深度优先搜索
def depth_first_search(start_state, max_depth=50):
    stack = [start_state]
    visited = set()
    while stack:
        state = stack.pop()
        if state.is_goal:
            return state
        if state.steps >= max_depth:
            continue
        visited.add(str(state.board))
        next_states = get_next_states(state)
        for next_state in next_states:
            if str(next_state.board) not in visited:
                stack.append(next_state)
    return None


# 广度优先搜索
def breadth_first_search(start_state):
    queue = [start_state]
    visited = set()
    while queue:
        state = queue.pop(0)
        if state.is_goal:
            return state
        visited.add(str(state.board))
        next_states = get_next_states(state)
        for next_state in next_states:
            if str(next_state.board) not in visited:
                queue.append(next_state)
    return None


# A*搜索
def a_star_search(start_state):
    heap = [(start_state.score, start_state)]
    visited = set()
    while heap:
        state = heapq.heappop(heap)[1]
        if state.is_goal:
            return state
        visited.add(str(state.board))
        next_states = get_next_states(state)
        for next_state in next_states:
            if str(next_state.board) not in visited:
                heapq.heappush(heap, (next_state.score, next_state))
    return None


# 测试
if __name__ == '__main__':
    # 用一个有解的例子测试
    start_board = [[2, 8, 3], [1, 6, 4], [7, 0, 5]]
    goal_board = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
    start_state = State(start_board)
    goal_state = State(goal_board, is_goal=True)

    print('深度优先搜索：')
    result = depth_first_search(start_state)
    if result:
        print('找到解：')
        print(result)
    else:
        print('未找到解')

    print('广度优先搜索：')
    result = breadth_first_search(start_state)
    if result:
        print('找到解：')
        print(result)
    else:
        print('未找到解')

    print('A*搜索：')
    result = a_star_search(start_state)
    if result:
        print('找到解：')
        print(result)
    else:
        print('未找到解')

说明：

1. `State` 类表示八数码问题的一个状态，包括当前的棋盘布局、到达该状态的步数和是否为目标状态。
2. `is_valid_state` 函数用于判断一个状态是否合法，即 1~8 每个数字只出现一次。
3. `get_next_states` 函数用于获取下一步可能的状态。
4. `depth_first_search` 函数实现深度优先搜索。
5. `breadth_first_search` 函数实现广度优先搜索。
6. `a_star_search` 函数实现A*搜索，评估函数为当前步数加上每个数字和其目标位置的曼哈顿距离之和。
7. 最后在 `if __name__ == '__main__':` 中进行测试。