Why is my recursive function not outputting anything?

[gotm]

#!/usr/local/bin/python
#Scott Landau
#CS 380
#Assignment 1 Programming Portion in Python
#Created - 4/6/09
#Last Edited - 4/7/09

#n is going to be equal to 4 for this queens problem.
n = 4

#Assigning the empty list to initialState.
initialState = []

#Making an allDirections list.
allDirections = [[-1,0],[1,0],[0,-1],[0,1],[-1,-1],[-1,1],[1,-1],[1,1]]

#declare the list 'state' which represents the number of non threatening
#queens that have been placed on the board.
state = []

def goal(state):
	if (len(state) == n):
		return True
	else:
		return False

#defining allRules list which the contents of which will be created in next function.
allRules = []
#defining all the rules for an nxn board. assigning these rules to allRules
def makeRules(n):
	for i in range(1, (n+1), 1):
		for j in range(1, (n+1), 1):
			allRules.append([i,j])
	return

#making a rule list. this list will probably be refined in future assignments but it will contain the one rule that is applicable in the current state. for #now we will just make it an empty list.
rule = []
#this function will apply the rule that is in the rule list to the given state, which just appends it to the state list.
def applyRule(rule,state):
	state.append(rule)
	return

#returns true if the row or column of 'pos' is out of bounds.
def outOfBounds(pos):
	if ((pos[0] < 1) or (pos[0] > n) or (pos[1] < 1) or (pos[1] > n)):
		return True
	else:
		return False 	

#function that will determine which positions queens cannot be placed into because they might eventually run into another queen already on the board.
def blocked(pos,state,direction):
	newpos = [(pos[0]+direction[0]),(pos[1]+direction[1])]
	for k in range(0, (len(state)), 1):
		if (newpos == state[k]):
			return True
			print "True"
		elif outOfBounds(newpos):
			return False
			print "False"
		else:
			blocked(newpos,state,direction)

state = [[1,2],[2,0]]
direction = [1,0]
pos = [1,0]
blocked(pos,state,direction)

That last function there is the one I am having problems with, I think. This is the N-Queens chess board problem, with a 4x4 board, where you have to place n queens so none of them can attack each other. This is just the basics to the whole problem but I just want to have a working "blocked" function. I thought my functions theory was correct, along with the code, but I tried putting test print lines in there to see if it was outputting anything and I am getting no output.

Any help?

[Murtan]

You're having an entity vs value comparison issue:

a = [[1,2],[2,0]]
b = [2,0]
aa = a[1]
# at this point, b = [2,0] and aa = [2,0]
# but aa == b returns False

# aa[0] == b[0] returns True
# aa[1] == b[1] returns True

Python is comparing the list entities and not the list values.

[Murtan]

If the coordinates were tuple (instead of lists) python would compare the values correctly:

a = [(1,2),(2,0)]
b = (2,0)
aa = a[1]
# now aa == b returns True

#alternatively, though probably slightly less efficient, you could convert the coordinates to tuples at the point of comparison
# tuple(aa) == tuple(b) would return True in the first example code.

[woooee]

For your example, the position is found, i.e. True is returned. Consider using "in" when comparing the two lists as that is the preferred method. The following illustrates this.

a = [ [0,1], [0,2], [1,2] ]
b = [0, 2,]
c = [2, 0]

if b in a:
   print "b found"
else:
   print "b not found"

if c in a:
   print "c found"
else:
   print "c not found"

What output were you expecting from the program?. The program does not print "true" because you return, or exit the function on the line before the print statement (Doh). This modified program shows that the position is indeed found.

#n is going to be equal to 4 for this queens problem.
n = 4
 
#Assigning the empty list to initialState.
initialState = []
 
#Making an allDirections list.
allDirections = [[-1,0],[1,0],[0,-1],[0,1],[-1,-1],[-1,1],[1,-1],[1,1]]
 
#declare the list 'state' which represents the number of non threatening
#queens that have been placed on the board.
state = []
 
def goal(state):
	if (len(state) == n):
		return True
	else:
		return False
 
#defining allRules list which the contents of which will be created in next function.
allRules = []
#defining all the rules for an nxn board. assigning these rules to allRules
def makeRules(n):
	for i in range(1, (n+1), 1):
		for j in range(1, (n+1), 1):
			allRules.append([i,j])
	return
 
#making a rule list. this list will probably be refined in future assignments but it will contain the one rule that is applicable in the current state. for #now we will just make it an empty list.
rule = []
#this function will apply the rule that is in the rule list to the given state, which just appends it to the state list.
def applyRule(rule,state):
	state.append(rule)
	return
 
#returns true if the row or column of 'pos' is out of bounds.
def outOfBounds(pos):
	if ((pos[0] < 1) or (pos[0] > n) or (pos[1] < 1) or (pos[1] > n)):
		return True
	else:
		return False 	
 
#function that will determine which positions queens cannot be placed into because they might eventually run into another queen already on the board.
def blocked(pos,state,direction):
	newpos = [(pos[0]+direction[0]),(pos[1]+direction[1])]
##	for k in range(0, (len(state)), 1):
##		if (newpos == state[k]):
        print "looking for", newpos
        print state, "\n"
        if newpos in state:
			return True
			print "True"
	elif outOfBounds(newpos):
			return False
			print "False"
	else:
			blocked(newpos,state,direction)
 
state = [[1,2],[2,0]]
direction = [1,0]
pos = [1,0]
##
##   added a variable that contains the value returned by the function
result = blocked(pos,state,direction)
if result == True:
   print "position found"
elif result == False:
   print "position not found"
else:               ## "None" (nothing returned)
   print "position added"