board.py

class Board():

########################################## #### Constructor ########################################## def __init__(self, n): self.n = n self.spaces = n * n

#indicates that all moves are possible at #the beginning self.constraints = {} for i in range(self.spaces): self.constraints[i] = 0

#holds the final places of the queens self.queenSpaces = []

########################################## #### Move Functions ##########################################

#returns all moves that have 0 constraints on them def getPossibleMoves(self): return [move for move in self.constraints if self.constraints[move] == 0]

def makeMove(self, space):

# add the queen self.queenSpaces.append(space)

# add the conflicts self.addOrRemoveConstraints(space)

def removeMove(self, space):

#remove the queen self.queenSpaces.remove(space)

#remove the dependent conflicts self.addOrRemoveConstraints(space, add=False)

########################################## #### Constraint Logic ##########################################

#adds or removes constraints along the row, col, and diags of a move def addOrRemoveConstraints(self, move, add=True):

# choosing whether to use add or remove function if (add): mutationFx = self.addConstraint else: mutationFx = self.removeConstraint

#TODO provide the logic to add or remove constraints from self.constraints

#YOUR CODE HERE

##########################

#add 1 to the constraint counter for a particular space def addConstraint(self, move): if not move == -1: self.constraints[move] += 1

#remove 1 from the constraint counter for a particular space def removeConstraint(self, move): if not move == -1: self.constraints[move] -= 1

########################################## #### Utility Functions ##########################################

#returns the corresponding space # based on 0-indexed row and column #returns -1 if the space is not on the board # e.g. # rcToSpace(3,4) # the space at row 3, column 4 # > 28 # the corresponding space number given an 8x8 board def rcToSpace(self, row, col): space = row * self.n + col if space >= self.spaces or space

def print(self): for r in range(self.n): row = "" for c in range(self.n): if(self.rcToSpace(r,c) in self.queenSpaces): row += "Q" else: row += "-" row += " " print(row)

lab4.py

import board

# board to be manipulated below b = board.Board(8)

#returns true if there exists a potential queen placement given the current board state # and leaves b.queenspaces filled with the appropriate queen placements #false if otherwise def placeMoves(b, row, column): if row > len(b)-1: yield b while column

#Hint 1: This should be recursively defined #Hint 2: You should only need to use the following three functions from the board class # - getPossibleMoves # - makeMove # - removeMove

if __name__ == "__main__": placeMoves() b.print()

Using the framework of the N-queens board data structure provided in board.py, complete the following objectives: 1. Complete the addOrRemoveConstraints function in board.py to effi ciently add or remove constraints to the appropriate spaces assuming that you just placed a queen at the space indicated by the move argument You may find it helpful to use rcToSpace. 2. Develop the placeMoves function in lab4.py to efficiently place the queens in the appropriate spots on the board using constraint propagation and backtracking. Note: there may be more than one solution, but you only need to find one