参考文章：八数码问题，A*算法，启发函数
Python >= 3.10

八数码问题

八数码问题是在3×3的九宫格棋盘上，摆有8个刻有1～8数码的将牌。棋盘中有一个空格，允许紧邻空格的某一将牌可以移到空格中，这样通过平移将牌可以将某一将牌布局变换为另一布局。针对给定的一种初始布局或结构（目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。

A*算法

A*算法是一种启发式图搜索算法，其特点在于对估价函数的定义上。对于一般的启发式图搜索，总是选择估价函数f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的实际代价g(n)以及从节点n到达目标节点的估价代价h(n),且$h(n) \leq h^*(n)$，$h^*(n)$为n节点到目的节点的最佳路径的代价。

代码

所使用的启发函数

def hn(self, a_chess_board:ChessBoard) -> int:
        self.f = self.h = 0
        # h(n)为不在目标状态的数码移到目的位置所需移动的曼哈顿距离的总和
        # D = |X1 - X2| + |Y1 - Y2|
        # X = i // 3
        # Y = i mod 3
        for i in range(0, 9):
            diff_chess_pos = abs(a_chess_board.chess_map.index(i) - self.chess_map.index(i))
#list.index(i):找到数字i在list中的索引，即在当前棋盘中的位置
            self.h += diff_chess_pos // 3 + diff_chess_pos % 3

        self.f = self.g + self.h
        return self.f

所需库

from __future__ import annotations 
# 为的是在类中使用自己的类型注解，在Python3.11中可以直接使用Self
# https://docs.python.org/3/whatsnew/3.11.html#whatsnew311-pep673
from queue import PriorityQueue
from copy import deepcopy
from typing import Literal

定义一个类来记录当前状态(棋盘)

#给该类型定义一个别名方便理解
ChessMap = list[int]

class ChessBoard:

    def __init__(self, chess_map:list[int] = []):
        self.f:int = 0
        self.h:int = 0
        self.g:int = 0

        self.chess_map:ChessMap = chess_map
        self.solution_path:list[ChessMap] = list()

    def __gt__(self, another:ChessBoard):
        # 作为PriorityQueue的排序依据
        return self.f > another.f

    def __eq__(self, another:ChessBoard):
        # 比较chessmap是否相同
        return self.chess_map == another.chess_map

    def __str__(self):
        return "".join(str(i) for i in self.chess_map)

    def get_space_index(self) -> int:
        return self.chess_map.index(0)

    def index2xy(self, index:int) -> tuple[int,int]:
        return (index // 3 ,index % 3)

    def hn(self, a_chess_board:ChessBoard) -> int:
        self.f = self.h = 0
        # h(n)为不在目标状态的数码移到目的位置所需移动的曼哈顿距离的总和
        # D = |X1 - X2| + |Y1 - Y2|
        # X = i // 3
        # Y = i mod 3
        for i in range(0, 9):
            diff_chess_pos = abs(a_chess_board.chess_map.index(i) - self.chess_map.index(i))
#list.index(i):找到数字i在list中的索引，即在当前棋盘中的位置
            self.h += diff_chess_pos // 3 + diff_chess_pos % 3

        self.f = self.g + self.h
        return self.f

定义一个可以操作棋盘的类(代理人)

class Oper:

    moves:dict[str, tuple] = {
        "up": (-1, 0),
        "down": (1, 0),
        "left": (0, -1),
        "right": (0, 1)
    }

    def __init__(self, source:ChessBoard, target:ChessBoard):
        self.source:ChessBoard = source
        self.target:ChessBoard = target
        self.close_list:list[ChessBoard] = list()
        self.open_list:PriorityQueue[ChessBoard] = PriorityQueue()
        self.search_chess_board:ChessBoard = ChessBoard()

    def possible_move(self, chess_board:ChessBoard) ->list[ChessBoard | Literal["overflow"]]:
        space_index = chess_board.get_space_index()
        space_x, space_y = chess_board.index2xy(space_index)
        possible_chess_map:list[ChessBoard | Literal["overflow"]] = []
        for direct in ["up", "down", "left", "right"]:
            new_x = space_x + self.moves[direct][0]
            new_y = space_y + self.moves[direct][1]
            if 0 <= new_x <= 2 and 0 <= new_y <= 2:
                new_chess_board = ChessBoard()
                new_chess_board.chess_map = deepcopy(chess_board.chess_map)
                new_chess_board.solution_path = deepcopy(chess_board.solution_path)
                new_chess_board.chess_map[space_index] = new_chess_board.chess_map[new_x * 3 + new_y]
                new_chess_board.chess_map[new_x * 3 + new_y] = 0
                new_chess_board.g = chess_board.g + 1
                new_chess_board.hn(self.target)
                new_chess_board.solution_path.append(new_chess_board.chess_map)
                possible_chess_map.append(new_chess_board)
            else:
                possible_chess_map.append("overflow")

        return possible_chess_map

    def calculate(self):
        self.source.hn(self.target)
        self.close_list.append(self.source)
        self.open_list.put(self.source)

        while not self.open_list.empty():
            chess_board = self.open_list.get()
            #print(chess_board, " size:%d"%self.open_list.qsize())
            if chess_board.h == 0:
                self.search_chess_board = chess_board
                break
            possible_chess_board_list = self.possible_move(chess_board)
            for pcb in possible_chess_board_list:
                if not isinstance(pcb, ChessBoard):
                    continue

                if pcb not in self.close_list:
                    self.close_list.append(pcb)
                    self.open_list.put(pcb)

        return self.search_chess_board

让代理人解决八数码问题

def print_chess_board(map:ChessMap):
    for i in range(1, 10):
        if map[i-1] == 0:
            print(' ', end=' ')
        else:
            print(map[i-1], end=' ')

        if i % 3 == 0:
            print("")

if __name__ == "__main__":
    source = list(map(int, input("按从左到右从上到下的顺序\n输入初始状态的八数码行：\n")))
    target = list(map(int, input("输入目标状态的八数码行：\n")))

    source_chess_board = ChessBoard(source)
    target_chess_board = ChessBoard(target)

    oper = Oper(source_chess_board, target_chess_board)

    result = oper.calculate()

    step_index = 1
    print("----------------")
    print("起手式：")
    print_chess_board(source_chess_board.chess_map)
    for step in result.solution_path:
        print("step #%d:"%step_index)
        print_chess_board(step)
        print("----------------")
        step_index += 1