list returns empty for the Nqueens solution (written in python)?

Question

I saw some c++ version of Nqueens solution online and decided to code it in python, but for some reason the solution list returns empty.

def is_safe(q , r):
    for i in range(q):
        tmp_q = position[i]
        if tmp_q == position[i] or tmp_q == r - (q - i) or tmp_q == r + (q - i):
            return False
    return True

def queensproblem(q):
    # q equals N, we have finished placed all the queens on each row
    if(q == N):
        solution = []
        for i in range(N):
            solution.append(position[i])
        solutions.append(solution)
    else:
        #look for all possibility in each row, 0...N
        for i in range(N):
            if(is_safe(q, i)):
                position[q] = i
                queensproblem(q + 1)

# q->number of queens placed
q = 0
N = 4
solutions = []
position = [None]*N
queensproblem(q)

print(solutions)

Answer 1

Logic error in is_safe:

    tmp_q = position[i]
    if tmp_q == position[i] or ...
        return False

At this point, tmp_q must be equal to position[i] ... you just forced that condition! If is_safe ever enters this loop, it will return false. Thus, you never complete a solution, and the list remains null.

I'm not going to fix your entire program ... that's not what SO is about. However, I'll give you a little more help: here's the code as I used it, with extra statements to help debugging. This is how I learned the "texture" of the failure: is_safe returning False for anything below the first queen.

print is a low-tech, effective debugging solution: when you have a sick program, ask where it hurts. :-)

def is_safe(q , r):
    for i in range(q):
        tmp_q = position[i]
        if tmp_q == position[i] or tmp_q == r - (q - i) or tmp_q == r + (q - i):
            return False
    return True

def queensproblem(q):
    # q equals N, we have finished placed all the queens on each row
    if(q == N):
        solution = []
        for i in range(N):
            solution.append(position[i])
        solutions.append(solution)
        print "end of problem", solutions
    else:
        #look for all possibility in each row, 0...N
        for i in range(N):
            print "possibility loop", i, solutions, is_safe(q, i)
            if(is_safe(q, i)):
                position[q] = i
                print "recur", position, q+1
                queensproblem(q + 1)

# q->number of queens placed
q = 0
N = 4
solutions = []
position = [None]*N
queensproblem(q)

print(solutions)