Pavage possible avec triominos (1)

En utilisant uniquement 3 carrés collés sur un côté en forme de L (un triomino), on a 4 sens possibles d'orientation si on souhaite garder les côtés parallèles aux axes.

On peut alors paver, par exemple, un carré de côté 8, percé à la case ligne 5, colonne 4. On a utilisé 21 triominos.

Objectif

On souhaite paver presque entièrement une grille carrée de \(n\) lignes et \(n\) colonnes, indicées de \(0\) inclus à \(n\) exclu. Il y a juste un trou à la ligne i_trou, colonne j_trou qui n'est pas à paver. Il ne faut pas paver en dehors de la grille carrée.

Écrire une fonction est_pavage qui détermine si un pavage est correct ou non. On donne en paramètres :

• n : le côté du carré
• i_trou : la ligne du trou
• j_trou : la colonne du trou
• triominos : la liste des triominos

Un triomino est donné avec un tuple, (i, j, sens)

• i désigne la ligne du carré central
• j désigne la colonne du carré central
• sens est l'orientation, selon le code indiqué plus haut ; un entier de 0 inclus à 4 exclu.

Par exemple, dans l'exemple au-dessus

• (7, 7, 0) désigne le triomino vert en bas à droite
• (7, 0, 1) désigne le triomino rouge en bas à gauche
• (0, 1, 2) désigne le triomino jaune en haut à gauche
• (6, 3, 3) désigne le triomino bleu en bas au milieu

Exemples

Un pavage valide d'un carré de côté 2 avec un trou en \((1, 1)\).

🐍 Console Python

>>> n = 2
>>> i_trou, j_trou = 1, 1
>>> triominos = [(0, 0, 3)]
>>> est_pavage(n, i_trou, j_trou, triominos)
True

Un pavage invalide (incomplet) d'un carré de côté 3 avec un trou en \((1, 2)\).

🐍 Console Python

>>> n = 3
>>> i_trou, j_trou = 1, 2
>>> triominos = [(0, 0, 3), (2, 1, 0)]
>>> est_pavage(n, i_trou, j_trou, triominos)
False

Un pavage invalide d'un carré de côté 4 avec un trou en \((1, 0)\) ; il y a un chevauchement en \((2, 2)\).

🐍 Console Python

>>> n = 4
>>> i_trou, j_trou = 1, 0
>>> triominos = [(0, 1, 2), (2, 1, 2), (0, 2, 3), (2, 3, 0), (3, 2, 1)]
>>> est_pavage(n, i_trou, j_trou, triominos)
False

Un pavage valide.

🐍 Console Python

>>> n = 5
>>> i_trou, j_trou = 4, 0
>>> triominos = [(0, 0, 3), (0, 2, 3), (1, 4, 0), (2, 1, 1), (2, 3, 3), (3, 0, 1), (4, 2, 0), (4, 4, 0)]
>>> est_pavage(n, i_trou, j_trou, triominos)
True

###

Lancer# testsbksl-nlbksl-nlassert estpy-undpavage(2, 1, 1, [(0, 0, 3)]) == Truebksl-nlbksl-nlassert estpy-undpavage(3, 1, 2, [(0, 0, 3), (2, 1, 0)]) == Falsebksl-nlbksl-nltriominos = [(0, 1, 2), (2, 1, 2), (0, 2, 3), (2, 3, 0), (3, 2, 1)]bksl-nlassert estpy-undpavage(4, 1, 0, triominos) == Falsebksl-nlbksl-nlbksl-nltriominos = [bksl-nl (0, 0, 3), (0, 2, 3), (1, 4, 0), (2, 1, 1),bksl-nl (2, 3, 3), (3, 0, 1), (4, 2, 0), (4, 4, 0)bksl-nl]bksl-nlassert estpy-undpavage(5, 4, 0, triominos) == Truebksl-nlbksl-nl# autres testsbksl-nlbksl-nlassert estpy-undpavage(2, 0, 0, [(0, 0, 3)]) == Falsebksl-nlassert estpy-undpavage(2, 0, 0, [(0, 1, 2)]) == Falsebksl-nlbksl-nltriominos = [bksl-nl (0, 0, 3), (0, 0, 3), (0, 2, 3), (1, 4, 0), (2, 1, 1),bksl-nl (2, 3, 3), (3, 0, 1), (4, 2, 0), (4, 4, 0)bksl-nl]bksl-nlassert estpy-undpavage(5, 4, 0, triominos) == False, "Il y a un doublon"bksl-nlbksl-nltriominos = [bksl-nl (0, 2, 3), (1, 4, 0), (2, 1, 1),bksl-nl (2, 3, 3), (3, 0, 1), (4, 2, 0), (4, 4, 0)bksl-nl]bksl-nlassert estpy-undpavage(5, 4, 0, triominos) == False, "Il y en manque"bksl-nlbksl-nlbksl-nlassert estpy-undpavage(4, 2, 1, [(1, 0, 1), (0, 2, 0), (1, 3, 0), (3, 0, 1), (2, 3, 2)]) == False, "Dessiner ce cas !!!"bksl-nlbksl-nlbksl-nl Valider ∞/∞ TéléchargerTéléverser RechargerSauvegarder

def estpy-undpavage(n, ipy-undtrou, jpy-undtrou, triominos):bksl-nl ...bksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert estpy-undpavage(2, 1, 1, [(0, 0, 3)]) == Truebksl-nlbksl-nlassert estpy-undpavage(3, 1, 2, [(0, 0, 3), (2, 1, 0)]) == Falsebksl-nlbksl-nltriominos = [(0, 1, 2), (2, 1, 2), (0, 2, 3), (2, 3, 0), (3, 2, 1)]bksl-nlassert estpy-undpavage(4, 1, 0, triominos) == Falsebksl-nlbksl-nlbksl-nltriominos = [bksl-nl (0, 0, 3), (0, 2, 3), (1, 4, 0), (2, 1, 1),bksl-nl (2, 3, 3), (3, 0, 1), (4, 2, 0), (4, 4, 0)bksl-nl]bksl-nlassert estpy-undpavage(5, 4, 0, triominos) == Truebksl-nlbksl-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-nlbksl-nl# testsbksl-nlbksl-nlassert estpy-undpavage(2, 1, 1, [(0, 0, 3)]) == Truebksl-nlbksl-nlassert estpy-undpavage(3, 1, 2, [(0, 0, 3), (2, 1, 0)]) == Falsebksl-nlbksl-nltriominos = [(0, 1, 2), (3, 1, 2), (0, 2, 3), (2, 3, 0), (3, 2, 1)]bksl-nlassert estpy-undpavage(4, 1, 0, triominos) == Falsebksl-nlbksl-nlbksl-nltriominos = [bksl-nl (0, 0, 3), (0, 2, 3), (1, 4, 0), (2, 1, 1),bksl-nl (2, 3, 3), (3, 0, 1), (4, 2, 0), (4, 4, 0)bksl-nl]bksl-nlassert estpy-undpavage(5, 4, 0, triominos) == Truebksl-nlbksl-nl

A

Z