title: Depth-First search in Python
body: <p>I'm trying to do a Depth-First search in Python but it's not working.</p>
  
  <p>Basically we have a peg-solitaire board:</p>
  
  <pre><code>[1,1,1,1,1,0,1,1,1,1]
  </code></pre>
  
  <p>1's represent a peg, and 0 is an open spot.  You must move a peg one at a time TWO SLOTS backwards or forward ONLY to an empty spot. If you jump over another peg in the process it becomes an empty slot.  You do this until one peg remains. So basically, a game goes like:</p>
  
  <pre><code>[1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
  [1, 1, 1, 0, 0, 1, 1, 1, 1, 1]
  [1, 0, 0, 1, 0, 1, 1, 1, 1, 1]
  [1, 0, 0, 1, 1, 0, 0, 1, 1, 1]
  [1, 0, 0, 0, 0, 1, 0, 1, 1, 1]
  [1, 0, 0, 0, 0, 1, 1, 0, 0, 1]
  [1, 0, 0, 0, 0, 0, 0, 1, 0, 1] #etc until only 1 peg left
  </code></pre>
  
  <p>Here's what I have:</p>
  
  <pre><code>class MiniPeg():
      def start(self):
          ''' returns the starting board '''
          board = [1,1,1,1,1,0,1,1,1,1]
          return board
  
      def goal(self, node):
          pegs = 0
  
          for pos in node:
              if pos == 1:
                  pegs += 1
  
          return (pegs == 1) # returns True if there is only 1 peg
  
      def succ(self, node):
          pos = 0
          for peg in node:
              if peg == 1:                
                  if pos &lt; (len(node) - 2):  # try to go forward
                      if node[pos+2] == 0 and node[pos+1] == 1:
                          return create_new_node(node, pos, pos+2)
  
                  if pos &gt; 2: # try to go backwards 
                      if node[pos-2] == 0 and node[pos-1] == 1:
                          return create_new_node(node, pos, pos-2)
          pos += 1
  
  def create_new_node(node, fr, to):
      node[fr] = 0
      node[to] = 1
      if fr &gt; to:
          node[fr-1] = 0
      else:
          node[fr+1] = 0
      return node
  
  if __name__ == "__main__":
      s = MiniPeg()
      b = s.start()
  
      while not s.goal(b):
          print b
          b = s.succ(b)
  </code></pre>
  
  <p>So, now my questions:</p>
  
  <ol>
  <li>Is this the right way to do a Depth-First search for this?</li>
  <li>My algorithm doesn't work!!!  It gets stuck.  I've been struggling on this for days before asking here so please help.</li>
  <li>Looks like I'm not following DRY, any suggestions?</li>
  <li>omg help me?</li>
  </ol>