深度优先搜索 8 益智游戏 "pop from empty list"

Question

我必须执行深度优先搜索来解决8拼图游戏：（-1代表空值）

initialState1 = [[-1,1,2], [7,8,3], [6,5,4]]
finalState1 = [[1,2,3], [8,-1,4], [7,6,5]]

我的代码：

def play(puzzle, direction):
  print(puzzle)
  if direction == "up":
    for i in range(3):
      for j in range(3):
        if(puzzle[i][j]==-1):
          if i!=0:
            puzzle[i][j] = puzzle[i-1][j]
            puzzle[i-1][j] = -1
          return puzzle

  if direction=="down":
    for i in range(3):
      for j in range(3):
        if(puzzle[i][j]==-1):
          if i!=2:
            puzzle[i][j] = puzzle[i+1][j]
            puzzle[i+1][j] = -1
          return puzzle

  if direction == "left":
    for i in range(3):
      for j in range(3):
        if(puzzle[i][j] == -1):
          if j!=0:
            puzzle[i][j] = puzzle[i][j-1]
            puzzle[i][j-1] = -1
          return puzzle

  if direction == "right":
    for i in range(3):
      for j in range(3):
        if(puzzle[i][j] == -1):
          if j!=2:
            puzzle[i][j] = puzzle[i][j+1]
            puzzle[i][j+1] = -1
          return puzzle

def checkBoundaries(puzzle):
    possibilities = []
    for i in range(3):
        for j in range(3):
            if(puzzle[i][j]==-1):
                if(i == 0):
                    if(j == 0):
                        possibilities.append("down")
                        possibilities.append("right")
                    elif(j == 1):
                        possibilities.append("down")
                        possibilities.append("right")
                        possibilities.append("left")
                    elif(j == 2):
                        possibilities.append("down")
                        possibilities.append("left")
                if(i == 1):
                    if(j == 0):
                        possibilities.append("down")
                        possibilities.append("right")
                        possibilities.append("up")
                    elif(j == 1):
                        possibilities.append("down")
                        possibilities.append("right")
                        possibilities.append("left")
                        possibilities.append("up")
                    elif(j == 2):
                        possibilities.append("down")
                        possibilities.append("left")
                        possibilities.append("up")
                if(i == 2):
                    if(j == 0):
                        possibilities.append("up")
                        possibilities.append("right")
                    elif(j == 1):
                        possibilities.append("up")
                        possibilities.append("right")
                        possibilities.append("left")
                    elif(j == 2):
                        possibilities.append("up")
                        possibilities.append("left")
                        
    return random.choice(possibilities)

def depthFirstSearch():
  pathcost=0
  queue=[]
  initialFormatted=[initialState1,"none"]
  queue.append(initialFormatted)

  while(True):
    puzzle=queue.pop(0)
    pathcost=pathcost+1
    print(str(puzzle[1])+" --> "+str(puzzle[0]))
    if(puzzle[0] == finalState1):
      print("Found")
      print("Path cost -> "+str(pathcost-1))
      break
    else:
      nextMove=play(puzzle[0], checkBoundaries(puzzle[0]))
      if(nextMove!=puzzle[0]):
          nextMove=[nextMove,checkBoundaries(puzzle[0])]
          queue.insert(0, nextMove)

depthFirstSearch()

但是运行这个代码，我收到这个错误：

puzzle=queue.pop(0) IndexError: pop from empty list

如何处理？我做错了什么？

我的代码是否正确地实现了我的目标？在 checkBoudaries 方法中，我目前正在将一个随机值（在可能范围内）设置为 return.. 是正确的还是我必须根据最后一步选择一些移动？

Answer 1

这里有多个概念性问题，以至于尝试写出更正版本的工作量太大了。但是，我想我现在已经足够了解您尝试的一般结构来修复它了。

您正在使用基于队列的方法（与递归方法相反），这意味着您需要跟踪路径成本（或者，如果要跟踪它们，整个路径）在队列节点本身。（在递归方法中，您将在递归调用中传递此信息。）
您正在使用基于队列的方法。那自然实现了广度优先搜索。您需要一个堆栈，以便在“父”位置的其他可能性之前尝试新的可能性。

您正在解决的特定问题使得进入循环成为可能。您需要对此进行某种检测。一个简单的方法是保持 set 个以前看到的位置。

你需要穷尽搜索，而不是只从当前位置选择一步。这就是算法的全部要点。您应该 return 来自 checkBoundaries 的 possibilities 的整个列表，并且 为每种可能性 .
添加一个单独的节点到堆栈

但是实际导致报告问题的事情:

if(nextMove!=puzzle[0]): nextMove=[nextMove,checkBoundaries(puzzle[0])] queue.insert(0, nextMove)

这个检查应该不是必需的，因为你应该只尝试有效的移动，而有效的移动应该（根据定义）改变棋盘位置。

但除此之外，您永远不会在队列中插入任何东西，因为这种情况从未满足 - nextMove 是总是等于 puzzle[0]，即使您更改了棋盘位置。为什么？因为是同一个对象。您的代码中没有任何内容会复制 board 对象；所以队列包含多个副本； play 代码修改了相同的单个对象，然后 return 将其返回给您，等等。这是 Python 中的一个常见问题，以多种形式出现 - 没有什么是完全相同的，但它与例如 List of lists changes reflected across sublists unexpectedly .
的问题相同
这意味着，即使您删除了不必要的检查，您仍然会遇到问题 - 因为您的 play 函数会影响队列中的每个节点。您需要重写 play 以便在不修改输入的情况下创建表示“下一个”棋盘位置的新列表列表。

深度优先搜索 8 益智游戏 "pop from empty list"

Depth First Search 8 puzzle game "pop from empty list"

python

depth-first-search