Pavage possible avec triominos (2)

Dans cet exercice, on considère un carré (avec un trou) dans une grille, dont le côté est une puissance de 2, et des triominos pour le paver. Il est recommandé d'avoir fait l'exercice Triominos et pavage ; on utilisera le même codage des triominos.

Objectif

On souhaite obtenir un pavage d'un carré troué par des triominos.

Écrire une fonction pavage_triominos qui prend en paramètres

• n : le côté d'un carré ; n sera une puissance de 2.
• i_trou : la ligne du trou
• j_trou : la colonne du trou

La fonction doit renvoyer une liste de triominos qui pave le carré troué. Chaque triomino est codé avec un tuple (i, j, sens) tel que défini dans l'exercice précédent ; i et j désignent la ligne et la colonne du carré central du triomino, et sens indique son orientation.

S'il est impossible d'obtenir un pavage, la fonction renverra None.

Dans cet exercice, on fournit et il sera possible d'utiliser la fonction est_pavage de l'exercice précédent pour vérifier votre pavage ; il n'est souvent pas unique. Tout pavage valide sera accepté.

Exemples

Premier exemple, ici le pavage est unique.

🐍 Console Python

>>> pavage_triominos(2, 1, 1)
[(0, 0, 3)]
>>> est_pavage(2, 1, 1, pavage_triominos(2, 1, 1))
True

Deuxième exemple, ici le pavage n'est pas unique.

🐍 Console Python

>>> pavage_triominos(4, 0, 1)
[(0, 3, 2), (1, 0, 1), (2, 2, 0), (3, 0, 1), (3, 3, 0)]
>>> est_pavage(4, 0, 1, pavage_triominos(4, 0, 1))
True

Troisième exemple, ici le pavage n'est pas unique.

🐍 Console Python

>>> est_pavage(8, 5, 4, pavage_triominos(8, 5, 4))
True

###

Lancer # testsbksl-nlassert estpy-undpavage(2, 1, 1, pavagepy-undtriominos(2, 1, 1)) == Truebksl-nlbksl-nlassert estpy-undpavage(4, 0, 1, pavagepy-undtriominos(4, 0, 1)) == Truebksl-nlbksl-nlassert estpy-undpavage(8, 5, 4, pavagepy-undtriominos(8, 5, 4)) == Truebksl-nlbksl-nl# autres testsbksl-nlassert pavagepy-undtriominos(1, 0, 0) == []bksl-nlbksl-nlfor a in range(16):bksl-nl i, j = divmod(a, 4)bksl-nl assert estpy-undpavage(4, i, j, pavagepy-undtriominos(4, i, j)) == Truebksl-nl assert estpy-undpavage(8, i, j, pavagepy-undtriominos(8, i, j)) == Truebksl-nlbksl-nlfor e in range(4, 7):bksl-nl n = 2py-strpy-strebksl-nl i, j = 1, 1bksl-nl assert estpy-undpavage(n, i, j, pavagepy-undtriominos(n, i, j)) == Truebksl-nl i, j = 2, 3bksl-nl assert estpy-undpavage(n, i, j, pavagepy-undtriominos(n, i, j)) == Truebksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder

