Triominos et pavage (2)

Dans cet exercice, on considère un carré (avec un trou) dans une grille, dont le côté est une puissance de 2, et des triominos pour le paver. Il est recommandé d'avoir fait l'exercice Triominos et pavage ; on utilisera le même codage des triominos.

Objectif

On souhaite obtenir un pavage d'un carré troué par des triominos.

Écrire une fonction pavage_triominos qui prend en paramètres

• n : le côté d'un carré ; n sera une puissance de 2.
• i_trou : la ligne du trou
• j_trou : la colonne du trou

La fonction doit renvoyer une liste de triominos qui pave le carré troué. Chaque triomino est codé avec un tuple (i, j, sens) tel que défini dans l'exercice précédent ; i et j désignent la ligne et la colonne du carré central du triomino, et sens indique son orientation.

S'il est impossible d'obtenir un pavage, la fonction renverra None.

Dans cet exercice, on fournit et il sera possible d'utiliser la fonction est_pavage de l'exercice précédent pour vérifier votre pavage ; il n'est souvent pas unique. Tout pavage valide sera accepté.

Exemples

Premier exemple, ici le pavage est unique.

🐍 Console Python

>>> pavage_triominos(2, 1, 1)
[(0, 0, 3)]
>>> est_pavage(2, 1, 1, pavage_triominos(2, 1, 1))
True

Deuxième exemple, ici le pavage n'est pas unique.

🐍 Console Python

>>> pavage_triominos(4, 0, 1)
[(0, 3, 2), (1, 0, 1), (2, 2, 0), (3, 0, 1), (3, 3, 0)]
>>> est_pavage(4, 0, 1, pavage_triominos(4, 0, 1))
True

Troisième exemple, ici le pavage n'est pas unique.

🐍 Console Python

>>> est_pavage(8, 5, 4, pavage_triominos(8, 5, 4))
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

