#!/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)