# --- HDR ---#bksl-nldef estpy-undpavage(n, ipy-undtrou, jpy-undtrou, triominos):bksl-nl if 3 py-str len(triominos) + 1 != n py-str n:bksl-nl return Falsebksl-nl pavage = [[False for j in range(n)] for i in range(n)]bksl-nl pavage[ipy-undtrou][jpy-undtrou] = Truebksl-nl for (i, j, sens) in triominos:bksl-nl if not (0 <= i < n) or not (0 <= j < n):bksl-nl return Falsebksl-nl # carré centralbksl-nl if pavage[i][j]:bksl-nl return Falsebksl-nl else:bksl-nl pavage[i][j] = Truebksl-nl # en haut, ou en basbksl-nl if sens > 1: # en basbksl-nl if i + 1 >= n:bksl-nl return Falsebksl-nl if pavage[i + 1][j]:bksl-nl return Falsebksl-nl pavage[i + 1][j] = Truebksl-nl else: # en hautbksl-nl if i - 1 < 0:bksl-nl return Falsebksl-nl if pavage[i - 1][j]:bksl-nl return Falsebksl-nl pavage[i - 1][j] = Truebksl-nl # à gauche, ou à droitebksl-nl if sens % 2 == 1: # à droitebksl-nl if j + 1 >= n:bksl-nl return Falsebksl-nl if pavage[i][j + 1]:bksl-nl return Falsebksl-nl pavage[i][j + 1] = Truebksl-nl else: # à gauchebksl-nl if j - 1 < 0:bksl-nl return Falsebksl-nl if pavage[i][j - 1]:bksl-nl return Falsebksl-nl pavage[i][j - 1] = Truebksl-nl # vérification que tout est remplibksl-nl # (facultatif avec le premier test)bksl-nl for i in range(n):bksl-nl for j in range(n):bksl-nl if not pavage[i][j]:bksl-nl return Falsebksl-nl return Truebksl-nlbksl-nlbksl-nl# --- HDR ---#bksl-nl"""bksl-nlFonction disponible :bksl-nlbksl-nlestpy-undpavage(n, ipy-undtrou, jpy-undtrou, triominos)bksl-nl renvoie un booléenbksl-nl détermine si les triominos pavent un carré de côté n ayant un trou indiquébksl-nl"""bksl-nlbksl-nlbksl-nldef pavagepy-undtriominos(n, ipy-undtrou, jpy-undtrou):bksl-nl ...bksl-nlbksl-nlbksl-nl# testsbksl-nlassert estpy-undpavage(2, 1, 1, pavagepy-undtriominos(2, 1, 1)) == Truebksl-nlbksl-nlassert estpy-undpavage(4, 0, 1, pavagepy-undtriominos(4, 0, 1)) == Truebksl-nlbksl-nlassert estpy-undpavage(8, 5, 4, pavagepy-undtriominos(8, 5, 4)) == Truebksl-nlbksl-nl"""bksl-nlFonction disponible :bksl-nlbksl-nlestpy-undpavage(n, ipy-undtrou, jpy-undtrou, triominos)bksl-nl renvoie un booléenbksl-nl détermine si les triominos pavent un carré de côté n ayant un trou indiquébksl-nl"""bksl-nlbksl-nlbksl-nldef pavagepy-undtriominos(n, ipy-undtrou, jpy-undtrou):bksl-nl resultat = []bksl-nl if n == 1:bksl-nl return resultatbksl-nl m = n // 2bksl-nl if ipy-undtrou < m: # le trou est en hautbksl-nl if jpy-undtrou < m: # le trou est à gauchebksl-nl for (i, j, s) in pavagepy-undtriominos(m, ipy-undtrou, jpy-undtrou):bksl-nl resultat.append((i, j, s))bksl-nl sens = 0bksl-nl resultat.append((m, m, sens))bksl-nl else: # le trou est à droitebksl-nl for (i, j, s) in pavagepy-undtriominos(m, ipy-undtrou, jpy-undtrou - m):bksl-nl resultat.append((i, j + m, s))bksl-nl sens = 1bksl-nl resultat.append((m, m - 1, sens))bksl-nl else: # le trou est en basbksl-nl if jpy-undtrou < m: # le trou est à gauchebksl-nl for (i, j, s) in pavagepy-undtriominos(m, ipy-undtrou - m, jpy-undtrou):bksl-nl resultat.append((i + m, j, s))bksl-nl sens = 2bksl-nl resultat.append((m - 1, m, sens))bksl-nl else: # le trou est à droitebksl-nl for (i, j, s) in pavagepy-undtriominos(m, ipy-undtrou - m, jpy-undtrou - m):bksl-nl resultat.append((i + m, j + m, s))bksl-nl sens = 3bksl-nl resultat.append((m - 1, m - 1, sens))bksl-nlbksl-nl if sens != 0:bksl-nl for (i, j, s) in pavagepy-undtriominos(m, m - 1, m - 1):bksl-nl resultat.append((i, j, s))bksl-nl if sens != 1:bksl-nl for (i, j, s) in pavagepy-undtriominos(m, m - 1, 0):bksl-nl resultat.append((i, j + m, s))bksl-nl if sens != 2:bksl-nl for (i, j, s) in pavagepy-undtriominos(m, 0, m - 1):bksl-nl resultat.append((i + m, j, s))bksl-nl if sens != 3:bksl-nl for (i, j, s) in pavagepy-undtriominos(m, 0, 0):bksl-nl resultat.append((i + m, j + m, s))bksl-nl return resultatbksl-nlbksl-nl

A

Z

Indice 1

Si le carré est une puissance de deux, on peut le couper en 4.

• le petit carré qui contient le trou peut être pavé par récursivité.
• pour les trois autres, on place un triomino commun, de sorte qu'il reste à paver un petit carré qui possède un trou à un coin.

Indice 2

Pour paver les trois autres carrés avec un trou dans un coin, on peut utiliser de la récursivité et un décalage sur le pavage obtenu.

Écrire chaque cas pourra s'avérer un peu long. Mais il est possible de factoriser le code, étudier le corrigé en ce sens.

Indice 3

On pourra utiliser le squelette de code

🐍 Script Python

def pavage_triominos(n, i_trou, j_trou):
    resultat = []
    if n == 1:
        return ...
    m = n // 2
    if i_trou < m:  # le trou est en haut
        if j_trou < m:  # le trou est à gauche
            ...
        else:           # le trou est à droite
            ...
    else:           # le trou est en bas
        ...

    ...
    return resultat