Exécuter le code
(Ctrl+S)Valider
Ctrl+Enter
(Clic droit pour l'historique)TéléchargerTéléverserRéinitialiser l'éditeurSauvegarder dans le navigateur

Évaluations restantes : 10/10

.128013vp5sq3[/(+n0P=g)ulFô.!;jS_a1ékti o94àm2:bfed,wyh]-86c7r050S0R0F0B0G0s0e0H0#0s0B0e0e0o010F0G0c010406050e0r0M0M0B0%0V040z0I0s0r0{0I0l050i12141618100c04051o1h1r0i1o100S0G0b0:0=0@0_0W0G0p0W0s1F0W0F0~050+0P0s0R1A0?0^011E1G1I1G0F1O1Q1M0F0%1p0F0W0:1b0e0c0B0l0_0N011S1C010Q0-0R0l0B0M0R1M1/1;1_1U1|1Q1 210~0a0H0n0%0I0c0I0e0G1e0l0H0)1-0%0%0R0#2m1h240l1p0i1+2z1(1*1)1N0S260_1I0l1~2j1M1x1z0;1T2J0G2L0l0I2P1M0c2s1p2x2z2%111:2n2R1`2W0%150s0~0H0C2w2+0 2*252-1U2/2;2?0N2_1;2{2x2I01300B2=040H0g342y10372~0_3a3c0H0K3g362+383m2?0d3q3i3s3k390I2:3b2?0!3x2|2,1B2 3C313d0$3H3j3K3l3M3E3d0Z3Q3z3S3B3D3n0J3Y2}3!3u040C0m3)3J2S3#3N0C2^1i2`3y3*3=3,0C333`353|3;2.3U3c0C3f423h3I3t470~0C3p4b3r3}463$4g3w4j444e4n3-3G4q4d3A3 3P4w3R3~4f3-3X4B3Z4D4t0C3(4H4l3L4t0N3/4N454P3N0N3_2%4r4y4E0N414Z4x3+4$4a4)4C4m4W4i4.4I4:3V0N4p4?4O3T4Q4v4|4U4~4W4A514s4W4G564#4Q4M5a4+4t0g4S5e4J3N0g4Y3{4*5k3V0g4(5o4/4V5r4-5u4@5w3c0g4=5z4}3?5r4{5F525H5C505K575r555P5b5l595T5f5l5d5X5q3c0K5i5#4^5%5n435p5+0~0K5t5.5v533V0K5y5@5A5_5%5E5}5G3,0K5J625L645O675Q5%5S6b5U5`5W6f5Y5`5!6j5$0~0d5)351s2#1h2P2C0S1*2H3A0#2X221p6w1q6u2)4j056C0)2$5~010e0S0~020f0r0I0F0x6U6W6Y6!6X0x3:386R0~0t1f2u0G1f2o0G1/1f0G1P1R0O3x4!3!6,040R0e0F0A1:0b0B0p0R0j0l0T0H0G0A1(0I0r7e0y7h2g7k0H1(6;0M2U2j0q6*3A710H7A0H2s0l0b0I0G1R0r2n0P0I1b0D1~7x706S3d7B0S0D0F0R2:2U1R2k0H1Q0/7r0I7t2W0/771~0F0H7J0:160%0D2o1R0#0u0F7`2n0B0V1;7;7?7i0r7f0l1x6V0D7Q3=716%6$6V6(8h6)4q066 3=0E0~0)0Q3q5/1U0U2?8v5^390Q0~77790R7n7s7u0e8A6P0}040j8M630~1g6K8B8O0T3q0H8w3l0~7g878R5L8X8Z8#390~7m8)8V8N0~0q6}4q7B8!8B0l0~2s120s0+0F8-8B0I0~0o968@040h0X3x8|8.8r040G8u4j8}6P8 048U2%9o5G98040o9a9n8.7t4g8*388O8`4Z8|9h8B9j2s0F0r0%9s2`9u6890730r930B958{7B8.9q0M9b9v999*9U9r9-389w0i0i9:3A9C045?3h9K6P9j9l9^3+8%7n7ja23=9w02938m9t9%0~9)8?5G9G8Z9T380#0C0~037%1R870H737;1~0H0W0B1d9g9J7A9i8%9mad8~8:a50ra71`a9abaN2 af9E3Aaj9nal6Bao04aq1Q7q7oau740H0L0H0paA0#0W0RaCaD9~5G9j0Q3CaR0_8O8Qah9.0GaU3!8,9AaJ040yb53=b7aI9p0~8Lb29F8^a~010I8y9k9R35aYa3048F7a8I7+8Kbc1`b0bBaS04ag2)8W0~8Yb8bg9kaLbEa bKbm9q8;7obQ018O8_a@a^aDae04919X94bX9w0vbX9q0B0c0c1~0SbXb0b1bIbNb4bjaVbSbM8Sbab`c2bfc4bib}ai8^7w9#b$aEb90e1~ca9S8.9w9zc85L9`6r9}cgchbNb*9Y9!cb5Lb.b:0~b=b@8ac68Pb|2`b(bHcMbJ04bLcq3taTc0b6c7cmcickcJ0qce9Ia^aF720.a?cWbd0~9H9Sbt3=anapara(7ja*7;a-0S2g2lc.c)cvc+a|0%bmbDc/2.8%cJcScZbNbbdc1Ubedhc9c$bmbo8%br2yc@ddbv0B78bx7*7,2jcJcL6sb9cOdG9cdgbsb(8(bWdkbRcRbTaK8=cT3A9w0YdTbGc$c=43cvb%b9cyb,dQbn0~b/d.b;b?b^dEdF2ydNdfd!djdW3!9w0kd!dId{cQdLdub(cldJcc04c%b#b$eac#c3cC9,ek389`5-cud6d+9Wczb-d:cE04cGd^d.b{eye56Oede83dcNdq0~dZen9_0G9DeCcYdMc!0lebe69cefcfdv1U9j0Rc-cJd%due$0_c_a#c{atavau7K0?eg9$9LaGd~bPeOe16TaQf13~cVcBbk04e,7T8.e:a$asa)e@a-a/0ra;d43{d)e.01a{a}f5bC0~d`eGb3d}fubFd cPdKd!eXfyf9c(dncCbp2Ud!bw8HdBbAeS8PeEfAe0f6bOdVfL9;eMe4fXf$4ydUdPf8c1eefb06fpa_9.d,9Zew04d;f/bueAcIfU0jfxd|fB0_e2f)fUeIfqbUf*eUbNfH8.bZfKd(d)eieWeL9xbm9`9|0 fpb(f`cAfE9+f}eyg1b_g3g5dHgqeNfY1`epgfe9gIgbfGejf c:eegler9Jc+e)cje+akfda!ffc|88fi2od27Xe{d*9 0~d8dafweyb gUfvdSg78/c5gRh19qgicQgXeJ97fNdthabNfQbydCh79cgHbNeFgjeTgPb~f0gL1UdYgag~dlhphec4bVa6h1hvh5f7gA8+8^f=f@e|cxeud-hxg8exd=cFd@g2hRbYfwhlc4g}f+f204e3hGd#h4ht8$h3h/d/h*hwhIf9gceac$h9f?gneVfHfqcogseQ045|gYehet92hQh_dXhThYd?cHgFhYeDhUh-h=hFh=gNh.h(fZeFi3f(h1isilhzgdbhgTiecXgW6~f^38a0aHiudwcjgphE0~0wcpiO1Ucsg%e#iK3Afsd9h1dbihdeitgghBgOhA9.hjedh9i3hcfPdy8GhhfTiBfVinhne7h^i.el04gKiW0_iAiGgVh{gQipiyiri6eqfIf:b!i!c*ibb+f{d.cDingEd_g|i:iDh;jdg jfghh}b#c+a1h,iQi2cniTiVj6eojkiZd5gZe}04g_i)g{inh%echJh0h=gei-hqdofUi^cni`h,hgfS7-dEfWj-i;cUiojah?j9jRePeRj0jF5GiYj:hLi0hOicjthYjvi+ezhWikjDhycKjzj}jBfDk4h)h+j+hHj(h`fGjHe#jJiNkufZjMgqiUi50~guhofag=fqi%g`j1kjj%eYeHd~jAh|j:dqj?kxdxdzfR0%8Jj`g3j|k7kL04ctjmiHk89.iwjOj8k?jlkOjojViakejsgzkzifgCjwkljyj$gqkwk19(k!b9ktkXj)k{j i?j)e!jVkEgSiRjh04kKizi6i8k_gVkcg?a`g^fth=i*knh:kWlEjEkZkrk#j0j;hbdsi{k+i~k/j0h#k|lk6Pkak=lB0~k^l2lGcggxhPkglNh?f~l`iieBl%l(j lPixh@h,j3fFh,lmj~lalhkGdwm7kYjLkClujX9N9PhdjBgy3H0i6M0R2z2!mu6v1y6x2C2F2A0B6{2z6w100i0)0+0-0e04.

Indice 1

Si le carré est une puissance de deux, on peut le couper en 4.

• le petit carré qui contient le trou peut être pavé par récursivité.
• pour les trois autres, on place un triomino commun, de sorte qu'il reste à paver un petit carré qui possède un trou à un coin.

Indice 2

Pour paver les trois autres carrés avec un trou dans un coin, on peut utiliser de la récursivité et un décalage sur le pavage obtenu.

Écrire chaque cas pourra s'avérer un peu long. Mais il est possible de factoriser le code, étudier le corrigé en ce sens.

Indice 3

On pourra utiliser le squelette de code

🐍 Script Python

def pavage_triominos(n, i_trou, j_trou):
    resultat = []
    if n == 1:
        return ...
    m = n // 2
    if i_trou < m:  # le trou est en haut
        if j_trou < m:  # le trou est à gauche
            ...
        else:           # le trou est à droite
            ...
    else:           # le trou est en bas
        ...

    ...
    return resultat