In this assignment we will explore the connection between induction and recursion.

Theorem: Let n be a positive integer. Every 2ⁿx2ⁿ chessboard with one square removed can be tiled using L-shaped triominoes, each covering three squares at a time.

The proof provided a recursive algorithm for constructing such a tiling. Your task in this assignment is to write a Python program that implements the algorithm.

Base case: when n = 1, a 2x2 chessboard with one square removed can be easily tiled with a triomino that covers the three remaining squares.

Recursive case: divide the board into four sub-boards. One of them will have a square removed. Put a triomino that overlaps all the remaining three sub-boards (see picture below and in the slides on induction), and perform recursive calls to tile the four sub-boards, with the squares covered by the additional triomino treated as removed squares for the recursive calls.

Implement a function called triominoes that implements this algorithm as described in the following code snippet:

def triominoes(n, removed_row=0, removed_column=0) :
    """
    tile a chessboard of size 2^n x 2^n with L-shaped triominoes with a
    missing square whose position is given by (removed_row, removed_column)

    return value:
    the return value is a list of lists, where element i,j is associated with
    position i,j in the board; each square is assigned an integer value which
    is the identifier of the triomino in that position.

    for example, a possible return value for n = 1 is:
    [ [1, 1], [1, 2] ]
    the value 1 corresponds to the squares covered by the triomino, and the
    value 2 corresponds to the removed square.

    an example for n = 2:
    [ [1,1,2,2],[1,3,3,2],[4,3,5,5],[4,4,5,6] ]
    This includes entries for triominoes with IDs 1,...,5 and 6 is the value
    associated with the removed square.

    There are no constraints on how you should number the triominoes/removed
    square.
    
    arguments:

    n:  the parameter for the size of the board
    
    removed_row, removed_column:  the row and column in the matrix where the removed
    square should be placed, i.e. 
    board[removed_row][removed_column] should contain the unique value associated
    with the removed square
    """

    # initialization of the board:
    board = [ [0] * 2**n for i in range(2**n) ]

    # code for generating the board goes here
    # you can (and are encouraged to) use recursive helper function/s

    return board

We recommend using a recursive helper function that has additional arguments that pass the matrix that stores triomino IDs and the location of the sub-board that is being treated by a given recursive call.

To visualize the results you can use the following Python commands that use matplotlib, which is the standard data plotting package for Python; matplotlib is installed on department machines, and comes as part of the Anaconda Python installation.

import matplotlib.pyplot as plt
# an example solution for n = 2
X = [ [1,1,2,2],[1,3,3,2],[4,3,5,5],[4,4,5,6] ]
# display the matrix:
img = plt.imshow(X, interpolation='nearest')
img.set_cmap('hot')
plt.axis('off')
# the bit that tells python to display the plot:
plt.show()

Do not include the plotting code with your submission as it may interfere with testing of your code.

Submit your assignment using the checkin system as a single file named PA2.py. The assignment is due by 10:00 pm on Thursday, November 2nd. Late submissions will be accepted until 10:00 pm on Friday November 3rd with a 20% penalty. No submissions will be accepted after this date.

Programming assignment 2: tiling with triominoes