A Board class for the Eight Puzzle Begin by downloading the following zip file:
ID: 3820848 • Letter: A
Question
A Board class for the Eight Puzzle
Begin by downloading the following zip file: project.zip
Unzip this archive, and you should find a folder named project, and within it a number of files, including board.py. Open that file in IDLE, and put your work for this part of the project in that file. You should not move any of the files out of the project folder.
We have given you the start of a constructor __init__(self, digitstr) that accepts a string input digitstr and assigns preliminary values to the following three attributes:
tiles: a reference to a 2-D list of integers with 3 rows and 3 columns that will be used to store the contents of the board. Initially, this 2-D list is filled with zeros.
blank_r: an integer representing the row of the blank cell; this is initially set to -1
blank_c: an integer representing the column of the blank cell; this is also initially set to -1
The input digitstr is a 9-character string of digits that specifies the desired configuration of the tiles. For example, consider the following puzzle:
It would be represented by the string '142358607'. Notice that:
the first 3 characters in the string (142) specify the contents of the first row
the next 3 characters (358) specify the contents of the second row
the final 3 characters (607) specify the contents of the last row, with 0 representing the blank cell.
Leaving our starter code alone, add code below it that updates the values of the three Board attributes to reflect the input digitstr. For the string 142358607 described above, you should end up with the following values:
tiles should be [[1, 4, 2], [3, 5, 8], [6, 0, 7]]
blank_r should be 2, since the blank cell is in row 2
blank_c should be 1, since the blank cell is in column 1
There are multiple options for processing the input digitstr, but you should use at least one loop. Here are some hints:
The tile at row r, column c gets its value from the digit at position (3*r + c) of the input string digitstr. For example, the tile at row 1, column 2 in the above puzzle is an 8, and that corresponds to digitstr[3*1 + 2] (i.e., position 5 in the string '142358607').
You can use the int() function to convert the string version of a digit to the appropriate integer.
Don’t forget to record the row and column numbers of the blank cell in the attributes blank_r and blank_c.
Examples:
Write a method __repr__(self) that returns a string representation of a Board object.
In the string that __repr__ constructs, each numeric tile should be represented by the appropriate single-character string, followed by a single space. The blank cell should be represented by an underscore character ('_') followed by a space; make sure that you do not accidentally use a hyphen ('-'). There should be a newline character (' ') after the characters for each row, so that each row will appear on a separate line when you evaluate or print a Board object. For example:
Note that calling str(b) from the Shell allows us to see the full string returned by __repr__, including all of the spaces and newline characters. Make sure that your results for this call match ours.
Hints:
This __repr__ will be similar to the one that you wrote for the Board class in Problem Set 10. You may want to use that method as a model, and to consult the hints that we gave you for that problem.
Remember that the __repr__ method needs to return a string, and that it should notdo any printing.
You can use the str() function to convert an integer to a string.
Make sure that your __repr__ doesn’t change the object in any way. In particular, the tiles list should not change:
As discussed in lecture, we can simplify things by imagining that all Eight-Puzzle moves involve “moving” the blank cell. For example, in the puzzle below
moving the blank up is equivalent to moving the 5 down, which produces the following board:
Write a method move_blank(self, direction) that takes as input a string directionthat specifies the direction in which the blank should move, and that attempts to modify the contents of the called Board object accordingly. Not all moves are possible on a givenBoard; for example, it isn’t possible to move the blank down if it is already in the bottom row. The method should return True or False to indicate whether the requested move was possible.
Notes/hints:
The input direction can have one of the following four values: 'up', 'down', 'left', 'right'. If any other value is passed in for ‘direction’, the method should print an error message and return False without making any changes to the object.
Here is one possible approach to this method:
Start by determining the new row and column coordinates of the blank cell, based on the value of direction. At first, you should store these new coordinates in temporary local variables, not in the attributes themselves.
Check to see if either of the new coordinates would take you off of the board. If so, simply return False.
Otherwise, make the necessary changes to the Board object’s attributes and return True. Draw some pictures to help you figure out the appropriate changes. We recommend changing the necessary elements of self.tiles beforechanging self.blank_r or self.blank_c.
Examples:
Write a method digit_string(self) that creates and returns a string of digits that corresponds to the current contents of the called Board object’s tiles attribute. For example:
Note that this call to digit_string() returns the string of digits that was used when creating the Board. However, this won’t always be the case, because the string returned by digit_string() should reflect any changes that have been made to the tiles. For example, consider this continuation of the above example:
Write a method copy(self) that returns a newly-constructed Board object that is a deep copy of the called object (i.e., of the object represented by self).
This method should use the Board constructor to create a new Board object with the same configuration of tiles as self, and it should return the newly created Board object.
Hint: The Board constructor takes a string of digits. How could you easily obtain the appropriate string of digits for the called Board?
Examples:
Write a method num_misplaced(self) that counts and returns the number of tiles in the called Board object that are not where they should be in the goal state. You should not include the blank cell in this count, even if it’s not where it should be in the goal state. For example:
Finally, write a method __eq__(self, other) that overloads the == operator – creating a version of the operator that works for Board objects. The method should return True if the called object (self) and the argument (other) have the same values for the tilesattribute, and False otherwise.
This method should be straightforward to implement because you can simply use the ==operator to compare self.tiles and other.tiles. You do not need to explicitly compare the individual tiles yourself, because the == operator already compares the individual elements of 2-D lists.
Examples:
142 287 4-5 136Explanation / Answer
class Board:
""" A class for objects that represent an Eight Puzzle board.
"""
def __init__(self, digitstr):
""" a constructor for a Board object whose configuration
is specified by the input digitstr
input: digitstr is a permutation of the digits 0-9
"""
# check that digitstr is 9-character string
# containing all digits from 0-9
assert(len(digitstr) == 9)
for x in range(9):
assert(str(x) in digitstr)
self.tiles = [[0] * 3 for x in range(3)]
self.blank_r = -1
self.blank_c = -1
# Put your code for the rest of __init__ below.
# Do *NOT* remove our code above.
for r in range(3):
for c in range(3):
self.tiles[r][c] = int(digitstr[3 * r + c])
if self.tiles[r][c] == 0:
self.blank_r = r
self.blank_c = c
### Add your other method definitions below. ###
def __repr__(self):
'''returns a string representation of a Board object'''
b = '' #begin with an empty string
#add one row of slots at a time
for row in range(3):
for col in range(3):
if self.tiles[row][col] == 0:
b += '_'
else:
b += str(self.tiles[row][col])
b += ' '
b += ' '
return b
def move_blank(self, direction):
'''takes as input a string direction that specifies the direction in which
the blank should move and that attempts to modify the contents of the called
Board object accordingly'''
blank_r = self.blank_r
blank_c = self.blank_c
if direction == 'up':
blank_r = self.blank_r - 1
elif direction == 'down':
blank_r = self.blank_r + 1
elif direction == 'left':
blank_c = self.blank_c - 1
elif direction == 'right':
blank_c = self.blank_c + 1
else:
print("Error:Uknown Direction")
return False
if blank_r >= 3 or blank_c >= 3 or blank_r < 0 or blank_c < 0:
return False
else:
substitute = self.tiles[blank_r][blank_c]
self.tiles[blank_r][blank_c] = 0
self.tiles[self.blank_r][self.blank_c] = substitute
self.blank_r = blank_r
self.blank_c = blank_c
return True
def digit_string(self):
'''creates and returns a string of digits that corresponds to the current
contents of the called Board object's tiles attribute'''
digitstring = ''
for r in range(3):
for c in range(3):
if self.tiles[r][c] == '_':
digitstring += '0'
else:
digitstring += str(self.tiles[r][c])
return digitstring
def copy(self):
'''returns a newly-constructed Board object that is a deep copy of the called object'''
first_board_str = self.digit_string()
new_board = Board(first_board_str)
return new_board
def num_misplaced(self):
'''counts and returns the number of tiles in the called Board object that are not
where they should be in the goal state (does not include blank)'''
proper_board = '012345678'
current_board = self.digit_string()
number_wrong = 0
for x in range(8):
if current_board[x] == 0 or current_board[x] == proper_board[x]:
number_wrong += 0
else:
number_wrong += 1
return number_wrong
def how_far(self):
'''counts and returns how far the number of misplaced tiles are from
where they are supposed to be'''
proper_board = '012345678'
current_board = self.digit_string()
how_far_sum = 0
for x in current_board:
if x == 0:
how_far_sum = how_far_sum
else:
proper_index = proper_board.index(str(x))
current_index = current_board.index(str(x))
how_far_sum += abs(proper_index - current_index)
return how_far_sum
def __eq__(self, other):
'''overloads the == operator and creates a version of the operator that
works for Board objects'''
if self.tiles == other.tiles:
return True
else:
return False
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.