python搜索问题

请问我的A*算法解决（n2-1）-puzzle问题中为什么当n=3时输出为none？

#coding=utf-8
import copy
import heapq
import numpy as np

# 最终状态
end_state = []

# 方向数组
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

OPEN = []

CLOSE = set() # close表，用于判重

# 输出列表path是移动数字方块的次序
path = []

def print_path(node):
    if node.parent != None:
        print_path(node.parent)
    if node.x != 0:
        path.append(node.x)
    return path

# 状态结点
class Node(object):
    def __init__(self, gn=0, hn=0, state=None, hash_value=None, parent=None, x=0):
       self.gn = gn
       self.hn = hn
       self.fn = self.gn + self.hn
       self.state = state
       self.hash_value = hash_value
       self.parent = parent
       self.x = x
    
    def __lt__(self, node): # heapq的比较函数
        if self.fn == node.fn:
            return self.gn > node.gn
        return self.fn < node.fn

# 启发式函数：求当前各节点到最终坐标的曼哈顿距离之和
def manhattan(state,n):
    M = 0
    for i in range(n):
        for j in range(n):
            if state[i][j] == end_state[i][j] or state[i][j] == 0:
                continue
            else:
                x = (state[i][j] - 1) // n   # 最终坐标
                y = state[i][j] - n * x -1 
                M += (abs(x - i) + abs(y - j))
    return M

def A_star(start, n):
    root = Node(0, 0, start, hash(str(start)), None, 0) # gn, hn, state hash_value, parent
    OPEN.append(root)
    heapq.heapify(OPEN)
    CLOSE.add(root.hash_value)
    while len(OPEN) != 0:
        top = heapq.heappop(OPEN)
        if top.state == end_state:
            return print_path(top)
        for i in range(n):
            for j in range(n):
                if top.state[i][j] != 0:
                    continue
                for d in range(n):
                    new_x = i + dx[d]
                    new_y = j + dy[d]
                    if 0 <= new_x <= n-1 and 0 <= new_y <= n-1:
                        state = copy.deepcopy(top.state)
                        state[i][j] = state[new_x][new_y]
                        state[new_x][new_y] = 0
                        h = hash(str(state))
                        if h in CLOSE:
                            continue
                        CLOSE.add(h)
                        child = Node(top.gn+1, manhattan(state,n), state, h ,top ,state[i][j])
                        heapq.heappush(OPEN, child)
                        

if __name__ == '__main__':
        puzzle = [[1,2,3],[4,5,0],[7,8,6]]
        end_state = [[1,2,3],[4,5,6],[7,8,0]]
        PATH=A_star(puzzle,3)
        print(PATH)

而当n=4时输出正常。

可能是因为 n=3 时的起始状态无法到达最终状态，导致 A* 算法无法找到解。在 n=4 时，使用的起始状态可能是可以到达最终状态的。你可以检查一下起始状态是否有误。