recursive function affecting variable

user_3953876 0
Viewed 81

I have a recursive function to count the number of way 8 queens can fit on an 8x8 chess board without intersecting each other (for a class). It works well and gives the correct permutations, the interesting thing happens when I have the program try to count the # of answers -it constantly returns my counter to zero. When I manually count the permutations it's 92 (which is correct).

def can_be_extended_to_solution(perm):
    i = len(perm) - 1
    for j in range(i):
        if i - j == abs(perm[i] - perm[j]):
            return False
    return True

def extend(perm,count, n):
    if len(perm)==n:
        count=count+1
        print "cycle counter= ",count
        print(perm)

    for k in range(n):
        if k not in perm:
            perm.append(k)
            if can_be_extended_to_solution(perm): # if it works
                extend(perm, count, n)
            perm.pop()        

extend(perm = [], count=0, n = 8)
counter recursion python
1 Answers

The issue is that you never allow the recursive call to modify the value of count. You pass the count value in to the function, but then when the count = count + 1 line is called, it only modifies the local value of count for that function call, and does not modify the value in the call that recursively called it.

The following modification works just fine (the return value of extend is 92).

def can_be_extended_to_solution(perm):
    i = len(perm) - 1
    for j in range(i):
        if i - j == abs(perm[i] - perm[j]):
            return False
    return True


def extend(perm, count, n):
    if len(perm) == n:
        count = count + 1
        print("cycle counter= " + str(count))
        print(perm)

    for k in range(n):
        if k not in perm:
            perm.append(k)
            if can_be_extended_to_solution(perm): # if it works
                count = extend(perm, count, n)
            perm.pop()
    return count

print(extend(perm=[], count=0, n=8))
user_53225740
Related