Infinite loop and recursion in Python

Question

I am working on implementing an iterative deepening depth first search to find solutions for the 8 puzzle problem. I am not interested in finding the actual search paths themselves, but rather just to time how long it takes for the program to run. (I have not yet implemented the timing function).

However, I am having some issues trying to implement the actual search function (scroll down to see). I pasted all the code I have so far, so if you copy and paste this, you can run it as well. That may be the best way to describe the problems I'm having...I'm just not understanding why I'm getting infinite loops during the recursion, e.g. in the test for puzzle 2 (p2), where the first expansion should yield a solution. I thought it may have something to do with not adding a "Return" in front of one of the lines of code (it's commented below). When I add the return, I can pass the test for puzzle 2, but something more complex like puzzle 3 fails, since it appears that the now the code is only expanding the left most branch...

Been at this for hours, and giving up hope. I would really appreciate another set of eyes on this, and if you could point out my error(s). Thank you!

#Classic 8 puzzle game
#Data Structure: [0,1,2,3,4,5,6,7,8], which is the goal state. 0 represents the blank
#We also want to ignore "backward" moves (reversing the previous action)

p1 = [0,1,2,3,4,5,6,7,8]
p2 = [3,1,2,0,4,5,6,7,8]
p3 = [3,1,2,4,5,8,6,0,7]

def z(p):   #returns the location of the blank cell, which is represented by 0
    return p.index(0)

def left(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc-1]
    p[zeroLoc-1] = 0
    return p

def up(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc-3]
    p[zeroLoc-3] = 0
    return p

def right(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc+1]
    p[zeroLoc+1] = 0
    return p

def down(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc+3]
    p[zeroLoc+3] = 0
    return p

def expand1(p):   #version 1, which generates all successors at once by copying parent
    x = z(p)
    #p[:] will make a copy of parent puzzle
    s = []  #set s of successors

    if x == 0:
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 1:
        s.append(left(p[:]))
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 2:
        s.append(left(p[:]))
        s.append(down(p[:]))
    elif x == 3:
        s.append(up(p[:]))
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 4:
        s.append(left(p[:]))
        s.append(up(p[:]))
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 5:
        s.append(left(p[:]))
        s.append(up(p[:]))
        s.append(down(p[:]))   
    elif x == 6:
        s.append(up(p[:]))
        s.append(right(p[:]))
    elif x == 7:
        s.append(left(p[:]))
        s.append(up(p[:]))
        s.append(right(p[:]))
    else:   #x == 8
        s.append(left(p[:]))
        s.append(up(p[:]))

    #returns set of all possible successors
    return s

goal = [0,1,2,3,4,5,6,7,8]

def DFS(root, goal):    #iterative deepening DFS
    limit = 0
    while True:
        result = DLS(root, goal, limit)
        if result == goal:
            return result
        limit = limit + 1

visited = []

def DLS(node, goal, limit):    #limited DFS
    if limit == 0 and node == goal:
        print "hi"
        return node
    elif limit > 0:
        visited.append(node)
        children = [x for x in expand1(node) if x not in visited]
        print "\n limit =", limit, "---",children   #for testing purposes only
        for child in children:
            DLS(child, goal, limit - 1)     #if I add "return" in front of this line, p2 passes the test below, but p3 will fail (only the leftmost branch of the tree is getting expanded...)
    else:
        return "No Solution"

#Below are tests

print "\ninput: ",p1
print "output: ",DFS(p1, goal)

print "\ninput: ",p2
print "output: ",DLS(p2, goal, 1)
#print "output: ",DFS(p2, goal)

print "\ninput: ",p3
print "output: ",DLS(p3, goal, 2)
#print "output: ",DFS(p2, goal)

Answer 1

The immediate issue you're having with your recursion is that you're not returning anything when you hit your recursive step. However, unconditionally returning the value from the first recursive call won't work either, since the first child isn't guaranteed to be the one that finds the solution. Instead, you need to test to see which (if any) of the recursive searches you're doing on your child states is successful. Here's how I'd change the end of your DLS function:

    for child in children:
        child_result = DLS(child, goal, limit - 1)
        if child_result != "No Solution":
            return child_result

# note, "else" removed here, so you can fall through to the return from above
return "No Solution"

A slightly more "pythonic" (and faster) way of doing this would be to use None as the sentinel value rather than the "No Solution" string. Then your test would simply be if child_result: return child_result and you could optionally leave off the return statement for the failed searches (since None is the default return value of a function).

There are some other issues going on with your code that you'll run into once this recursion issue is fixed. For instance, using a global visited variable is problematic, unless you reset it each time you restart another recursive search. But I'll leave those to you!

Answer 2

Use classes for your states! This should make things much easier. To get you started. Don't want to post the whole solution right now, but this makes things much easier.

#example usage
cur = initialPuzzle
for k in range(0,5): # for 5 iterations. this will cycle through, so there is some coding to do
    allsucc = cur.succ() # get all successors as puzzle instances
    cur = allsucc[0] # expand first                                                                                           
    print 'expand ',cur 

---

import copy


class puzzle:

    '''
    orientation
    [0, 1, 2
     3, 4, 5
     6, 7, 8]
    '''

    def __init__(self,p):
        self.p = p

    def z(self):  
        ''' returns the location of the blank cell, which is represented by 0 '''
        return self.p.index(0)

    def swap(self,a,b):
        self.p[a] = self.p[b]
        self.p[b] = 0

    def left(self):
        self.swap(self.z(),self.z()+1) #FIXME: raise exception if not allowed

    def up(self):
        self.swap(self.z(),self.z()+3)

    def right(self):
        self.swap(self.z(),self.z()-1)

    def down(self):
        self.swap(self.z(),self.z()-3)

    def __str__(self):
        return str(self.p)

    def copyApply(self,func):
        cpy = self.copy()
        func(cpy)
        return cpy

    def makeCopies(self,s):
        ''' some bookkeeping '''
        flist = list()
        if 'U' in s:
            flist.append(self.copyApply(puzzle.up))
        if 'L' in s:
            flist.append(self.copyApply(puzzle.left))
        if 'R' in s:
            flist.append(self.copyApply(puzzle.right))
        if 'D' in s:
            flist.append(self.copyApply(puzzle.down))

        return flist

    def succ(self):
        # return all successor states for this puzzle state
        # short hand of allowed success states
        m = ['UL','ULR','UR','UDR','ULRD','UDL','DL','LRD','DR']
        ss= self.makeCopies(m[self.z()]) # map them to copies of puzzles
        return ss


    def copy(self):
        return copy.deepcopy(self)



# some initial state
p1 = [0,1,2,3,4,5,6,7,8]

print '*'*20
pz = puzzle(p1)
print pz

a,b = pz.succ()
print a,b