CMU 15-112 Fall 2016: Fundamentals of Programming and Computer Science
Lab 11 (Due Friday 11-11, at 11:11pm, 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.
• Make your own lab11.py file, similar in format to our previous lab files, and import this version of the cs112 file: cs112_f16_wk11.py.
• Be sure to place all your graphics, include the import lines below the #ignore_rest line, and all your autograded functions above that line, or the autograder will not work!
• This week you may use up to 6 submissions. Only your last submission counts.
• Do not hardcode the test cases in your solutions.
• If you know what itertools are, don't use them to get around using recursion. If you don't know what itertools are, you may safely ignore this item.
• Do not use global variables! Do use test functions! Do use helper functions!
• You may use iteration (for + while loops) to solve rectangula, but only if you use recursion meaningfully.

1. solveRectangula(board) [100 pts] [manually graded]
   Background: first, watch this short video on how to play the game of Rectangula:
   
   Now, your task is to write the function solveRectangula(board). This function takes a board which is a 2d list of integers corresponding to the board you see in the video, where blank cells contain 0's. Your function should return a solution to that board, which consists of a list of rectangles (in any order) such that:
   1. Every rectangle in your solution is on the board.
   2. No two rectangles in your solution overlap.
   3. Every non-zero number on the board is inside exactly one rectangle in your solution, and the area of that rectangle matches the number.
   4. And every rectangle in your solution contains exactly one number on the board.
   One oddity is that your rectangles must be of the form (row0, col0, width, height), where (row0, col0) marks the top-left of the rectangle (remember, rows increase vertically, cols increase horizontally), and width is the total number of columns, and height is the total number of rows (so width*height is the area of the rectangle).
   
   If there is no possible solution, your function should return None.
   
   We have provided a lot of code for you. This code is in the file lab11_rectangula_tester.py. You should place that code next to your lab11.py file. Do not include any code from rectangula-tester.py in your lab11.py file! Instead, include these lines in your lab11.py file, below the #ignore_rest line:
   ############################################### # ignore_rest ############################################### # Place these imports in lab11.py below the ignore_rest line! from lab11_rectangula_tester import testSolveRectangula from lab11_rectangula_tester import playRectangula testSolveRectangula(solveRectangula) playRectangula(solveRectangula)
   Then, when you run your lab11.py file, you'll run the testSolveRectangula function and the playRectangula function in rectangula-tester.py.
   
   Remember: Do not include any code from rectangula-tester.py in your lab11.py file!
   
   Now, how should you solve a Rectangula puzzle? You may do this any way you wish, so long as you use backtracking meaningfully. That said, here are some hints about how we did this in our sample solution:
   
   
   • We first created a list of intPositions, which are tuples of the form (row, col, intValue), one for each non-zero integer on the board.
   
   
   • We separately created what we termed a "rectBoard", which is a board of the same size as the original board, but where each cell indicates whether or not it is included in a rectangle yet. This simplified testing whether a new rectangle intersects with any existing rectangle. But you can skip this step if you wish, and just try to intersect each new rectangle to all previous rectangles. But we found this approach to be easier.
   
   
   • The backtracking involves trying to place each intPosition onto the board. To "place" an intPosition means to place a rectangle of that area so that it contains that intPosition. When you run out of intPositions, you're done!
   
   
   • When you have to backtrack, don't forget to undo everything you did to make a move! This is the most common source of bugs in backtracking, so be careful about this step.
   
   
   • We found it was helpful to have a helper function that computed all the possible dimensions for a rectangle of a given area. For example, for an area of 8, the possible dimensions are 1x8, 2x4, 4x2, and 8x1.
   
   
   • When you try to place an intPosition, you should try to place every rectangle of the given area (using that helper function we just mentioned to find all the dimensions for the given area), and then to anchor the top-left of each of these different-dimensioned rectangles at every possible location where that rectangle includes the given position on the board. That may be worth re-reading once or twice...
   
   
   • For each of those possible rectangles that contains the given intPosition, don't forget to check the numbered rules given at the top of this writeup concerning what constitutes a solution.
   
   
   • We also found it handy to include an optional depth parameter so we could print out debug information indented by depth, which is really helpful in recursive debugging.
   
   
   • Also, to easily turn off all your debug printing, which you want to do before you submit, we suggest using a function that looks something like this:
     # To easily turn on/off db output def db(*args): dbOn = True if (dbOn): print(*args)
     So you call db() instead of print() for all your debug printing. Then, when you're done, instead of removing all those db() calls, you just dbOn to False, and voila, all your db printing is disabled. Handy!
   
   Have fun!!!