title: Depth First Search 8 puzzle game "pop from empty list"
body: <p>I have to perform a depth first seach to solve the 8 puzzle game: (-1 represents the empty value)</p>
  <pre><code>initialState1 = [[-1,1,2], [7,8,3], [6,5,4]]
  finalState1 = [[1,2,3], [8,-1,4], [7,6,5]]
  </code></pre>
  <p>The code I have:</p>
  <pre class="lang-py prettyprint-override"><code>def play(puzzle, direction):
    print(puzzle)
    if direction == &quot;up&quot;:
      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==&quot;down&quot;:
      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 == &quot;left&quot;:
      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 == &quot;right&quot;:
      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(&quot;down&quot;)
                          possibilities.append(&quot;right&quot;)
                      elif(j == 1):
                          possibilities.append(&quot;down&quot;)
                          possibilities.append(&quot;right&quot;)
                          possibilities.append(&quot;left&quot;)
                      elif(j == 2):
                          possibilities.append(&quot;down&quot;)
                          possibilities.append(&quot;left&quot;)
                  if(i == 1):
                      if(j == 0):
                          possibilities.append(&quot;down&quot;)
                          possibilities.append(&quot;right&quot;)
                          possibilities.append(&quot;up&quot;)
                      elif(j == 1):
                          possibilities.append(&quot;down&quot;)
                          possibilities.append(&quot;right&quot;)
                          possibilities.append(&quot;left&quot;)
                          possibilities.append(&quot;up&quot;)
                      elif(j == 2):
                          possibilities.append(&quot;down&quot;)
                          possibilities.append(&quot;left&quot;)
                          possibilities.append(&quot;up&quot;)
                  if(i == 2):
                      if(j == 0):
                          possibilities.append(&quot;up&quot;)
                          possibilities.append(&quot;right&quot;)
                      elif(j == 1):
                          possibilities.append(&quot;up&quot;)
                          possibilities.append(&quot;right&quot;)
                          possibilities.append(&quot;left&quot;)
                      elif(j == 2):
                          possibilities.append(&quot;up&quot;)
                          possibilities.append(&quot;left&quot;)
                          
      return random.choice(possibilities)
  
  def depthFirstSearch():
    pathcost=0
    queue=[]
    initialFormatted=[initialState1,&quot;none&quot;]
    queue.append(initialFormatted)
  
    while(True):
      puzzle=queue.pop(0)
      pathcost=pathcost+1
      print(str(puzzle[1])+&quot; --&gt; &quot;+str(puzzle[0]))
      if(puzzle[0] == finalState1):
        print(&quot;Found&quot;)
        print(&quot;Path cost -&gt; &quot;+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()
  </code></pre>
  <p>But running this code, I receive this error :</p>
  <blockquote>
  <p>puzzle=queue.pop(0)
  IndexError: pop from empty list</p>
  </blockquote>
  <p>How to handle this? What i'm doing wrong?</p>
  <p>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?</p>