So here is my program:

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

import pdb

#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(0, (n), 1):
		for j in range(0, (n), 1):
			allRules.append([i,j])
	return

#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] < 0) or (pos[0] > (n-1)) or (pos[1] < 0) or (pos[1] > (n-1))):
		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])]
	if newpos in state:
		return True
	elif outOfBounds(newpos):		
		return False
	else:
		return True		
		blocked(newpos,state,direction)
		

#precondition to the actions checker
def precondition(rule,state):
   for k in range(0, 8):
      if blocked(rule,state,(allDirections[k])):
         return False
   return True

#generating a list of candidate rules
def candidateRules(state):
	temp = []
	temp = allRules
	for l in range(0,(len(state)),1):
		number = temp.count(state[l])
		for m in range(1,number,1):
			temp.remove(state[l])
	return temp
			
#applicable rules. use candidate and then precondition
def applicableRules(state):
	newRules = candidateRules(state)
	for n in range(0,(len(newRules)),1):
		if not precondition(newRules[n],state):
			newRules.remove(newRules[n])
	return newRules

#make a rule look "pretty"
def printRule(rule):
	print "Place a queen in " + str(rule)
	return

#same for a state
def printState(state):
	hboard = "+---"
	vboard = "|   "
	for a in range(0,n,1):
		print hboard + hboard + hboard + hboard
		print vboard + vboard + vboard + vboard
	print hboard + hboard + hboard + hboard
	return

#backTrack algorithm
def backTrack(state):
	firstState = state[0]
	new = state[1:]
	number = new.count(firstState)
	if (number > 0):
		return "FAILED 1"
	if (goal(firstState)):
		return "GOAL"
	if ((len(state)) > depthBound):
		return "FAILED 3"

	ruleSet = applicableRules(firstState) 
	if (ruleSet == []):
		return "FAILED 4"
	   
	for r in range(0,(len(ruleSet)),1):
		newState = applyRule((ruleSet[r]),firstState) 
	        newStateList = state.insert(newState, 1) 
	        path = backTrack(newStateList)
	        if (path):
			return path.append(ruleSet[r])
	return "FAILED 5"

#test
printState(state)

My state is in the form [[1,1],[2,0]] etc. This is just an example, because this cannot be a valid state according to the problem.

I had to make a visual representation of a chessboard. I did that with printState(state). The problem is, right now it's just printing the chessboard, and I'm confused on how, after passing state, it can actually place a 'Q' in one of the blank spots. Maybe I did this a bad way?

Can anyone help?

Also, I asked my teacher for help on these other two things but, if anyone knows why my candidateRules(state) is printing all the rules all the time, or see any other issues with this, I would appreciate it.

I AM NOT ASKING FOR YOU GUYS TO DO THIS ASSIGNMENT. I seemed to have had someone think that I was doing that the last time I posted a question, but I came with code and have tried my hardest before coming here. There is no point to come here without trying, I'm just trying to get some extra help.

Thanks.

Oh, and apparently my blocked function is not recursive? I thought it was, but it needs to be, so any help I'll take :) If not though that's fine too.

Oh, and apparently my blocked function is not recursive? I thought it was, but it needs to be, so any help I'll take :) If not though that's fine too.

You have a return before the call to blocked. A function always exits immediately when it reaches a return, skipping any lines that come after it.

This article has been dead for over six months. Start a new discussion instead.