Pavages dans Sage

Aujourd'hui, j'ai montré le principe d'induction dans le cadre de mon cours Structures discrètes à l'UQAC. J'utilise le livre Mathématiques discrètes, édition révisée de K. Rosen, une référence classique en matière de mathématiques discrètes. En particulier, j'ai présenté une démonstration par induction portant sur un problème de pavage que j'énonce brièvement ici :

Considérons une grille de dimension 2ⁿ × 2ⁿ dont on a retiré une cellule (n'importe quelle cellule). Nous pouvons démontrer par induction qu'il est possible de paver la grille moins ce carré en utilisant autant de copies qu'on le désire des quatre tuiles suivantes :

L'idée consiste à diviser le carré principal en quatre sous-carrés de taille 2^n − 1 × 2^n − 1. Ensuite, on identifie lequel des quatre sous-carrés contient la cellule qu'on avait initialement supprimée. Par induction, nous pouvons résoudre le problème pour ce sous-carré. Quant aux trois sous-carrés qui restent, il suffit de supprimer leur cellule la plus proche du centre du carré principal : Ces trois cellules sont connexes et décrivent exactement la forme d'une des quatre tuiles de base permises. Par induction, nous résolvons alors les trois sous-problèmes pour chacun des trois sous-carrés, puis on ajoute la tuile centrale, ce qui termine la démonstration.

Il est intéressant de noter que cette démonstration par induction cache un algorithme récursif qui nous permet de paver complètement le carré principal. Grâce au ticket #11379 (conçu par mon ami et collègue S. Labbé) récemment intégré dans le logiciel Sage, j'ai été en mesure de générer la solution. Voici le résultat pour la grille 8 × 8 de laquelle on a retiré la cellule (2, 2) :

À noter que les polyominos en bleu sont ceux obtenus par les cas de base de l'algorithme alors que les rouges sont ceux positionnés lors de chaque appel récursif. Évidemment, l'algorithme est valide également pour d'autres valeurs de n. Plus bas se trouve un exemple avec la grille 16 × 16 de laquelle on a retiré la cellule (10, 3) :

Le code source utilisé est le suivant :

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

Les deux images ci-haut sont obtenues à l'aide des commandes

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

et

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