- 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:
- The list is 2d, non-empty, square, and contains only integers,
where no integer occurs more than once in the square.
- 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:
- 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 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.
- isLegalSudoku(board) [25 pts]
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) [5 pts]
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) [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 (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) [5 pts]
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) [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 N2 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 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.
- makeWordSearch(wordList, replaceEmpties) [35 pts]
Write the function makeWordSearch(wordList, replaceEmpties) that takes a possibly-empty list
of non-empty lowercase words and a boolean value replaceEmpties (that we will
explain later) and returns a wordSearch (a 2d list of lowercase letters)
that contains all the given words, according to the algorithm described here.
To start, if the wordList is empty, just return None. Otherwise, start
with a 0x0 board. Add each word in the order given to the board according
to the rules below, and return the resulting board.
First, if the word is longer than the number of rows in the board (which is guaranteed
to happen on the first word), then it cannot possibly fit on the board (right?).
In that case, add empty rows and empty columns to the board, keeping the board
square, so that the number of rows equals the length of the word.
Note that empty cells do not yet contain any letters.
Next, if possible,
add the word in the location and direction resulting in the
lowest cost, where the cost is the total number of
empty cells that must be filled in with a letter to add the word at the given location and direction.
If there is a tie, use the first location and direction with the lowest cost, where
you should sweep across row0 from left-to-right, then row1, and so on, and
where the directions should be ordered in the same way (up-left, up, up-right,
left, right, down-left, down, down-right).
It is possible that this process completes with no place to add the word.
In that case,
add one more row and one more column of empty cells to the board, keeping it
square, and then add the
word to the bottom row starting at column 0 and heading to the right.
Hint: you should carefully re-read the previous paragraph, as it may
not be too intuitive!
After you have added all the words, if the replaceEmpties parameter is
False, return the board as-is, with empty cells containing a dash ('-').
However, if replaceEmpties is True, then for each empty cell on the board,
replace it with the first lowercase letter that does not appear among
its non-empty neighbors. Do this sweeping the usual way, left-to-right
across row0, then row1, and so on.
You will surely want to add some well-chosen helper functions here. Also,
you may wish to carefully review a few test cases we are providing you,
prior to designing your solution:
def testMakeWordSearch():
print("Testing makeWordSearch()...", end="")
board = makeWordSearch([], False)
assert(board == None)
board = makeWordSearch(["ab"], False)
assert(board == [['a', 'b'], ['-', '-'] ])
board = makeWordSearch(["ab"], True)
assert(board == [['a', 'b'], ['c', 'd'] ])
board = makeWordSearch(["ab", "bc", "cd"], False)
assert(board == [['a', 'b'], ['c', 'd'] ])
board = makeWordSearch(["ab", "bc", "cd", "de"], False)
assert(board == [['a', 'b', '-'], ['c', 'd', '-'], ['d', 'e', '-']])
board = makeWordSearch(["ab", "bc", "cd", "de"], True)
assert(board == [['a', 'b', 'a'], ['c', 'd', 'c'], ['d', 'e', 'a']])
board = makeWordSearch(["abc"], False)
assert(board == [['a', 'b', 'c'], ['-', '-', '-'], ['-', '-', '-']])
board = makeWordSearch(["abc"], True)
assert(board == [['a', 'b', 'c'], ['c', 'd', 'a'], ['a', 'b', 'c']])
board = makeWordSearch(["abc", "adc", "bd", "bef", "gfc"], False)
assert(board == [['a', 'b', 'c'], ['d', 'e', '-'], ['c', 'f', 'g']])
board = makeWordSearch(["abc", "adc", "bd", "bef", "gfc"], True)
assert(board == [['a', 'b', 'c'], ['d', 'e', 'a'], ['c', 'f', 'g']])
print("Passed!")
- Bonus/Optional: makeBetterWordSearch(wordList) [2.5 pts]
Note: The internet is chock full of wordsearch generators. Do not search
for them and do not use them in any way here. This is meant to be all
about you and your cleverness. Using other people's work here would ruin
all the fun, and all the learning. With that, enjoy!
There are ways we can make an even better wordSearch than the one we just
created above. Here, write the function makeBetterWordSearch(wordList) that
works as above, only the board it returns abides by these additional rules:
- Each word in the wordList appears exactly once on the board.
- Each direction is used equally, as much as possible. To be more precise,
no direction is used more than one more time than any other direction.
- Starting locations are reasonably well-distributed, and not localized say
to the left-top of the board.
- The board is as small as possible.
- The board requires no more than 1 second of time to compute and return.
The autograder will only check some of these conditions, and will only
award 0.5 of the 2.5 possible points here. The remaining 2 points will
be added after the hw deadline. In addition, we may award some small additional
points for especially clever solutions.
- Bonus/Optional: playBattleship(rows, cols, ships, makeMoveFn) [2.5 pts]
Same note as above: Do not use any of the many Battleship
programs out there. It is disallowed, of course, and in any case is not in the spirit
of bonus work, which is not done for points but for the joy of a hard
challenge and for the love of learning.
Here, you will write a computer player for a variant of the game of Battleship.
First, read about the game
here. You may also benefit from (and hopefully also enjoy) playing
it for a while, such as
here (chosen randomly from the many online options).
Now, our variant is that the board will contain N ships, one each
of size 1, 2, 3, ..., up to N. So if N==3, there is one ship that
is of length 1, one ship of length 2, and one ship of length 3.
With this in mind, write the function playBattleship(rows, cols, ships, makeMoveFn)
that takes the size of the board (in rows and cols) and the number of ships
(what we termed N above), along with a makeMoveFn that we will provide to you.
Unlike most code you write, here our code must run first before we can use your
code. We write a battleshipDriver() function, which is the top-level function
that is called to play a game. That function sets up a rows-by-cols board,
chooses a random number N of ships, randomly places those N ships, and then
that function finally calls your function playBattleship, supplying your function
with the rows, cols, ships, and a makeMoveFn. Importantly, your
function is not provided with the locations of the randomly-placed ships
(of course not!).
What about that makeMoveFun that we give you, and that your function calls?
You provide that function with two arguments, the row and col of the move,
and it returns one of these values:
- [string]: an error message (off board, repeated location, not an integer, etc)
- -1: no ship at location
- 0: you hit but did not sink a ship
- N>0: you hit and sunk ship N
Remember that a ship is not sunk until you hit every part of it.
In any case, your function should return immediately after all N ships are sunk.
As with the previous problem, this problem will only be autograded with an
easy case worth 0.5 points. The remaining 2 points will be graded after
the hw deadline. Plainly, the fewer guesses you make, the more bonus you get.
Also, as with the previous problem, you get a maximum amount of compute
time to play your game, though here it is up to 2.5 seconds. Have fun!