using python
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 isn't 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 other's 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, let's 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 doesn't, 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 don't 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
