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

Question

I have to perform a depth first seach to solve the 8 puzzle game: (-1 represents the empty value)

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

The code I have:

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()

But running this code, I receive this error :

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

How to handle this? What i'm doing wrong?

And is my code doing the right thing to achieve my goal ? In checkBoudaries method, I'm currently setting a random value (within the possibilities) to return.. Is it right or do I have to prefer some movement based on the last move?

Answer 1

There are multiple conceptual problems here, to the point where it's too much work to try and write out a corrected version. However, I think I now understand the general structure of your attempt well enough to fix it.

1. You are using a queue-based approach (as opposed to a recursive one), which means you need to keep track of the path costs (or, if you want to track them, the entire paths) in the queue nodes themselves. (In a recursive approach, you would pass this information along in the recursive call.)

2. You are using a queue-based approach. That naturally implements breadth-first search. You want a stack instead, so that new possibilities from the current position are tried before the other possibilities at the "parent" position.

3. The particular problem you are solving makes it possible to go in a loop. You need to have some kind of detection for this. A simple approach is to maintain a set of previously seen positions.

4. You need to search exhaustively, not just pick one move from the current position. That's the entire point of the algorithm. You should return the entire list of possibilities from checkBoundaries, and add a separate node to the stack for each possibility.

---

But the thing that actually causes the reported problem:

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

This check shouldn't be necessary, because you are only supposed to be trying valid moves, and valid moves should (by definition) change the board position.

But aside from that, you never insert anything into your queue because this condition is never met - the nextMove is always equal to puzzle[0], even though you changed the board position. Why? Because it is the same object. Nothing in your code ever makes a copy of the board object; so the queue contains multiple copies; the play code modifies that same, single object and returns it back to you, etc. This is a common problem in Python that manifests in many forms - nothing that's quite an exact duplicate, but it's the same problem as, for example, List of lists changes reflected across sublists unexpectedly .

Which means, even if you removed the unnecessary check, you would still have problems - because your play function affects every node in the queue. You need to rewrite play so that it creates a new list-of-lists representing the "next" board position, without modifying the input.