CMU 15-112: Fundamentals of Programming and Computer Science Extra Practice for Week 5 (Due never)

• These problems will help you prepare for midterm1. They are optional and you are encouraged to collaborate when working on them.

• You may also wish to see extra-practice5-ct-and-roc.html.

• This week we are not providing a starter file. You should now be able to make your own (though of course we are happy to help you get started!).
• Do not use recursion this week.
• Do not hardcode the test cases in your solutions.
• You may assumed 2d lists are rectangular unless explicitly stated otherwise.

1. isRectangular(L)
Write the function isRectangular(L) that takes a possibly-2d (or possibly not) list L and returns True if the list is in fact 2d, and if it is also rectangular, so each row has the same number of elements. Return False otherwise.

2. hasNoPrimes(L)
Write the function hasNoPrimes(L) that takes a 2d list L of integers, and returns True if L does not contain any primes, and False otherwise.

3. hasDuplicates(L)
Write the function hasNoPrimes(L) that takes a 2d list L of arbitrary values, and returns True if L contains any duplicate values (that is, if any two values in L are equal to each other), and False otherwise.

4. fixMostlyMagicSquare(L)
In this week's writing session, we wrote isMostlyMagicSquare(L). Here, say we have a mostly magic square L, but then we modify L by changing exactly one value in L so that it no longer is a mostly magic square. For this exercise, we assume we have just such a list L, and your task is to find and fix that change. So, given the list L, return a new list M such that M is the same as L, only with exactly one value changed, and M is a mostly magic square.

5. makeMagicSquare(n)
Write the function makeMagicSquare(n) that takes a positive odd integer n and returns an nxn magic square by following De La Loubere's Method as described here. If n is not a positive odd integer, return None.

6. isLatinSquare(board)
Write the function isLatinSquare(a) that takes a 2d list and returns True if it is a Latin square and False otherwise.

7. matrixMultiply(m1, m2)
Write the function matrixMultiply(m1, m2) that takes two 2d lists (that we will consider to be matrices) and returns a new 2d list that is the result of multiplying the two matrices. Return None if the two matrices cannot be multiplied for any reason.

8. isKingsTour(board)
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 N2. 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.

9. isKnightsTour(board)
Background: A "knight's tour" in chess is a sequence of legal knight moves such that the knight visits every square exactly once. We can represent a (supposed) knight's tour as an NxN list of the integers from 1 to N2 listing the positions in order that the knight occupied on the tour. If it is a legal knight's tour, then all the numbers from 1 to N2 will be included and each move from k to (k+1) will be a legal knight's move. With this in mind, write the function isKnightsTour(board) that takes such a 2d list of integers and returns True if it represents a legal knight's tour and False otherwise.

10. nQueensChecker(board)
Background:  The "N Queens" problem asks if we can place N queens on an NxN chessboard such that no two queens are attacking each other. For most values of N, there are many ways to solve this problem. Here, you will write the function nQueensChecker(board) that takes a 2d list of booleans where True indicates a queen is present and False indicates a blank cell, and returns True if this NxN board contains N queens all of which do not attack any others, and False otherwise.

11. isLegalSudoku(board)
This problem involves the game Sudoku, though we will generalize it to the N2xN2 case, where N is a positive integer (and not just the 32x32 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 N2 different N-by-N sub-regions as "blocks". The following figure shows each of the 9 blocks in a 32x32 puzzle highlighted in a different color:

Note: this example is 32x32 but your code must work for arbitrary sizes (N2xN2 for arbitrary N). For our purposes, we will number the blocks from 0 to N2-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 (N2-1), the left column as column 0, and the right column as column (N2-1).

A Sudoku is in a legal state if all N4 cells are either blank or contain a single integer from 1 to N2 (inclusive), and if each integer from 1 to N2 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 N2xN2 2d list of integers, where 0 indicates that a given cell is blank. For example, here is how we would represent the 32x32 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)
This function takes a 1d list of values, which you should verify is of length N2 for some positive integer N and contains only integers in the range 0 to N2 (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 N2, inclusive, and if each integer from 1 to N2 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)
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 (N2-1) is the bottom row), and False otherwise. To do this, your function must create a 1d list of length N2 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)
This function works just like the isLegalRow function, only for columns, where column 0 is the leftmost column and column (N2-1) is the rightmost column. Similarly to isLegalRow, this function must create a 1d list of length N2 holding the values from the given column, and then provide these values to the areLegalValues function you previously wrote.

isLegalBlock(board, block)
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 N2 holding the values from the given block, and then provide these values to the areLegalValues function you previously wrote.

isLegalSudoku(board)
This function takes a Sudoku board (which you may assume is a N2xN2 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.

12. Games, games, games!
Have fun writing your own console-based 2d board games (human-human mainly, but maybe a simple human-computer game) such as: