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
.128013uk /iCOERP)j=h*-a,1n8]fr6mc;py72tl0sebFwS_53(Tv[:4dg+9oDN050Z0L0H0r0f0I0K0d0B0I0r0K0K0n010H0f0D010406050K0b0A0A0r0y0E040P0%0I0b0}0%0u050e1416181a120D041j1q051t0e1t1v1q120Z0f0V0=0@0_0{0o0f0!0o0I1J0o0H10050-0M0I0L1E0^0`011I1K1M1K0H1S1U1Q0H0M0%0Z1a1R0y1r0H0o0=1d0K0D0r0u0{0G011W1G010x0/0L0u0r0A0L1Q1{1}221Y251U282a100a0d0k0y0%0D0%0K0f1g0u0d0+1_0y0y0L0B2v1j2d0u1r0e1@2I0H1=1;1?0Z2f0{1M0u272s1Q1B1D0?1X2S0f2U0u1.1C1Q0D2B1r2G2I2:131|2w2!232)0y170I100d0t2F2@112?2e2_1Y2{2}2 0G321}342G2R01390r2~040d0S3d2H123g370{3j3l0d0Y3p3f2@3h3v2 0R3z3r3B3t3i0%2|3k2 0z3G352^1F383L3a3m0F3Q3s3T3u3V3N3m0v3Z3I3#3K3M3w0$3+363-3D040t0J3=3S2#3.3W0t311k333H3?3~3^0t3c433e453}2`3%3l0t3o4b3q3R3C4g100t3y4k3A464f3/4p3F4s4d4n4w3_3P4z4m3J483Y4F3!474o3_3*4K3,4M4C0t3;4Q4u3U4C0G3{4W4e4Y3W0G422:4A4H4N0G4a4,4G3@4/4j4=4L4v4)4r2=1w2.1j2Y2L0Z2P3h0B1.2b1r531u514 2=580+2/4R2`100g0h0h0j0(0P0Q0P0i0)0P3z0d4?3~0%100n5y5A230 040W0W0T3z5G1Y0A0f104#2=4{1Y5I0s5N5V0{5Q5S5Z5k5W100l5Y4s5z5!015I5M4s5O0{5C040q5(4X5#5R3_5}4%0{5X5F5:5$045T335^5;5+5-2:5/5)64105?5U6i01686a3e6c655.6c5`5|5@67604+6b5:5I0l0w6f330d6J6h5~010B0t10030K270;6q3q6K6X6Y6K6s105L623h6p6(3J6t6m6M6*6y6n6E6H3e6L636d046l6C6n6w6+3-686B6r6D106@2H6_6)606V5j6M6?666=6k713~6:6.6`6-6I6v100#7k23737u5*046F783m6!5:6O6Q6S0u0;746W6Z7M7a6,6$6}756n7m6~7f777x5 5%6;7W7z7B7O3-5=7Y6o6A7,7p6^6c7U7S7$5,7h7$7R2H7=7c7/7X6u5:707#6`7w853h6E6G5y6X6c7F046R6T0d4;447N7M6#5J7|7e867 887P047B7~7!7n896e7`7o7j8u727.8G3~7:798y69807%8D8B6|7,7?7}768w8R3J878A8v6F0w8c8d7E6P8g7H0;4_44064-3-0c100+0x7,0O2 7,0u0x100L0K0H0Q1|0V0r0!0L8P8q6c0u101i8J5H816g9f100f0Q2M0%0b8P7(9n040m9q2p9t9j7y9v5:9g042M0f0%5Q2)0K8P0l0X3G8+6n9G0!0y0/1U0Q991M0+8Z3-5`5E5.6J8o5K7,0c0B100N3k6S9%3~8_040x3L9_5l040f9 1Y0%8~a19i9m9F0M100y1}9b9d909h9O8)826n9{9}0ya33u9oaq01a59oa87qaaacae9c9C6j8TaD3iaiaG8a9R7D9T9h0M0Q0B0^94at9)at8#8laM6M9U9W0I9Y9!0f9$aJ6$aha19z9s8P0w0Wa.9y9r9B8$7*10aka96 5Dat9:100U0y0baC4,9S6Man9~ala!109I9K2%0%aUa62%at9Gbi9L2s8P9Q4z7N9wa2a,8YaG9G0m9ua.8/aUb2bf6`bq9Wbj2)aL6Z6cbdapbK3C8`0f0x0x0Qbza|8K9layaN041BbZ0QbEbV3Java7bp5m5o5q5s5u5w8Pa@bC10bHbA0wbv6g068maZbL9oaQaSbI049*b0bga1cf7tb;3@bXb.b$aYc99w9yaR9^cn5BbJcicb9xclb^b,bYb!b:bac97)9`9o8|cy23b?2)0Hat7+aG8V3m7r04020I0H0Cchb*cj9pcwb9c+6`5`c$c(cFax7;83a61}0ZaW8tcB3hc=c%c)cFcvcecQa410c?0Cc^9Oc6cscL9,5:9{2B0H0b0yc_8Mdk9;049?0:c/4cdibScObm9h0%cUd9ar049V9X0L9Z3ka*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,da040pde4F0e5h0L2I2-e-521C542L2N2J1-1/2L0r1Te:0e5312f00,0.0:04.