CMU 15-112 Fall 2016: Fundamentals of Programming and Computer Science
Lab 5 (Due Thursday 29-Sep, at 10pm, no extensions or grace days)

---

• This lab is Collaborative. No solo work allowed. Work in groups of 2-3 (and the same group the whole time). See the syllabus for more details.
• Starter files: lab5.py and cs112_f16_wk5.py
• This week you may use up to 6 submissions. Only your last submission counts.
• Do not use recursion this week.
• Do not hardcode the test cases in your solutions.

---

Note: be sure to use our starter files, and in any case, be sure to place your graphics code (including the tkinter import line) below the #ignore_rest line, so the autograder ignores it. Since tkinter is not available on the autograder server, if you include tkinter above the #ignore_rest line, your code will crash and you will receive a 0 for that submission.

---

1. removeRowAndCol [25 pts] [autograded]
   Write removeRowAndCol non-destructively and also destructively, as described here:
   
   
   1. removeRowAndCol(A, row, col)
      Write the function removeRowAndCol(A, row, col) that takes a 2d list A, a row index and a col index, and non-destructively returns a new 2d list with the given row and column removed. So, if:

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

      Then removeRowAndCol(A, 1, 2) returns:

              [ [ 2, 3, 5],
                [ 0, 1, 3]
              ]
      

      You may assume the row and col are legal, in that they are non-negative integers no larger than the largest row and col index, respectively. Also, A remains unchanged.
   
   
   2. destructiveRemoveRowAndCol(A, row, col)
      Rewrite the previous function so it is destructive. In this case, the return value is None and instead the 2d list A is destructively modified to remove the given row and column.


2. wordSearchWithIntegerWildCards(board, word) [25 pts] [autograded]
   Here we will modify wordSearch so that we can include positive integers in the board, like so (see board[1][1]):

       board = [ [ 'p', 'i', 'g' ],
                 [ 's',   2, 'c' ],
               ]
   

   When matching a word, a positive integer on the board matches exactly that many letters in the word. So the board above contains the word "cow" starting from [1,2] heading left, since the 2 matches "ow". It also contains the word "cows" for the same reason. To make this work, of the three functions in our wordSearch solution, the outer two do not have to change (except a slight renaming), but the innermost one does. Rewrite the innermost function here so that it works as described. Among other parameters, your function should take a direction as a non-negative int (rather than a tuple), and it should return True if the word is in the wordSearch and False otherwise.


3. isLegalSudoku(board) [25 pts] [autograded]
   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. runSillyGame() [25 pts] [manually graded]
   First, carefully watch this video (), then write the missing functions (or portions thereof) in lab5.py:
   1. randomlyPlaceValue
   2. drawCell
   3. doMove