CMU 15-112: Fundamentals of Programming and Computer Science
Collab 11 (Due Monday 16-Nov at 8pm ET (Pittsburgh-time))
...but submit at the end of your collab section!




  1. Freddy Fractal Viewer
    Following the Fractal Viewer pattern in the course notes here, write a fractal that draws a circular-shaped face of a teddy bear (named "Freddy"!), without ears. While you need not be pixel-perfect, try to make the face reasonably similar to the one in the image below.

    At level 1, you get one freddy without ears. At level 2, the ears of the outer freddy themselves become freddies. And so on.

    The radius of each ear is exactly half the radius of the face. The following figure shows an example of a Fractal Teddy with maximum recursion level (depth) of 6.



    Hint: to draw the mouth, you should use the function create_arc(...) of Tkinter with the optional parameters style and extent. For more information about this function read the documentation here.


  2. Knight's Tour Solver with Backtracking
    First, read about the Knight's Tour problem here. Next, write the function knightsTour(n) that takes a non-negative int n and returns a 2d list of a knight's tour on an nxn board, or None if this does not exist.

    Following these instructions, print2dList(knightsTour(5)) should print a legal 5x5 knight's tour, such as this one:
    [
     [  1,  6, 15, 10, 21 ]
     [ 14,  9, 20,  5, 16 ]
     [ 19,  2,  7, 22, 11 ]
     [  8, 13, 24, 17,  4 ]
     [ 25, 18,  3, 12, 23 ]
    ]
    
    Here we see that the tour started at 1, which is at the top-left corner. Then following the sequence 1,2,3,... to follow each move in order.

    Note that it is possible for some n that there is a legal knight's tour, only not one starting at the top-left corner. You will have to account for that in your solution.

    Also: backtracking can be slow, and your solution will probably not run fast enough after n=6. That's ok. :-)

    Optional extra challenge: speed this up! There are techniques that can make this work for n>6 (though they still bog down eventually). You can do some pondering of your own, or some internet sleuthing, but in any case, try to make this run faster. Or not, since it is optional.

    In any case, have fun!