Почему мое решение не может решить задачу 8puzzle для досок, требующих более 1 хода?

Я пытаюсь решить 8 задач на Python, приведенных здесь в этом задании -https://www.cs.princeton.edu/courses/archive/fall12/cos226/assignments/8puzzle.html

Мое целевое состояние немного отличается от того, что указано в задании -

#GOAL STATE
goal_state =  [[0,1,2],[3,4,5],[6,7,8]]

Глючная часть, похоже, связана с функцией isSolvable. Он реализован корректно, но при тестировании доски считает целевым состоянием состояние, в котором сохраняется относительный порядок, а пустое место может быть где угодно. Таким образом, может случиться так, что доска разрешима, но она может не привести к текущему определенному целевому состоянию. Поэтому я не могу придумать метод, с помощью которого я мог бы проверить все возможные целевые состояния во время выполнения решающей функции *

Кроме того, моя функция решения была неправильно реализована. Я рассматривал только того соседа, у которого было минимальное манхэттенское значение, и когда я зашел в тупик, я не рассматривал другие штаты. Это можно сделать с помощью приоритетной очереди. Я не совсем уверен, как приступить к его реализации. Я написал его часть (см. ниже), что также неправильно, поскольку я не помещал родителя в кучу. Пожалуйста, дайте мне руководство для этого.

Вот мой полный код: https://pastebin.com/q7sAKS6a

Обновленный код с неполной функцией решения - https://pastebin.com/n4CcQaks

Я использовал манхэттенские значения для расчета эвристических значений и значение Хэмминга для устранения ничьей.

моя функция isSolvable, функция Манхэттена и функция решателя:

Разрешимая функция -

#Conditions for unsolvability -->
#https://www.geeksforgeeks.org/check-instance-8-puzzle-solvable/
    def isSolvable(self):
        self.one_d_array = []

        for i in range(0,len(self.board)):
            for j in range(0,len(self.board)):
                self.one_d_array.append(self.board[i][j])

        inv_count = 0
        for i in range(0,len(self.one_d_array)-1):
            for j in range(i+1, len(self.one_d_array)):
                if (self.one_d_array[i] != 0 and self.one_d_array[j] != 0 and self.one_d_array[i] > self.one_d_array[j]):
                    inv_count = inv_count + 1

        if(inv_count % 2 == 0):
            print("board is solvable")
            return True
        else:
            print("board is not solvable")
            return False

Манхэттенская функция

    def manhattan_value(self,data=None):
        manhattan_distance = 0
        for i in range(0,len(data)):
            for j in range(0,len(data)):
                if(data[i][j] != self.goal_state[i][j] and data[i][j] != 0):
                    #correct position of the element
                    x_goal , y_goal = divmod(data[i][j],3)
                    manhattan_distance = manhattan_distance + abs(i-x_goal) + abs(j-y_goal)

        return manhattan_distance

Обновленная функция решения

    #implement A* algorithm
    def solver(self):
        moves = 0
        heuristic_value = []
        prev_state = []
        curr_state = self.board
        output = []
        heap_array = []
        store_manhattan_values = []


        if(curr_state == self.goal_state):
            print("goal state reached!")
            print(curr_state)
            print("number of moves required to reach goal state --> {}".format(moves))

        else:
            while(True):
                min_heuristic_value = 99999999999
                min_pos = None
                moves = moves + 1
                output = self.get_neighbours(curr_state)

                for i in range(len(output)):
                    store_manhattan_values.append([self.manhattan_value(output[i]),i])

                #print(store_manhattan_values)
                for i in range(len(store_manhattan_values)):
                    heapq.heappush(heap_array,store_manhattan_values[i])

                #print(heap_array)
                #print(heapq.heappop(heap_array)[1])


                #if(moves > 1):
                #    return
            return

Перейдите по ссылке PASTEBIN для получения полного кода и всех ссылок (https://pastebin.com/r7TngdFc).

Обновленный код с неполной функцией решения - https://pastebin.com/n4CcQaks

В данной ссылке для моего кода (на основе моих тестов и отладки до сих пор) - эти функции работают правильно - manhatten_value, hamming_value, append_in_list, get_neighbours

Что делают эти функции -

isSolvable — сообщает, можно ли решить доску или нет.

manhattan_value — вычисляет манхэттенское значение переданной ему доски.

hamming_value — вычисляет значение hamming переданной ему доски.

append_in_list — вспомогательная функция для получения соседей. Он меняет значения местами, затем сохраняет результирующее состояние в массиве, а затем меняет их местами, чтобы вернуться в исходное положение для дальнейшего обмена и получения других возможных состояний.

get_neighbours — получает всех возможных соседей, которые можно сформировать, поменяв местами пустой элемент (0 элемент).

решатель — реализует алгоритм A*

Я не могу найти свою ошибку. Пожалуйста, направьте меня в этой проблеме. Заранее спасибо за вашу помощь!

Я заранее извиняюсь, так как я не могу создать минимальную версию моего кода для этой проблемы. Никак не могу придумать, как использовать все функции и выдать минимальную версию кода.