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
.128013](wdef+nO5r-F3EjuRa/;lbC)8pg[o D7khm:vT,P1Ssi9*y0_t4N2c6=050e0f0Z0t0T0w0S0F0%0w0t0S0S0)010Z0T0B010406050S0r0K0K0t0l0W040R0E0w0r0}0E0i050u1416181a120B041j1q051t0u1t1v1q120e0T0M0=0@0_0{0J0T0C0J0w1J0J0Z10050-0x0w0f1E0^0`011I1K1M1K0Z1S1U1Q0Z0x0E0e1a1R0l1r0Z0J0=1d0S0B0t0i0{0$011W1G010g0/0f0i0t0K0f1Q1{1}221Y251U282a100a0F0P0l0E0B0E0S0T1g0i0F0+1_0l0l0f0%2v1j2d0i1r0u1@2I0Z1=1;1?0e2f0{1M0i272s1Q1B1D0?1X2S0T2U0i1.1C1Q0B2B1r2G2I2:131|2w2!232)0l170w100F0Q2F2@112?2e2_1Y2{2}2 0$321}342G2R01390t2~040F0o3d2H123g370{3j3l0F0!3p3f2@3h3v2 0k3z3r3B3t3i0E2|3k2 0(3G352^1F383L3a3m0H3Q3s3T3u3V3N3m0A3Z3I3#3K3M3w0U3+363-3D040Q0X3=3S2#3.3W0Q311k333H3?3~3^0Q3c433e453}2`3%3l0Q3o4b3q3R3C4g100Q3y4k3A464f3/4p3F4s4d4n4w3_3P4z4m3J483Y4F3!474o3_3*4K3,4M4C0Q3;4Q4u3U4C0$3{4W4e4Y3W0$422:4A4H4N0$4a4,4G3@4/4j4=4L4v4)4r2=1w2.1j2Y2L0e2P3h0%1.2b1r531u514 2=580+2/4R2`100y0j0j0s0G0R0Y0R0p0#0R3z0F4?3~0E100)5y5A230 040D0D0c3z5G1Y0K0T104#2=4{1Y5I0O5N5V0{5Q5S5Z5k5W100z5Y4s5z5!015I5M4s5O0{5C040m5(4X5#5R3_5}4%0{5X5F5:5$045T335^5;5+5-2:5/5)64105?5U6i01686a3e6c655.6c5`5|5@67604+6b5:5I0z0b6f330F6J6h5~010%0Q10030S270;6q3q6K6X6Y6K6s105L623h6p6(3J6t6m6M6*6y6n6E6H3e6L636d046l6C6n6w6+3-686B6r6D106@2H6_6)606V5j6M6?666=6k713~6:6.6`6-6I6v100h7k23737u5*046F783m6!5:6O6Q6S0i0;746W6Z7M7a6,6$6}756n7m6~7f777x5 5%6;7W7z7B7O3-5=7Y6o6A7,7p6^6c7U7S7$5,7h7$7R2H7=7c7/7X6u5:707#6`7w853h6E6G5y6X6c7F046R6T0F4;447N7M6#5J7|7e867 887P047B7~7!7n896e7`7o7j8u727.8G3~7:798y69807%8D8B6|7,7?7}768w8R3J878A8v6F0b8c8d7E6P8g7H0;4_44064-3-0I100+0g7,0d2 7,0i0g100f0S0Z0Y1|0M0t0C0f8P8q6c0i101i8J5H816g9f100T0Y2M0E0r8P7(9n040q9q2p9t9j7y9v5:9g042M0T0E5Q2)0S8P0z0L3G8+6n9G0C0l0/1U0Y991M0+8Z3-5`5E5.6J8o5K7,0I0%100n3k6S9%3~8_040g3L9_5l040T9 1Y0E8~a19i9m9F0x100l1}9b9d909h9O8)826n9{9}0la33u9oaq01a59oa87qaaacae9c9C6j8TaD3iaiaG8a9R7D9T9h0x0Y0%0^94at9)at8#8laM6M9U9W0w9Y9!0T9$aJ6$aha19z9s8P0b0Da.9y9r9B8$7*10aka96 5Dat9:100N0l0raC4,9S6Man9~ala!109I9K2%0EaUa62%at9Gbi9L2s8P9Q4z7N9wa2a,8YaG9G0q9ua.8/aUb2bf6`bq9Wbj2)aL6Z6cbdapbK3C8`0T0g0g0Ybza|8K9layaN041BbZ0YbEbV3Java7bp5m5o5q5s5u5w8Pa@bC10bHbA0bbv6g068maZbL9oaQaSbI049*b0bga1cf7tb;3@bXb.b$aYc99w9yaR9^cn5BbJcicb9xclb^b,bYb!b:bac97)9`9o8|cy23b?2)0Zat7+aG8V3m7r04020w0Z0vchb*cj9pcwb9c+6`5`c$c(cFax7;83a61}0eaW8tcB3hc=c%c)cFcvcecQa410c?0vc^9Oc6cscL9,5:9{2B0Z0r0lc_8Mdk9;049?0:c/4cdibScObm9h0EcUd9ar049V9X0f9Z3ka*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,da040Vde4F0u5h0f2I2-e-521C542L2N2J1-1/2L0t1Te:0u5312f00,0.0:04.