15-112 Spring 2016 Homework 6
Due Sunday, 21-Feb, at 10pm

Read these instructions first!

• This hw is SOLO. See the syllabus for details.
• Starting this week, you may use 2d lists and animation, but (as usual) you may not use constructs we have not yet covered (recursion, lambda functions, etc), unless explicitly allowed below.
• This week you may only make up to 5 submissions max to Autolab. As usual, only your last one counts. Also, as usual, we will add 50% more submissions (3 this week) for late/grace days.
• Here is the starter code (hw6.py) that you must use for hw6. Notice how in the othello problem, mousePressed was renamed to othelloMousePressed, keyPressed to othelloKeyPressed, etc, and similar edits were made in the fancy wheels problem. In this way, you can have your othello animation in the same file as your fancy wheels animation (see below) without the two conflicting with each others' names.

---

1. isMagicSquare(a) [20 pts]
   Write the function isMagicSquare(a) that takes an arbitrary list (that is, a possibly-empty, possibly-ragged, possibly-2d list of arbitrary values) and returns True if it is a magic square and False otherwise, where a magic square has these properties:
   1. The list is 2d, non-empty, square, and contains only integers, where no integer occurs more than once in the square.
   2. Each row, each column, and each of the 2 diagonals each sum to the same total.
   If you are curious, you can optionally see here for more details, including this sample magic square:
   


2. isKingsTour(board) [20 pts]
   Background: in Chess, a King can move from any square to any adjacent square in any of the 8 possible directions. A King's Tour is a series of legal King moves so that every square is visited exactly once. We can represent a Kings Tour in a 2d list where the numbers represent the order the squares are visited, going from 1 to N². For example, consider these 2d lists:

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

   The first is a legal Kings Tour but the second is not, because there is no way to legally move from the 7 to the 8, and the third is not, because it contains a 0 which is out of range. Also, this should work not just for 3x3 boards but for any NxN board. For example, here is a legal Kings Tour in a 4x4 board:

       [ [  1, 14, 15, 16],
         [ 13,  2,  7,  6],
         [ 12,  8,  3,  5],
         [ 11, 10,  9,  4]
       ]
   

   With this in mind, write the function isKingsTour(board) that takes a 2d list of integers, which you may assume is NxN for some N>0, and returns True if it represents a legal Kings Tour and False otherwise.


3. isLegalSudoku(board) [25 pts]
   This problem involves the game Sudoku, though we will generalize it to the N²xN² case, where N is a positive integer (and not just the 3²x3² case which is most commonly played). First, read the top part (up to History) of the Wikipedia page on Sudoku so we can agree on the rules. As 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 9 blocks in a 3²x3² puzzle highlighted in a different color:
   
   
   Note: this example is 3²x3² but your code must work for arbitrary sizes (N²xN² for arbitrary N). 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 (in light blue in the figure), moving across and then down (so, in the figure, block 1 is yellow, block 2 is maroon, block 3 is red, block 4 is pink, block 5 is gray, block 6 is tan, block 7 is green, and block 8 is sky blue). 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 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! So you should solve the problem by writing the following functions in the order given:
   
   areLegalValues(values) [5 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 Sudoko 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 presumably have been extracted from some Sudoku board.
   
   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.)
   
   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.
   
   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.
   
   isLegalSudoku(board) [5 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? Seriously, this exercise is a very clear demonstration of the principle of top-down design and function decomposition.


4. runOthello() [15 pts]
   Write the function runOthello() that uses the animation framework we just covered this week to create a variant of this game. It will be quite a bit simpler than the online version (and please do keep this simple) -- you just have to display the board itself, along with the score for each player, so you don't need a splash screen, or instructions, or options, or a help screen. Also, no sound. And your game will be human-human (Player1 and Player2), rather than human-computer (and note that a human-human text-based game of Othello is included in this week's worked examples -- how handy!). Also, while the online game displays legal moves as you hover over them, your game does not have to do that. You also do not need to animate the pieces flipping, they can just instantly flip (though you may animate them for bonus, see below). To deal with game over you should check if the board is full. You don't have to worry about the case when the board is not full but no more legal moves remain. When game over is detected, you should print a "Game Over" message in the center of the screen. When your function is run, it should display a 600x600 window with a 8x8 Othello board.


5. runFancyWheels() [20 pts]
   Write the function runFancyWheels that displays the animation shown at the end of this video.
   
   The first 4 minutes mostly describe what's going on, and you have to watch the entire video to be sure you understand the problem statement, but the actual animation starts around 4:00 in. Note that the video includes buttons at the bottom (go, pause, step, etc) which you should ignore.
   
   When your function is run, it should display a 600x600 window with the 5x5 version of the animation (to be more precise, this is an NxN version where N is initially 5). If the user presses the Right arrow or the Up arrow, N should increase by 1, so the first time, this would change to a 6x6 (in the same sized window), then a 7x7, and so on. If the user presses the Left arrow or the Down arrow, N should decrease by 1, except that N must remain positive (so never set N smaller than 1). Be sure to notice how some wheels spin clockwise and others spin anti-clockwise, in a specific pattern.
   
   Hint: you almost surely will want to include a variable called data.steps or data.timerCounter or some such, which increases by 1 each time timerFired is called. Then you can use this variable to determine the angle of rotation of each fancy wheel.


6. bonus/optional: Enhanced Othello [up to +3 pts]
   For optional bonus, you can:
   • Deal with game over and passing correctly (a user must pass when they don't have a legal move, otherwise they may not pass) (and the game is over when there are no more legal moves by either player) (+0.5 pt)
   • Add a timer (+0.5 pt). If the user takes too long (say, over 10 seconds), they have to pass and the other player gets their turn.
   • Make the pieces animate when they are flipped (+1 pt).
   • Show legal moves as a hint when the player hovers over a legal move (+1 pt).
     Hint: for this, you'll need to add a mouseMotion event in your run function, which responds to mouse events even while the button is not pressed. This is similar to a mousePressed event but requires that you add this line to run() to bind the event:
     root.bind("<Motion>", lambda event: mouseMotionWrapper(event, canvas, data))
     Then, write mouseMotionWrapper (also in run()) to be nearly identical to mousePressedWrapper, and finally write your othelloMouseMotion function (not in run()) to do the heavy lifting.

---