python - 为什么我的解决方案无法解决需要多于 1 步的棋盘的 8puzzle 问题？

Question

我正在尝试解决此作业中给出的 python 中的 8 个难题 - 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 函数。它实现正确，但在测试电路板时，它认为目标状态是保持相对顺序的状态，空白可以在任何地方。因此，董事会可能是可解决的，但可能不会导致当前定义的目标状态。所以我想不出一种方法可以在运行求解器函数时测试所有可能的目标状态 *

另外，我的求解器函数执行错误。我只考虑曼哈顿值(value)最小的邻居，当我走到死胡同时，我没有考虑其他州。这可以通过使用优先级队列来完成。我不确定如何继续实现它。我已经写了它的一部分(见下文)，这也是错误的，因为我没有将父级插入堆中。请为此提供指导。

这是我的完整代码 - https://pastebin.com/q7sAKS6a

更新了具有不完整求解器功能的代码 - https://pastebin.com/n4CcQaks

我使用曼哈顿值来计算启发式值，并使用汉明值来打破平局。

我的 isSolvable 函数、manhattan 函数和 solver 函数:

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 - 判断棋盘是否可以求解

ma​​nhattan_value - 计算传递给它的棋盘的曼哈顿值。

hamming_value - 计算传递给它的棋盘的汉明值。

append_in_list - 获取邻居的辅助函数。它交换值然后将结果状态保存在数组中，然后重新交换它们以返回到原始位置以进一步交换并获得其他可能的状态。

get_neighbours - 获取所有可能的邻居，这些邻居可以通过与空白元素(0 元素)交换位置而形成。

求解器 - 实现 A* 算法

我找不到我的错误。请指导我解决这个问题。预先感谢您的帮助!

我提前道歉，因为我无法为这个问题生成我的代码的最小版本。我想不出任何方法来使用所有功能并生成代码的最小版本。

Answer 1

(请注意，此答案不同于以下许多评论所涉及的早期修订。)

我不明白当前代码是如何实现队列的。似乎求解器中的 while 循环每次都从可能的移动列表中选择一个新的棋盘状态，然后考虑由这个新的棋盘状态生成的下一个列表。

另一方面，根据我的理解，优先级队列会将当前棋盘状态的所有(有效)邻居插入其中并确定优先级，以便下一个选择的棋盘状态从队列中移除并检查的将是具有最高优先级的。

(为了在调试中完全确定，我可能会添加一个备忘录来检测代码是否最终也重新访问了棋盘状态——啊，转念一想，我相信作业描述中的规定是当前移动的次数是如果正确观察到优先级队列，添加到优先级分配将排除重新访问相同的板状态，因此可能不需要内存。)