Depth-First search in Python

Question

Okay so basically I'm trying to do a depth-first search for a mini-peg solitaire game. For those unfamiliar with the game it's pretty simple.

There's a board with 10 holes and 9 pegs, a peg is represented by a 1 and an empty spot by a 0. You can move a peg backwards or forwards two holes at a time (but you can only move to an empty hole), and if you jump over another peg in the process you take it out and it becomes a hole.

So here's what a game looks 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

So, I have a generator function here that finds all legal moves for a certain "node", or a game board:

def succ(self, node):
    size = len(node)

    # find all legal moves going forward
    for pos in range(0, size-1):
        new_node = list(node)
        if ((node[pos] == 1) and (pos < (size - 2)) and (node[pos+2] == 0)):
            new_node[pos] = 0  # we're moving now
            new_node[pos+2] = 1 # this is where we're moving the peg to
            new_node[pos+1] = 0  # take out the peg here if there was one
            yield new_node

    # find all legal moves going backwards
    for pos in range(0, size-1):
        new_node = list(node)
        if ((node[pos] == 1) and (pos > 1) and (node[pos-2] == 0)):
            new_node[pos] = 0  # we're moving now
            new_node[pos-2] = 1 # this is where we're moving the peg
            new_node[pos-1] = 0  # take out the peg here if there was one
            yield new_node

Now if you know depth-first search, this seems like a GREAT generator to use when solving this puzzle. Or is it? (I think it is, maybe you can help come up with a more Pythonic way?)

Well, my recursive puzzle solver function that will use the generator isn't working, maybe you can help me out?

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 solve_board(dfs_obj, node):
    if goal(node):  # only 1 peg!
        print node
        return node

    for new_node in succ(node):
        print new_node
        return solve_board(new_node)

if __name__ == "__main__":
    solve_board([1, 1, 1, 1, 1, 0, 1, 1, 1, 1])

So basically I think my succ() function is doing the right thing (maybe it's not?), but my solve_board() recursion might be funky, because the board doesn't solve.

Answer 1

I haven't decyphered your succ() function, but assuming it works then the rest of the program indeed does depth-first search. I take it that the code doesn't terminate? If succ can return a state that was previously encountered then you might have an infinite decision tree and depth-first search could get stuck going down the infinite branch and miss the correct solution on another branch. In this case you need to use breadth-first search.

Answer 2

Since you are allowed to jump over empty holes, you'll have to keep track of any nodes you have already visited. Otherwise you will have an infinite loop.

You also need to not shortcircuit the for loop unless you have found a goal

tested_nodes=set()
def solve_board(dfs_obj, node):
    if goal(node):  # only 1 peg!
        print node
        return node

    for new_node in succ(node):
        if tuple(new_node) not in tested_nodes:
            tested_nodes.add(tuple(new_node))
            print new_node
            result = solve_board(new_node)
            if result:  # True if it's a goal, None otherwise
                return result

You have the range wrong in your succ function too, you should not subtrace 1 from the size for the range. You could also rewrite it like this to remove one of the conditions from the if

def succ(self, node):
    size = len(node)

    # find all legal moves going forward
    for pos in range(size-2):
        new_node = list(node)
        if ((node[pos] == 1) and (node[pos+2] == 0)):
            new_node[pos] = 0  # we're moving now
            new_node[pos+2] = 1 # this is where we're moving the peg to
            new_node[pos+1] = 0  # take out the peg here if there was one
            yield new_node

    # find all legal moves going backwards
    for pos in range(1,size):
        new_node = list(node)
        if ((node[pos] == 1) and (node[pos-2] == 0)):
            new_node[pos] = 0  # we're moving now
            new_node[pos-2] = 1 # this is where we're moving the peg
            new_node[pos-1] = 0  # take out the peg here if there was one
            yield new_node

Another way to write the succ funtion would be

def succ(self, node):
    for i in range(len(node)-2):
        j=i+3
        if node[i:j]==[1,1,0]:
            yield node[:i]+[0,0,1]+node[j:]
        if node[i:j]==[0,1,1]:
            yield node[:i]+[1,0,0]+node[j:]
        if node[i:j]==[1,0,0]:
            yield node[:i]+[0,0,1]+node[j:]
        if node[i:j]==[0,0,1]:
            yield node[:i]+[1,0,0]+node[j:]

This tunes the depth first slightly by preferring moves that remove a peg