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,C:kn9DSvFsuO8;y7e[62-0w]r5_pag)R1iTN/=mhb4+j*odt cE(P3lf050W0s0X0E0J0(0l0Y0Z0(0E0l0l0N010X0J0D010406050l0m0O0O0E0A0q040i0V0(0m0}0V0f050M1416181a120D041j1q051t0M1t1v1q120W0J0j0=0@0_0{0P0J0F0P0(1J0P0X10050-0Q0(0s1E0^0`011I1K1M1K0X1S1U1Q0X0Q0V0W1a1R0A1r0X0P0=1d0l0D0E0f0{0v011W1G010)0/0s0f0E0O0s1Q1{1}221Y251U282a100a0Y0$0A0V0D0V0l0J1g0f0Y0+1_0A0A0s0Z2v1j2d0f1r0M1@2I0X1=1;1?0W2f0{1M0f272s1Q1B1D0?1X2S0J2U0f1.1C1Q0D2B1r2G2I2:131|2w2!232)0A170(100Y0I2F2@112?2e2_1Y2{2}2 0v321}342G2R01390E2~040Y0%3d2H123g370{3j3l0Y0R3p3f2@3h3v2 0B3z3r3B3t3i0V2|3k2 0u3G352^1F383L3a3m0r3Q3s3T3u3V3N3m0o3Z3I3#3K3M3w0g3+363-3D040I0x3=3S2#3.3W0I311k333H3?3~3^0I3c433e453}2`3%3l0I3o4b3q3R3C4g100I3y4k3A464f3/4p3F4s4d4n4w3_3P4z4m3J483Y4F3!474o3_3*4K3,4M4C0I3;4Q4u3U4C0v3{4W4e4Y3W0v422:4A4H4N0v4a4,4G3@4/4j4=4L4v4)4r2=1w2.1j2Y2L0W2P3h0Z1.2b1r531u514 2=580+2/4R2`100c0n0n0H0h0i0C0i0!0L0i3z0Y4?3~0V100N5y5A230 040t0t0#3z5G1Y0O0J104#2=4{1Y5I0b5N5V0{5Q5S5Z5k5W100G5Y4s5z5!015I5M4s5O0{5C040w5(4X5#5R3_5}4%0{5X5F5:5$045T335^5;5+5-2:5/5)64105?5U6i01686a3e6c655.6c5`5|5@67604+6b5:5I0G0z6f330Y6J6h5~010Z0I10030l270;6q3q6K6X6Y6K6s105L623h6p6(3J6t6m6M6*6y6n6E6H3e6L636d046l6C6n6w6+3-686B6r6D106@2H6_6)606V5j6M6?666=6k713~6:6.6`6-6I6v100S7k23737u5*046F783m6!5:6O6Q6S0f0;746W6Z7M7a6,6$6}756n7m6~7f777x5 5%6;7W7z7B7O3-5=7Y6o6A7,7p6^6c7U7S7$5,7h7$7R2H7=7c7/7X6u5:707#6`7w853h6E6G5y6X6c7F046R6T0Y4;447N7M6#5J7|7e867 887P047B7~7!7n896e7`7o7j8u727.8G3~7:798y69807%8D8B6|7,7?7}768w8R3J878A8v6F0z8c8d7E6P8g7H0;4_44064-3-0e100+0)7,0y2 7,0f0)100s0l0X0C1|0j0E0F0s8P8q6c0f101i8J5H816g9f100J0C2M0V0m8P7(9n040T9q2p9t9j7y9v5:9g042M0J0V5Q2)0l8P0G0d3G8+6n9G0F0A0/1U0C991M0+8Z3-5`5E5.6J8o5K7,0e0Z100k3k6S9%3~8_040)3L9_5l040J9 1Y0V8~a19i9m9F0Q100A1}9b9d909h9O8)826n9{9}0Aa33u9oaq01a59oa87qaaacae9c9C6j8TaD3iaiaG8a9R7D9T9h0Q0C0Z0^94at9)at8#8laM6M9U9W0(9Y9!0J9$aJ6$aha19z9s8P0z0ta.9y9r9B8$7*10aka96 5Dat9:100K0A0maC4,9S6Man9~ala!109I9K2%0VaUa62%at9Gbi9L2s8P9Q4z7N9wa2a,8YaG9G0T9ua.8/aUb2bf6`bq9Wbj2)aL6Z6cbdapbK3C8`0J0)0)0Cbza|8K9layaN041BbZ0CbEbV3Java7bp5m5o5q5s5u5w8Pa@bC10bHbA0zbv6g068maZbL9oaQaSbI049*b0bga1cf7tb;3@bXb.b$aYc99w9yaR9^cn5BbJcicb9xclb^b,bYb!b:bac97)9`9o8|cy23b?2)0Xat7+aG8V3m7r04020(0X0pchb*cj9pcwb9c+6`5`c$c(cFax7;83a61}0WaW8tcB3hc=c%c)cFcvcecQa410c?0pc^9Oc6cscL9,5:9{2B0X0m0Ac_8Mdk9;049?0:c/4cdibScObm9h0VcUd9ar049V9X0s9Z3ka*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,da040Ude4F0M5h0s2I2-e-521C542L2N2J1-1/2L0E1Te:0M5312f00,0.0:04.