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, Ow*5e(8CR0pkDojicE6TS1vd:Fy24fln-]93m=)rh[us;b/t_gaP+N7050A0h0Y0#0s0H0U0c0t0H0#0U0U0O010Y0s0n010406050U0T0N0N0#0Q0D040x0q0H0T0}0q0I050X1416181a120n041j1q051t0X1t1v1q120A0s0z0=0@0_0{0R0s0!0R0H1J0R0Y10050-0W0H0h1E0^0`011I1K1M1K0Y1S1U1Q0Y0W0q0A1a1R0Q1r0Y0R0=1d0U0n0#0I0{0E011W1G010G0/0h0I0#0N0h1Q1{1}221Y251U282a100a0c0$0Q0q0n0q0U0s1g0I0c0+1_0Q0Q0h0t2v1j2d0I1r0X1@2I0Y1=1;1?0A2f0{1M0I272s1Q1B1D0?1X2S0s2U0I1.1C1Q0n2B1r2G2I2:131|2w2!232)0Q170H100c0y2F2@112?2e2_1Y2{2}2 0E321}342G2R01390#2~040c0M3d2H123g370{3j3l0c0F3p3f2@3h3v2 0g3z3r3B3t3i0q2|3k2 0v3G352^1F383L3a3m0)3Q3s3T3u3V3N3m0j3Z3I3#3K3M3w0L3+363-3D040y0m3=3S2#3.3W0y311k333H3?3~3^0y3c433e453}2`3%3l0y3o4b3q3R3C4g100y3y4k3A464f3/4p3F4s4d4n4w3_3P4z4m3J483Y4F3!474o3_3*4K3,4M4C0y3;4Q4u3U4C0E3{4W4e4Y3W0E422:4A4H4N0E4a4,4G3@4/4j4=4L4v4)4r2=1w2.1j2Y2L0A2P3h0t1.2b1r531u514 2=580+2/4R2`100k0d0d0l0p0x0Z0x0u0(0x3z0c4?3~0q100O5y5A230 040S0S0i3z5G1Y0N0s104#2=4{1Y5I0b5N5V0{5Q5S5Z5k5W100P5Y4s5z5!015I5M4s5O0{5C040J5(4X5#5R3_5}4%0{5X5F5:5$045T335^5;5+5-2:5/5)64105?5U6i01686a3e6c655.6c5`5|5@67604+6b5:5I0P0K6f330c6J6h5~010t0y10030U270;6q3q6K6X6Y6K6s105L623h6p6(3J6t6m6M6*6y6n6E6H3e6L636d046l6C6n6w6+3-686B6r6D106@2H6_6)606V5j6M6?666=6k713~6:6.6`6-6I6v100%7k23737u5*046F783m6!5:6O6Q6S0I0;746W6Z7M7a6,6$6}756n7m6~7f777x5 5%6;7W7z7B7O3-5=7Y6o6A7,7p6^6c7U7S7$5,7h7$7R2H7=7c7/7X6u5:707#6`7w853h6E6G5y6X6c7F046R6T0c4;447N7M6#5J7|7e867 887P047B7~7!7n896e7`7o7j8u727.8G3~7:798y69807%8D8B6|7,7?7}768w8R3J878A8v6F0K8c8d7E6P8g7H0;4_44064-3-0o100+0G7,0e2 7,0I0G100h0U0Y0Z1|0z0#0!0h8P8q6c0I101i8J5H816g9f100s0Z2M0q0T8P7(9n040r9q2p9t9j7y9v5:9g042M0s0q5Q2)0U8P0P0B3G8+6n9G0!0Q0/1U0Z991M0+8Z3-5`5E5.6J8o5K7,0o0t100C3k6S9%3~8_040G3L9_5l040s9 1Y0q8~a19i9m9F0W100Q1}9b9d909h9O8)826n9{9}0Qa33u9oaq01a59oa87qaaacae9c9C6j8TaD3iaiaG8a9R7D9T9h0W0Z0t0^94at9)at8#8laM6M9U9W0H9Y9!0s9$aJ6$aha19z9s8P0K0Sa.9y9r9B8$7*10aka96 5Dat9:100w0Q0TaC4,9S6Man9~ala!109I9K2%0qaUa62%at9Gbi9L2s8P9Q4z7N9wa2a,8YaG9G0r9ua.8/aUb2bf6`bq9Wbj2)aL6Z6cbdapbK3C8`0s0G0G0Zbza|8K9layaN041BbZ0ZbEbV3Java7bp5m5o5q5s5u5w8Pa@bC10bHbA0Kbv6g068maZbL9oaQaSbI049*b0bga1cf7tb;3@bXb.b$aYc99w9yaR9^cn5BbJcicb9xclb^b,bYb!b:bac97)9`9o8|cy23b?2)0Yat7+aG8V3m7r04020H0Y0Vchb*cj9pcwb9c+6`5`c$c(cFax7;83a61}0AaW8tcB3hc=c%c)cFcvcecQa410c?0Vc^9Oc6cscL9,5:9{2B0Y0T0Qc_8Mdk9;049?0:c/4cdibScObm9h0qcUd9ar049V9X0h9Z3ka*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,da040fde4F0X5h0h2I2-e-521C542L2N2J1-1/2L0#1Te:0X5312f00,0.0:04.