Tilings in Sage

Today, I taught the induction principle in my class Structures discrètes at UQAC. I use the book Discrete mathematics and Applications of K. Rosen, which is a classical for basic discrete mathematics. In particular, I presented a proof by induction on an interesting tiling problem that I briefly state here:

Consider a grid of dimension 2ⁿ × 2ⁿ from which one cell has been removed (it can be any cell). We may prove by induction that it is possible to tile the grid minus one square using as many times as we want one of the following four tiles:

The idea is to divide the main square into four sub-squares of size 2^n − 1 × 2^n − 1. Then, we identify which of the four sub-square contains the cell that has been initially removed. By induction, we can solve the problem for this sub-square. For the three remaining sub-squares, it suffices to remove their cell closest to the center of the main square: These three cells form the shape of one of the three basic tiles. By induction, we can solve the three remaining sub-squares then add the appropriate shape, ending the proof.

Interestingly, this proof by induction hides a recursive algorithm that allows one to tile the main square. Using the ticket #11379 (created by my friend and colleague S. Labbé recently merged in Sage, I was able to generate the solution. Here is the output for the 8 × 8 grid where the cell (2, 2) has been removed:

Note that the blue polyominoes are those obtained from the basis case while red polyominoes are those positionned at each recursive call. Of course, it computes the solution for other values of n. Below is an example on the 16 × 16 grid with cell (10, 3) removed:

The source code used is the following:

from sage.combinat.tiling import Polyomino

def find_tiling((x0,y0), (x1,y1), (cx,cy)):
    if x1 - x0 == 1:
        cells = set([(x0,y0), (x0,y1), (x1,y0), (x1,y1)])
        return [Polyomino(cells - set([(cx,cy)]), color='blue')]
    else:
        solution = []
        mx = int((x0 + x1) / 2)
        my = int((y0 + y1) / 2)

        # Center cells
        cells = set([(mx, my), (mx + 1, my), (mx, my + 1), (mx + 1, my + 1)])

        # Lower-left sub-square
        if cx <= mx and cy <= my:
            (dx, dy) = (cx, cy)
            solution.append(Polyomino(cells - set([(mx, my)]), color='red'))
        else:
            (dx, dy) = (mx, my)
        solution += find_tiling((x0, y0), (mx, my), (dx, dy))

        # Lower-right sub-square
        if cx > mx and cy <= my:
            (dx, dy) = (cx, cy)
            solution.append(Polyomino(cells - set([(mx + 1, my)]), color='red'))
        else:
            (dx, dy) = (mx + 1, my)
        solution += find_tiling((mx + 1, y0), (x1, my), (dx, dy))

        # Upper-left sub-square
        if cx <= mx and cy > my:
            (dx, dy) = (cx, cy)
            solution.append(Polyomino(cells - set([(mx, my + 1)]), color='red'))
        else:
            (dx, dy) = (mx, my + 1)
        solution += find_tiling((x0, my + 1), (mx, y1), (dx, dy))

        # Upper-right sub-square
        if cx > mx and cy > my:
            (dx, dy) = (cx, cy)
            solution.append(Polyomino(cells - set([(mx + 1, my + 1)]), color='red'))
        else:
            (dx, dy) = (mx + 1, my + 1)
        solution += find_tiling((mx + 1, my + 1), (x1, y1), (dx, dy))

        return solution

The two previous images have been generated by the commands

sum(p.show2d() for p in find_tiling((0,0), (7,7), (2,2))).show(aspect_ratio=1, axes=False)

and

sum(p.show2d() for p in find_tiling((0,0), (15,15), (10,3))).show(aspect_ratio=1, axes=False)