Depth-First search in Python

Question

I'm trying to do a Depth-First search in Python but it's not working.

Basically we have a peg-solitaire board:

[1,1,1,1,1,0,1,1,1,1]

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:

[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

Here's what I have:

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

So, now my questions:

1. Is this the right way to do a Depth-First search for this?
2. My algorithm doesn't work!!! It gets stuck. I've been struggling on this for days before asking here so please help.
3. Looks like I'm not following DRY, any suggestions?
4. omg help me?

Answer 1

The normal way to implement DFS in a situation where each step is a "move" from a "board position" to some possible next one, until a goal is reached, is as follows (pseudocode)

seenpositions = set()
currentpositions = set([startingposition])
while currentpositions:
  nextpositions = set()
  for p in currentpositions:
    seenpositions.add(p)
    succ = possiblesuccessors(p)
    for np in succ:
      if np in seenpositions: continue
      if isending(np): raise FoundSolution(np)
      nextpositions.add(np)
  currentpositions = nextpositions
raise NoSolutionExists()

You probably also want to keep backward links to be able to emit, at the end, the series of moves leading to the found solution (if any), but that's an ancillary problem.

I don't recognize a trace of this general structure (or reasonable variant thereof) in your code. Why not try to record it this way? You only need to code possiblesuccessors and isending (if you insist on keeping a position as a list you'll have to turn it into a tuple to check membership in set and add to set, but, that's pretty minor;-).

Answer 2

It doesn't appear that you're creating new nodes, just re-using existing ones. DFS requires some kind of stack (either the call stack, or your own stack). Where is that?

Answer 3

Well, first of all a depth-first search assumes a tree. Now, that makes sense here as you have several possible moves in most cases. A depth first-search would simply try the first possible move, and then the first possible move in the new situation, and the first possible move in that new situation, until success or no more possible moves, in which case it would back up until it finds a move it hasn't tried, and go down again.

The "correct" way of doing that is with recursion. You have no recursion in your system as far as I can see.

Something like this would work (pythonic psuedo codeish english):

def try_next_move(self, board):
    for each of the pegs in the board:
        if the peg can be moved:
            new_board = board with the peg moved
            if new_board is solved:
                return True
            if self.try_next_move(new_board):
                return True
            # That move didn't lead to a solution. Try the next.
    # No move  worked.
    return False

Answer 4

The basic algorithmic problem is that the succ function always only produces just one possible move for a given board state. Even if there would be more than one possible moves, the succ function just returns the first one it can find. A depth first search needs to process all possible moves in each state.

Further problems might then come from the fact that create_new_node, despite it's name, doesn't really create a new node, but modifies the existing one. For depth first search where you want to keep the previous node around it would be better if this function actually created a copy of the list it get's as a parameter.

Also, when checking for the possibility to go backwards in succ, you only try to do so if pos > 2. That's too restrictive, pos > 1 would also be ok.