title: Python: N Puzzle (8-Puzzle) Solver Heruistics: How to iterate?
body: <p>I have written a selection of functions to try and solve a N-puzzle / 8-puzzle.  </p>
  
  <p>I am quite content with my ability to manipulate the puzzle but am struggling with how to iterate and find the best path. My skills are not in OOP either and so the functions are simple.</p>
  
  <p>The idea is obviously to reduce the heruistic distance and place all pieces in their desired locations.</p>
  
  <p>I have read up a lot of other questions regarding this topic but they're often more advanced and OOP focused.</p>
  
  <p>When I try and iterate through there are no good moves. I'm not sure how to perform the A* algorithm. </p>
  
  <pre><code>from math import sqrt, fabs
  import copy as cp
  
  # Trial puzzle
  puzzle1 = [
      [3,5,4],
      [2,1,0],
      [6,7,8]]
  
  # This function is used minimise typing later
  def starpiece(piece):
      '''Checks the input of a *arg and returns either tuple'''
      if piece == ():
          return 0
      elif isinstance(piece[0], (str, int)) == True:
          return piece[0]
      elif isinstance(piece[0], (tuple, list)) and len(piece[0]) == 2:
          return piece[0]
  
  # This function creates the goal puzzle layout
  def goal(puzzle):
      '''Input a nested list and output an goal list'''
      n = len(puzzle) * len(puzzle)
      goal = [x for x in range(1,n)]
      goal.append(0)
      nested_goal = [goal[i:i+len(puzzle)] for i in range(0, len(goal), len(puzzle))]
      return nested_goal
  
  # This fuction gives either the coordinates (as a tuple) of a piece in the puzzle
  # or the piece in the puzzle at give coordinates 
  def search(puzzle, *piece):
      '''Input a puzzle and piece value and output a tuple of coordinates. 
      If no piece is selected 0 is chosen by default. If coordinates are 
      entered the piece value at those coordinates are outputed'''
      piece = starpiece(piece)
      if isinstance(piece, (tuple, list)) == True:
          return puzzle[piece[0]][piece[1]]
      for slice1, sublist in enumerate(puzzle):
          for slice2, item in enumerate(sublist):
              if puzzle[slice1][slice2] == piece:
                  x, y = slice1, slice2
      return (x, y)  
  
  # This function gives the neighbours of a piece at a given position as a list of coordinates
  def neighbours(puzzle, *piece):
      '''Input a position (as a tuple) or piece and output a list 
      of adjacent neighbours. Default are the neighbours to 0'''
      length = len(puzzle) - 1
      return_list = []
      piece = starpiece(piece)
      if isinstance(piece, tuple) != True:
          piece = search(puzzle, piece)
      if (piece[0] - 1) &gt;= 0:
          x_minus = (piece[0] - 1)
          return_list.append((x_minus, piece[1]))
      if (piece[0] + 1) &lt;= length:
          x_plus = (piece[0] + 1)
          return_list.append((x_plus, piece[1]))
      if (piece[1] - 1) &gt;= 0:
          y_minus = (piece[1] - 1)
          return_list.append((piece[0], y_minus))
      if (piece[1] + 1) &lt;= length:
          y_plus = (piece[1] + 1)
          return_list.append((piece[0], y_plus))
      return return_list
  
  # This function swaps piece values of adjacent cells 
  def swap(puzzle, cell1, *cell2):
      '''Moves two cells, if adjacent a swap occurs. Default value for cell2 is 0.
      Input either a cell value or cell cooridinates''' 
      cell2 = starpiece(cell2)
      if isinstance(cell1, (str, int)) == True:
          cell1 = search(puzzle, cell1)    
      if isinstance(cell2, (str, int)) == True:
          cell2 = search(puzzle, cell2) 
      puzzleSwap = cp.deepcopy(puzzle)
      if cell1 == cell2:
          print('Warning: no swap occured as both cell values were {}'.format(search(puzzle,cell1)))
          return puzzleSwap
      elif cell1 in neighbours(puzzleSwap, cell2):
          puzzleSwap[cell1[0]][cell1[1]], puzzleSwap[cell2[0]][cell2[1]] = puzzleSwap[cell2[0]][cell2[1]], puzzleSwap[cell1[0]][cell1[1]]
          return puzzleSwap
      else:
          print('''Warning: no swap occured as cells aren't adjacent''')
          return puzzleSwap
  
  # This function gives true if a piece is in it's correct position
  def inplace(puzzle, p):
      '''Ouputs bool on whether a piece is in it's correct position'''
      if search(puzzle, p) == search(goal(puzzle), p):
          return True
      else:
          return False
  
  # These functions give heruistic measurements 
  def heruistic(puzzle):
      '''All returns heruistic (misplaced, total distance) as a tuple. Other 
      choices are: heruistic misplaced, heruistic distance or heruistic list'''
      heruistic_misplaced = 0
      heruistic_distance = 0
      heruistic_distance_total = 0
      heruistic_list = []
      for sublist in puzzle:
          for item in sublist:
              if inplace(puzzle, item) == False:
                  heruistic_misplaced += 1          
      for sublist in puzzle:
          for item in sublist:
              a = search(puzzle, item)
              b = search(goal(puzzle), item)
              heruistic_distance = int(fabs(a[0] - b[0]) + fabs(a[1] - b[1]))
              heruistic_distance_total += heruistic_distance
              heruistic_list.append(heruistic_distance)
  
      return (heruistic_misplaced, heruistic_distance_total, heruistic_list)
  
  def hm(puzzle):
      '''Outputs heruistic misplaced'''
      return heruistic(puzzle)[0]
  
  def hd(puzzle):
      '''Outputs total heruistic distance'''
      return heruistic(puzzle)[1]
  
  def hl(puzzle):
      '''Outputs heruistic list'''
      return heruistic(puzzle)[2]
  
  def hp(puzzle, p):
      '''Outputs heruistic distance at a given location'''
      x, y = search(puzzle, p)[0], search(puzzle, p)[1]
      return heruistic(puzzle)[2][(x * len(puzzle)) + y]
  
  # This is supposted to iterate along a route according to heruistics but doesn't work
  def iterMove(puzzle):
      state = cp.deepcopy(puzzle)
      while state != goal(puzzle):
          state_hd = hd(state)
          state_hm = hm(state)
          moves = neighbours(state)
          ok_moves = []
          good_moves = []
          for move in moves:
              maybe_state = swap(state, move)
              if hd(maybe_state) &lt; state_hd and hm(maybe_state) &lt; state_hm:
                  good_moves.append(move)
              elif hd(maybe_state) &lt; state_hd:
                  ok_moves.append(move)
              elif hm(maybe_state) &lt; state_hm:
                  ok_moves.append(move)
          if good_moves != []:
              print(state)
              state = swap(state, good_moves[0])
          elif ok_moves != []:
              print(state)
              state = swap(state, ok_moves[0])
  
  
  &gt;&gt; iterMove(puzzle1)
  'no good moves'
  </code></pre>