• Define a PuzzlePiece class. This class is a little similar to the Node class from our notes on Binary trees. The PuzzlePiece class must have two attributes: connected pieces and secret id. The connected pieces attribute should be used to save all the other puzzle pieces that the current piece is connected to in a list. It should initially start as an empty list. The secret id attribute will be used to keep track of which piece is which when testing the code, but otherwise isnt too important. The following methods must also be defined in this class:

  a) Define a connect to method which takes in two inputs self and other and appends each of them to each others connected pieces attribute.

  b) Define a str magic method which simply returns the secret id of the object. Again, this will help with testing your code.

• Define a Puzzle class. This class will actually create and keep track of all the puzzle pieces. The initialization method (or constructor method, as it is usually called) should create a bunch of puzzle pieces and connect them. For simplicity, lets assume we want to create 100 puzzle pieces on a 10x10 grid, and each piece is connected to the ones directly above, below, to the left, or to the right of it. Thus, most pieces (but not all) will be connected to exactly 4 other pieces. Needless to say, you should create each piece using the PuzzlePiece class. When you create each piece, set its secret id to be its coordinates on the grid. In the end, after creating and connected all the puzzle pieces, you should store them all in a list using the attribute pieces (feel free to store them in matrix format as a list of lists, with each list representing one row of the grid). The following methods must also be defined in this class:

  a) Define a random piece method which takes an input exclude (as well as self) that gener- ates and returns a random puzzle piece from the pieces attribute. The input exclude will be a list of puzzle pieces that you wish to exclude from being randomly generated, so make sure you return a random puzzle piece that is *not* in exclude. You can import a module to generate random numbers for this.

  b) Define a p solve method which uses the random piece method above to randomly pick puzzle pieces and see if they go together, following the description in the introduction. First gener- ate a puzzle piece to start with, and from then on generate a new puzzle piece and see if it fits or not. If it doesnt, it gets thrown back to possibly get picked up again later (to keep things simple, its ok if the same piece gets picked up multiple times in a row). Eventually, you build outward from one piece to put all the pieces together. You should return the list of pieces you successfully put together *in the order that you put them together*. Needless to say, this list should include all the puzzle pieces. You should also print the number of times you had to pick a random piece. Needless to say, this number might be fairly large since you will likely pick up a lot of pieces that dont fit at first. Oh, and I almost forgot: for full credit this method must be written recursively! If you find this confusing, you might want to first write it non-recursively and then see if you can convert it to being recursive. Also, let me emphasize that this method should only check individual puzzle pieces to see if they are connected using the connected pieces attribute of the PuzzlePiece class. You should NOT use the secret id attribute or the puzzle grid or any other outside knowledge to determine if two pieces go together or not.

c) Define a p solve table method which runs the p solve method on the puzzle and then creates a table which visualizes how the pieces were put together and in which order. To do this, look up the ax.table(...) function in the matplotlib module (needless to say, the matplotlib module can do tables). See my example output on the next page. Feel free to make your table look different from mine, but the number in each cell should show the order in which that piece was put together. In particular, the first piece you randomly started with should be labelled with 1, and 2 should be the next piece you found that fit with the first piece, and 3 should be the next piece you found that fit with either 1 or 2, etc. In this way the user can see how your solution built out from the starting point.