Triominos et pavage (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.

triominos

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

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

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10
.128013nFTmOwgPoC,*6]uRa8bsr[vcej-1S9_d(iyk02; 5+l4t/E3)fh:=7DNp050G0z0T0r0I0R0u0O0y0R0r0u0u0#010T0I0)010406050u0p0e0e0r0v0J040D0j0R0p0}0j0b050U1416181a120)041j1q051t0U1t1v1q120G0I0x0=0@0_0{0Z0I0h0Z0R1J0Z0T10050-0t0R0z1E0^0`011I1K1M1K0T1S1U1Q0T0t0j0G1a1R0v1r0T0Z0=1d0u0)0r0b0{0M011W1G010Y0/0z0b0r0e0z1Q1{1}221Y251U282a100a0O0i0v0j0)0j0u0I1g0b0O0+1_0v0v0z0y2v1j2d0b1r0U1@2I0T1=1;1?0G2f0{1M0b272s1Q1B1D0?1X2S0I2U0b1.1C1Q0)2B1r2G2I2:131|2w2!232)0v170R100O0C2F2@112?2e2_1Y2{2}2 0M321}342G2R01390r2~040O0W3d2H123g370{3j3l0O0S3p3f2@3h3v2 0P3z3r3B3t3i0j2|3k2 0n3G352^1F383L3a3m0$3Q3s3T3u3V3N3m0s3Z3I3#3K3M3w0E3+363-3D040C0L3=3S2#3.3W0C311k333H3?3~3^0C3c433e453}2`3%3l0C3o4b3q3R3C4g100C3y4k3A464f3/4p3F4s4d4n4w3_3P4z4m3J483Y4F3!474o3_3*4K3,4M4C0C3;4Q4u3U4C0M3{4W4e4Y3W0M422:4A4H4N0M4a4,4G3@4/4j4=4L4v4)4r2=1w2.1j2Y2L0G2P3h0y1.2b1r531u514 2=580+2/4R2`100k0f0f0q0%0D0F0D0V0(0D3z0O4?3~0j100#5y5A230 040w0w0H3z5G1Y0e0I104#2=4{1Y5I0l5N5V0{5Q5S5Z5k5W100X5Y4s5z5!015I5M4s5O0{5C040B5(4X5#5R3_5}4%0{5X5F5:5$045T335^5;5+5-2:5/5)64105?5U6i01686a3e6c655.6c5`5|5@67604+6b5:5I0X0o6f330O6J6h5~010y0C10030u270;6q3q6K6X6Y6K6s105L623h6p6(3J6t6m6M6*6y6n6E6H3e6L636d046l6C6n6w6+3-686B6r6D106@2H6_6)606V5j6M6?666=6k713~6:6.6`6-6I6v100Q7k23737u5*046F783m6!5:6O6Q6S0b0;746W6Z7M7a6,6$6}756n7m6~7f777x5 5%6;7W7z7B7O3-5=7Y6o6A7,7p6^6c7U7S7$5,7h7$7R2H7=7c7/7X6u5:707#6`7w853h6E6G5y6X6c7F046R6T0O4;447N7M6#5J7|7e867 887P047B7~7!7n896e7`7o7j8u727.8G3~7:798y69807%8D8B6|7,7?7}768w8R3J878A8v6F0o8c8d7E6P8g7H0;4_44064-3-0K100+0Y7,0g2 7,0b0Y100z0u0T0F1|0x0r0h0z8P8q6c0b101i8J5H816g9f100I0F2M0j0p8P7(9n040A9q2p9t9j7y9v5:9g042M0I0j5Q2)0u8P0X0!3G8+6n9G0h0v0/1U0F991M0+8Z3-5`5E5.6J8o5K7,0K0y100c3k6S9%3~8_040Y3L9_5l040I9 1Y0j8~a19i9m9F0t100v1}9b9d909h9O8)826n9{9}0va33u9oaq01a59oa87qaaacae9c9C6j8TaD3iaiaG8a9R7D9T9h0t0F0y0^94at9)at8#8laM6M9U9W0R9Y9!0I9$aJ6$aha19z9s8P0o0wa.9y9r9B8$7*10aka96 5Dat9:100d0v0paC4,9S6Man9~ala!109I9K2%0jaUa62%at9Gbi9L2s8P9Q4z7N9wa2a,8YaG9G0A9ua.8/aUb2bf6`bq9Wbj2)aL6Z6cbdapbK3C8`0I0Y0Y0Fbza|8K9layaN041BbZ0FbEbV3Java7bp5m5o5q5s5u5w8Pa@bC10bHbA0obv6g068maZbL9oaQaSbI049*b0bga1cf7tb;3@bXb.b$aYc99w9yaR9^cn5BbJcicb9xclb^b,bYb!b:bac97)9`9o8|cy23b?2)0Tat7+aG8V3m7r04020R0T0Nchb*cj9pcwb9c+6`5`c$c(cFax7;83a61}0GaW8tcB3hc=c%c)cFcvcecQa410c?0Nc^9Oc6cscL9,5:9{2B0T0p0vc_8Mdk9;049?0:c/4cdibScObm9h0jcUd9ar049V9X0z9Z3ka*dx8W7i5Ja.c-d8b%9k04a?a^cdcxdW7yc5bQdicMa0dJa%dLa)a+d%aEc0d?aHa/c.a=d^7VcCd7d$d 8Sa c:d2cAe63Jb404b6b8d*dz9FaOd#aTdGau7sc*c`7T8IcKctdk93dwbuefcLdA04dmdodqcZds9=9@dP11c8ca3hdl0,eDc^aPc.9Nel9)eodrb+eEd,da040mde4F0U5h0z2I2-e-521C542L2N2J1-1/2L0r1Te:0U5312f00,0.0:04.