title: N Puzzle in Python
body: <p>I'm trying to build a solution to the N-Puzzle problem using breadth first search in Python.</p>
  
  <p>My solution is adept at finding an answer if all of the numbers bar the zero are in order. e.g.</p>
  
  <pre><code>initial_state = [1,2,3,4,0,5,6,7,8] 
  </code></pre>
  
  <p>or</p>
  
  <pre><code>initial_state = [1,2,3,4,5,6,7,0,8]
  </code></pre>
  
  <p>but fails with</p>
  
  <pre><code>initial_state = [1,2,5,3,4,0,6,7,8]
  </code></pre>
  
  <p>Pleases find below my implementation. If someone could point out the flaw in my logic it'd much appreciated.</p>
  
  <p>Thanks in advance!</p>
  
  <pre><code>def right(state):
      items = list(state)
  
      i = items.index(0)
  
      n = int(math.sqrt(len(items)))
  
      if (i+1) % n != 0:
          del items[i]
  
          items.insert(i+1, 0)
  
          return tuple(items)
      else:
          pass
  
  
  def left(state):
      items = list(state)
  
      i = items.index(0)
  
      n = int(math.sqrt(len(items)))
  
      if i % n != 0:
  
          del items[i]
  
          items.insert(i-1, 0)
  
          return tuple(items)
      else:
          pass
  
  
  def up(state):
      items = list(state)
  
      i = items.index(0)
  
      n = int(math.sqrt(len(items)))
  
      if n**2 &lt; i &lt;= (n**2 - n):
  
          del items[i]
  
          items.insert(i+n, 0)
  
          return tuple(items)
      else:
          pass
  
  
  
  def down(state):
      items = list(state)
  
      i = items.index(0)
  
      n = int(math.sqrt(len(items)))
  
      if i &gt; n:
  
          del items[i]
  
          items.insert(i-n, 0)
  
          return tuple(items)
      else:
          pass
  
  
  class Problem(object):
  
      def __init__(self, initial, goal=None):
  
          self.initial = initial
          self.goal = goal
  
          self.n = len(initial)
  
          self.size = int(math.sqrt(self.n))
  
          self.blank = self.initial.index(0)
  
          self.top_row = [i for i in range(self.n) if i &lt; self.size]
  
          self.bottom_row = [i for i in range(self.n) if self.n - (self.size) &lt;= i &lt; self.n]
  
          self.left_column = [i for i in range(self.n) if i % self.size == 0]
  
          self.right_column = [i for i in range(self.n) if (i + 1) % self.size == 0]
  
      def actions(self):
  
          result_list = ["UP","DOWN","LEFT","RIGHT"]
  
          return result_list
  
      def result(self, state, action):
  
          if action == "RIGHT":
              return right(state)
  
          if action == "LEFT":
              return left(state)
  
          if action == "UP":
              return up(state)
  
          if action == "DOWN":
              return down(state)
  
      def goal_test(self, state):
          return state == self.goal
  
      def path_cost(self, c):
  
          return c + 1
  
  class Node:
  
      def __init__(self, state, parent=None, action=None, path_cost=0):
      self.state = state
      self.parent = parent
      self.action = action
      self.path_cost = path_cost
      self.depth = 0
      if parent:
          self.depth = parent.depth + 1
  
      def __repr__(self):
          return "&lt;Node %s&gt;" % (self.state,)
  
      def __lt__(self, node):
          return self.state &lt; node.state
  
      def expand(self, problem):
  
          return [self.child_node(problem, action)
                  for action in problem.actions() if self.child_node(problem,action) is not None]
  
      def child_node(self, problem, action):
          next = problem.result(self.state, action)
          if next:
              return Node(next, self, action,
                  problem.path_cost(self.path_cost))
          else:
              pass
  
      def solution(self):
  
          return [node.action for node in self.path()[1:]]
  
      def path(self):
  
          node, path_back = self, []
          while node:
              path_back.append(node)
              node = node.parent
          return list(reversed(path_back))
  
      def __eq__(self, other):
          return isinstance(other, Node) and self.state == other.state
  
      def __hash__(self):
          return hash(self.state)
  
  def bfs(problem):
      node = Node(problem.initial)
      frontier = deque([node])
      explored = set()
      while frontier:
          node = frontier.pop()
          explored.add(node.state)
  
          if problem.goal_test(node.state):
              return node
  
          for child in node.expand(problem):
              if child.state not in explored and child not in frontier:
                  frontier.append(child)
      return [child for child in explored]
  
  
  p = Problem((1,2,5,3,4,0,6,7,8), (0,1,2,3,4,5,6,7,8))
  bfs(p)
  
  #returns   
  
  """[(1, 2, 5, 3, 4, 0, 6, 7, 8),
      (1, 2, 0, 5, 3, 4, 6, 7, 8),
      (0, 1, 2, 5, 3, 4, 6, 7, 8),
      (1, 2, 5, 3, 0, 4, 6, 7, 8),
      (1, 2, 5, 0, 3, 4, 6, 7, 8),
      (1, 0, 2, 5, 3, 4, 6, 7, 8)]"""
  </code></pre>