Previous Midterm [20 pts]
This is
SOLO. Do
midterm2 from s13, including the bonus (which is not bonus for this hw).
For the code tracing, include evidence that you traced the code and do not
just include the answers. For the sketched answers, you can do
anything even distantly reasonable to convey your sketch, including written
descriptions.
This is SOLO. This problem is inspired by the “ABC Path” problems at BrainBashers.com. For more (optional) info, check this out.
Background: In what we will call an “ABC Puzzle”, you are given a 5x5 board like this:
It is an empty board except that it contains a single “A” in an arbitrary cell. Also, the letters from “B” to “Y” are arranged around the outside of the board in an arbitrary order, along with arrows that constrain those letters to a certain row, column, or diagonal. For example, in the image, we see the “H” and “T” are constrained to column 0, “L” and “I” are constrained to row 0, and “C” and “G” are constrained to the column running from (0,0) to (4,4). The goal of this puzzle is to place every letter from “B” to “Y” on the board such that: (1) each letter from “B” to “Y” is placed in the row, column, or diagonal in which it is constrained; and (2) each letter from “B” to “Y” is placed adjacent (including diagonally) to the previous letter (so “B” is adjacent to “A”, and “C” is adjacent to “B”, and so on).
A solution to the puzzle is here:
Be sure you understand why this solves the puzzle! If you are unsure, go to the link at BrainBashers.com and read more about this kind of puzzle, including this help page, and maybe try to solve a few more of them (the puzzles include a button you can press to get the solutions!).
Now, for us to represent one of these puzzles in Python, we have to represent the constraints. We’ll do that by reading them clockwise starting from the top-left corner. Thus, in the given example, the constraints are:
constraints = "CHJXBOVLFNURGPEKWTSQDYMI"
And we also need to specify the position of the “A”, which we will do as a (row,col) tuple, as such:
aLocation = (0,4)
With this in mind, write the function solveABC(constraints, aLocation), that takes constraints and the location of the “A”, which together define an ABC Puzzle, and returns a completed board which solves the puzzle, or None if no such board exists. Here is a test function that is based on the puzzle used in the example above (notice how the constraints and aLocation match the unsolved puzzle, and the resulting board matches the solved puzzle):
def testSolveABC():
print "Testing solveABC()...",
constraints = "CHJXBOVLFNURGPEKWTSQDYMI"
aLocation = (0,4)
board = solveABC(constraints, aLocation)
solution = [['I', 'J', 'K', 'L', 'A'],
['H', 'G', 'F', 'B', 'M'],
['T', 'Y', 'C', 'E', 'N'],
['U', 'S', 'X', 'D', 'O'],
['V', 'W', 'R', 'Q', 'P']
]
assert(board == solution)
print "Passed!"
Note: To receive any credit for this problem, you must solve it recursively, even if you could dream up a non-recursive solution!
Hint #1: This is a backtracking problem. Study nQueens. This is most like that problem.
Hint #2: Our sample solution required about 50 lines of code. If you are ranging well past that, perhaps you should pause and rethink your approach. Probably in the vicinity of some blue hoodies!
- flatten [2 pts]
This is SOLO. From f11-hw5, do: flatten. Place your solution in hw9.py.
- solveSudoku
[5 pts]
This is SOLO. Write the function solveSudoku that takes a partially-completed Sudoku board (a 2d list with 0’s representing empty cells), and returns a solved version of the same puzzle, or None if no such solution exists. Note: you must use backtracking here. Also, it will take way too long if you are not clever about the order in which you make your guesses. For that, always find the cell that is the most constrained, that is, the one that has the fewest possible legal choices (resolving ties arbitrarily).
- factorizationAnimation
[5 pts]
This is SOLO. Duplicate this animation (without looking at the Javascript, of course).