Homework 7

Due Tuesday 23-March, at 10pm

To start

1. Create a folder named ‘hw7’
2. Create a new file, hw7.py, in that folder.
3. Edit hw7.py and add the functions, classes, and some testcases as required.
4. When you have completed and fully tested hw7, submit hw7.py to Gradescope.

For this hw, you may submit up to 10 times, but only your last submission counts.

Some important notes

1. This homework is solo. You may not collaborate or discuss it with anyone outside of the course, and your options for discussing with other students currently taking the course are limited. See the academic honesty policy for more details.
2. After you submit to Gradescope, make sure you check your score. If you aren’t sure how to do this, then ask a CA or Professor.
3. There is no partial credit on Gradescope testcases. Your Gradescope score is your Gradescope score.
4. Read the last bullet point again. Seriously, we won’t go back later and increase your Gradescope score for any reason. Even if you worked really hard and it was only a minor error…
5. Do not hardcode the test cases in your solutions.
6. We are not giving you any starter code this week. That means you need to create your file from scratch and include your own testcases. For writing testcases, follow the style of testcases uses in the previous homeworks.
7. Remember the course’s academic integrity policy. Solving the homework yourself is your best preparation for exams and quizzes; cheating or short-cutting your learning process in order to improve your homework score will actually hurt your course grade long-term.
8. Your code will be graded for style. Check the style notes on the website for details.

Problems

1. Bird Class and Subclasses [20 pts]
   Write the Bird, Penguin, and MessengerBird classes so that they pass testBirdClasses and use the OOP constructs we learned this week as appropriate.
   
   
   def getLocalMethods(clss): import types # This is a helper function for the test function below. # It returns a sorted list of the names of the methods # defined in a class. It's okay if you don't fully understand it! result = [ ] for var in clss.__dict__: val = clss.__dict__[var] if (isinstance(val, types.FunctionType)): result.append(var) return sorted(result) def testBirdClasses(): print("Testing Bird classes...", end="") # A basic Bird has a species name, can fly, and can lay eggs bird1 = Bird("Parrot") assert(type(bird1) == Bird) assert(isinstance(bird1, Bird)) assert(bird1.fly() == "I can fly!") assert(bird1.countEggs() == 0) assert(str(bird1) == "Parrot has 0 eggs") bird1.layEgg() assert(bird1.countEggs() == 1) assert(str(bird1) == "Parrot has 1 egg") bird1.layEgg() assert(bird1.countEggs() == 2) assert(str(bird1) == "Parrot has 2 eggs") assert(getLocalMethods(Bird) == ['__init__', '__repr__', 'countEggs', 'fly', 'layEgg']) # A Penguin is a Bird that cannot fly, but can swim bird2 = Penguin("Emperor Penguin") assert(type(bird2) == Penguin) assert(isinstance(bird2, Penguin)) assert(isinstance(bird2, Bird)) assert(bird2.fly() == "No flying for me.") assert(bird2.swim() == "I can swim!") bird2.layEgg() assert(bird2.countEggs() == 1) assert(str(bird2) == "Emperor Penguin has 1 egg") assert(getLocalMethods(Penguin) == ['fly', 'swim']) # A MessengerBird is a Bird that can optionally carry a message bird3 = MessengerBird("War Pigeon", message="Top-Secret Message!") assert(type(bird3) == MessengerBird) assert(isinstance(bird3, MessengerBird)) assert(isinstance(bird3, Bird)) assert(not isinstance(bird3, Penguin)) assert(bird3.deliverMessage() == "Top-Secret Message!") assert(str(bird3) == "War Pigeon has 0 eggs") assert(bird3.fly() == "I can fly!") bird4 = MessengerBird("Homing Pigeon") assert(bird4.deliverMessage() == "") bird4.layEgg() assert(bird4.countEggs() == 1) assert(getLocalMethods(MessengerBird) == ['__init__', 'deliverMessage']) print("Done!")


