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 trouj_trou: la colonne du troutriominos: la liste des triominos
Un triomino est donné avec un tuple, (i, j, sens)
idésigne la ligne du carré centraljdésigne la colonne du carré centralsensest l'orientation, selon le code indiqué plus haut ; un entier de0inclus à4exclu.
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)\).
>>> 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)\).
>>> 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)\).
>>> 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.
>>> 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
def estpy-undpavage(n, ipy-undtrou, jpy-undtrou, triominos):bksl-nl ...bksl-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),bksl-nl (0, 2, 3),bksl-nl (1, 4, 0),bksl-nl (2, 1, 1),bksl-nl (2, 3, 3),bksl-nl (3, 0, 1),bksl-nl (4, 2, 0),bksl-nl (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-nl
A
Z