board.py class Board(): ########################################## #### Construc

Question

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 < 0:
return -1
else:
return 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 < len(b):
if Board.getPossibleMoves(self):
b[row][column] = 1
for solution in placeMoves(b, row+1, 0):
return solution
else:
column += 1
  

#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.

Explanation / Answer

   #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 < 0:

            return -1

        else:

            return 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.p

import board

b = board.Board(8)

def placeMoves(b, row, column):

    if row > len(b)-1:

        yield b

   while column < len(b):

        if Board.getPossibleMoves(self):

          b[row][column] = 1

          for solution in placeMoves(b, row+1, 0):

              return solution

        else:

            column += 1

if __name__ == "__main__":

    placeMoves()

    b.print()

                                                     

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.