2. Sudoku Logic [35 pts]
   
   Note: This problem is not object oriented (so don't put these functions in a class), but you will use it as a helper function for the next problem.
   
   This problem involves the game Sudoku, a game which is played on a 3²x3² grid, though we will generalize it to the N²xN² case, where N is a positive integer. First, read the top part (up to History) of the Wikipedia page on Sudoku so we can agree on the rules. For terminology, we will refer to each of the N² different N-by-N sub-regions as "blocks". The following figure shows each of the 4 blocks in a 2²x2² completed puzzle highlighted in a different color:
   
   
   
   While the next example shows the blocks of a 3²x3² incomplete puzzle:
   
   
   
   For our purposes, we will number the blocks from 0 to N²-1 (hence, 0 to 8 in the figure), with block 0 in the top-left (red), moving across and then down (so, in the figure, block 1 is orange, block 2 is yellow, block 3 is green, block 4 is blue, block 5 is purple, block 6 is gray, block 7 is brown, and block 8 is tan). We will refer to the top row as row 0, the bottom row as row (N²-1), the left column as column 0, and the right column as column (N²-1).
   
   A Sudoku is in a legal state if all N⁴ cells are either blank (0) or contain a single integer from 1 to N² (inclusive), and if each integer from 1 to N² occurs at most once in each row, each column, and each block. A Sudoku is solved if it is in a legal state and contains no blanks.
   
   We will represent a Sudoku board as an N²xN² 2d list of integers, where 0 indicates that a given cell is blank. For example, here is how we would represent the 3²x3² Sudoku board in the figure above:
   
   

   [
     [ 5, 3, 0, 0, 7, 0, 0, 0, 0 ],
     [ 6, 0, 0, 1, 9, 5, 0, 0, 0 ],
     [ 0, 9, 8, 0, 0, 0, 0, 6, 0 ],
     [ 8, 0, 0, 0, 6, 0, 0, 0, 3 ],
     [ 4, 0, 0, 8, 0, 3, 0, 0, 1 ],
     [ 7, 0, 0, 0, 2, 0, 0, 0, 6 ],
     [ 0, 6, 0, 0, 0, 0, 2, 8, 0 ],
     [ 0, 0, 0, 4, 1, 9, 0, 0, 5 ],
     [ 0, 0, 0, 0, 8, 0, 0, 7, 9 ]
   ]
   

   
   With this description in mind, your task is to write some functions to indicate if a given Sudoku board is legal. To make this problem more approachable, we are providing a specific design for you to follow. And to make the problem more gradeable, we are requiring that you follow the design! You should solve the problem by writing the following functions in the order given:
   
   
   1. areLegalValues(values) [10 pts]
      This function takes a 1d list of values, which you should verify is of length N² for some positive integer N and contains only integers in the range 0 to N² (inclusive). These values may be extracted from any given row, column, or block in a Sudoku board (and, in fact, that is exactly what the next few functions will do -- they will each call this helper function). The function returns True if the values are legal: that is, if every value is an integer between 0 and N², inclusive, and if each integer from 1 to N² occurs at most once in the given list (0 may be repeated, of course). Note that this function does not take a 2d Sudoku board, but only a 1d list of values that may or may not have been extracted from some Sudoku board. Also, note that this function must be non-destructive.
   
   
   2. isLegalRow(board, row) [5 pts]
      This function takes a Sudoku board and a row number. The function returns True if the given row in the given board is legal (where row 0 is the top row and row (N²-1) is the bottom row), and False otherwise. To do this, your function must create a 1d list of length N² holding the values from the given row, and then provide these values to the areLegalValues function you previously wrote. (Actually, because areLegalValues is non-destructive, you do not have to copy the row; you may use an alias.)
   
   
   3. isLegalCol(board, col) [5 pts]
      This function works just like the isLegalRow function, only for columns, where column 0 is the leftmost column and column (N²-1) is the rightmost column. Similarly to isLegalRow, this function must create a 1d list of length N² holding the values from the given column, and then provide these values to the areLegalValues function you previously wrote.
   
   
   4. isLegalBlock(board, block) [5 pts]
      This function works just like the isLegalRow function, only for blocks, where block 0 is the left-top block, and block numbers proceed across and then down, as described earlier. Similarly to isLegalRow and isLegalCol, this function must create a 1d list of length N² holding the values from the given block, and then provide these values to the areLegalValues function you previously wrote. Note that getting the values from a block is much harder than getting the values from a row or col. You'll need to do a bit of math to find the starting row and col for each block based on the block's number.
   
   
   5. isLegalSudoku(board) [10 pts]
      This function takes a Sudoku board (which you may assume is a N²xN² 2d list of integers), and returns True if the board is legal, as described above. To do this, your function must call isLegalRow over every row, isLegalCol over every column, and isLegalBlock over every block. See how helpful those helper functions are?


3. Sudoku Game [40 pts]

   Your task is to make the “backend” for a sudoku game. This will support operations: putting numbers on the board, undoing, and redoing moves. To make this an interactive, working game, all we need to do is attach a frontend! We will do this using graphics/animations in the coming weeks.

   In this assignment you will make an OOP class called SudokuGame that supports the following interface. Your class may have whatever else behind the scenes, but must have support the spec exactly:

   Initialization

   SudokuGame’s __init__(self, board) method should take in a 2d list representing the starting board. You can assume that it is a valid sudoku board and that it is size N**2 by N**2. You should store this, along with any other information that you may need, as instance variables in the object.

   Get board

   In order to grade this, and also to support a clean interface, please define a function getBoard(self) that returns the current sudoku board in a 2d list consisting of integers from 0 to N**2.

   This function should be one line long, but make sure you return a copy of the board so that there are no aliasing issues. Making a deep copy is your friend here.

   Putting numbers on the board

   SudokuGame should have a method placeNumber(self, row, col, num) that places num at row, col if all three values are valid. Validity is defined as being on the board, with a valid num, either 0 (which signifies clearing the space) or any number from 1 to N**2.

   The final state of the board after placing num should be a valid sudoku board. You may find isLegalSudoku helpful here.

   Additionally, you cannot replace a value that was in the original board. So if, initially, there was a 2 at position 0, 0, then no other value can be put there.

   If num was placed successfully, return True. If not, return False.

   Undoing and redoing moves

   You should be able to undo a move by calling undoMove(self). This should undo whatever was the last placed number (including placing a 0).

   You should also be able to redo a move by calling redoMove(self), which redoes the last move that has been undone. Here is sample usage of both:

   game = SudokuGame(someBoard) game.placeNumber(0, 0, 4) game.placeNumber(0, 0, 2) game.placeNumber(0, 0, 1) game.undoMove() # after this, board[0][0] is 2 game.undoMove() # after this, board[0][0] is 4 game.redoMove() # after this, board[0][0] is 2 game.redoMove() # after this, board[0][0] is 1

   redoMove should work like redo does on standard applications. So, once you make a move, it should clear any undone moves that you have (so future redoMove calls will NOT apply them).

   game = SudokuGame(someBoard) game.placeNumber(0, 0, 4) game.placeNumber(0, 0, 2) game.placeNumber(0, 0, 1) game.undoMove() # after this, board[0][0] is 2 game.undoMove() # after this, board[0][0] is 4 game.placeNumber(0, 0, 5) game.redoMove() # after this, board[0][0] is still 5 (the 2 doesn't get applied)

   Remember to return True if the undo or redo was successful, and False otherwise.

   Hints:

   • You will need exactly 2 extra lists to accomplish this behavior. What is each used for? I bet you can figure it out!
   • Whatever you put in those 2 extra lists, you MAY NOT put the entire board in at any point. That would be a wildly inefficient use of space. Instead, think about what information you would need to undo or redo a move!
   
   

   Checking game over

   We can check if the sudoku game is over by calling the checkGameOver(self) method. This will return True if the game is over (the board is filled and valid) and False otherwise.

   Test case

   Here is a testcase that you may find helpful:
   def testSudokuGame(): print("testing SudokuGame...") game = SudokuGame([ [1, 2, 0, 4], [4, 0, 2, 0], [2, 0, 0, 3], [0, 1, 4, 0] ]) # game isn't over at the beginning! assert(game.checkGameOver() == False) # can't override original squares! assert(game.placeNumber(0, 0, 3) == False) assert(game.getBoard() == [ [1, 2, 0, 4], [4, 0, 2, 0], [2, 0, 0, 3], [0, 1, 4, 0] ]) assert(game.placeNumber(1, 1, 3)) assert(game.placeNumber(0, 2, 3)) assert(game.getBoard() == [ [1, 2, 3, 4], [4, 3, 2, 0], [2, 0, 0, 3], [0, 1, 4, 0] ]) # undo the last move, then redo it assert(game.undoMove() == True) assert(game.getBoard() == [ [1, 2, 0, 4], [4, 3, 2, 0], [2, 0, 0, 3], [0, 1, 4, 0] ]) assert(game.redoMove() == True) assert(game.getBoard() == [ [1, 2, 3, 4], [4, 3, 2, 0], [2, 0, 0, 3], [0, 1, 4, 0] ]) # undo a move, then replace it with a new move assert(game.undoMove() == True) assert(game.undoMove() == True) assert(game.placeNumber(3, 0, 3)) assert(game.getBoard() == [ [1, 2, 0, 4], [4, 0, 2, 0], [2, 0, 0, 3], [3, 1, 4, 0] ]) # this should do nothing, since we replaced the move assert(game.redoMove() == False) assert(game.getBoard() == [ [1, 2, 0, 4], [4, 0, 2, 0], [2, 0, 0, 3], [3, 1, 4, 0] ]) newGame = SudokuGame([ [1, 2, 3, 4], [4, 3, 2, 1], [2, 0, 1, 3], [3, 1, 4, 2] ]) assert(newGame.undoMove() == False) assert(newGame.getBoard() == [ [1, 2, 3, 4], [4, 3, 2, 1], [2, 0, 1, 3], [3, 1, 4, 2] ]) assert(newGame.checkGameOver() == False) assert(newGame.placeNumber(2, 1, 4)) assert(newGame.checkGameOver() == True) print("passed!")