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

Indices

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.

Version videVersion à compléter

Évaluations restantes : 10/10

.1280131=0(P-5tiS8;lmsf+àok.e/9cw,[):!n23phuvrby_]dg 467ja050S0w0i0Z0j0n0p0U0z0n0Z0p0p0c010i0j0J010406050p0L0o0o0Z0N0P040k0t0n0L0@0t0G050x0~1012140|0J041d1k051n0x1n1p1k0|0S0j0M0,0.0:0=0K0j0T0K0n1D0K0i0`050%0O0n0w1y0/0;011C1E1G1E0i1M1O1K0i0O0t0S141L0N1l0i0K0,170p0J0Z0G0=0H011Q1A010q0)0w0G0Z0o0w1K1=1@1|1S1 1O22240`0a0U0f0N0t0J0t0p0j1a0G0U0#1:0N0N0w0z2p1d270G1l0x1.2C0i1,1+1-0S290=1G0G212m1K1v1x0-1R2M0j2O0G1(1w1K0J2v1l2A2C2*0}1?2q2U1}2Z0N110n0`0U0b2z2.0{2-282:1S2=2@2_0H2|1@2~2A2L01330Z2^040U0I372B0|3a310=3d3f0U0V3j392.3b3p2_0h3t3l3v3n3c0t2?3e2_0W3A2 2/1z323F343g0X3K3m3N3o3P3H3g0l3T3C3V3E3G3q0y3#303%3x040b0d3,3M2V3(3Q0b2{1e2}3B3-3^3/0b363}383 3@2;3X3f0b3i453k3L3w4a0`0b3s4e3u40493)4j3z4m474h4q3:3J4t4g3D423S4z3U414i3:3!4E3$4G4w0b3+4K4o3O4w0H3=4Q484S3Q0H3|2*4u4B4H0H444$4A3.4)4d4,4F4p4Z4l4;4L4?3Y0H4s4_4R3W4T4y4 4X514Z4D544v4Z4J594(4T4P5d4.4w0I4V5h4M3Q0I4#3~4-5n3Y0I4+5r4=4Y5u4:5x4`5z3f0I4^5C503_5u4~5I555K5F535N5a5u585S5e5o5c5W5i5o5g5!5t3f0V5l5(4{5*5q381m2(1d2S2F0S2J3b0z1(251l5^1o5?2,4m055}0#2)5D0=0u0`0#0q3t5s1}0A2_6g5y3o0q0`1?0M0Z0T0w0Q2G0j0t0o2X2m6l6a010_040e6C5J0G0`1c656m6E0`0B3t0U6h320`0j6v2j0L6I5O6F6R4m6T6O6K040Y6Y0t6!6N6D6F0D0E3A0U6{6*6D6,2v0~0n0%0i6S6U0=0t0`0c756O6F0C0R6`6|76016c040j6f6)7i6,6M2*6}5J78040c7a7o6O6z4j6#3b6F6_4t6|7I7t5O7k2v0i0L0N7r2}7K3w0`700L720Z747H7h6+0`0o7b6D7v7y7s7p6L7*7u0`0x0x7;5O7B045w467I7i7k7m7_7U7l6/6;7.6O7v02720m834B7(7D3D7F6S7T3D0z0b0`030U1O0U2G6:0U0w0p0i8w2q0K0Z197g7J8l3%817n886~0`6.8u877S7i8a8c8e3.8g6=5J8j6)8H3^8n8p8r1P8P8w8y0U0s0U0T8D0z0K0w8F8G7$6D7k0q3F8V3^6F6H8Y5O6,0j8h3%6%912;8N99926Q9c6V040p9f1}6@9i776j7l7R388$9d046q6s6u6w6y6A9l957E0`942,7%047)9F8i9h7z8M858P9m1S9b9Q6J8N869U0=6@7G4$8{9*9v9j7W7Y7!9J7+0`0v9#3c0`0Z0J0J210S9^939I2}7/7la09P8L9Y6-a6046(a8960`9E9;8Z0`0D0D8`9*a40p21ah8R89799p017{5,7~9+6{a49.739^7v9@9N8W049{9}0G9 aJ9g6Ga25;9K9Mai6$a7at9RaWa37caZ9uaparabalan8|5J7k0w0*8_aQ9n0`9(7S9,0=8(048q8s8,8x8z8:0S2j2oa^9)aBa~7j0`8 0Naw939^97abada!a90Ybnaw6,asaU6?akaw0t9r2Xbt6p0Z6r6t6Y6x6z2Zbv2B7ibka_9ja$bwajacbD9S6Zbs9Xaf6-9!b!3b7v0gbWbSbNa(046^a/aBaD8x7XaFbQ779?bl9`9|9~ab0eaTb.9R98b{6PbVb(8faacb3%7v0rb,bZae84bM69bUa.7#b?9Kaq0Gcmbe7,aw7{5:3kbdbe6 b^9/aGb}c86,aMc1c8a1b~9Lcjbpb#b-3g8S0`b+ce3^czcRa*csa,cNakamcqbea=a@aba|9ubeb0b28+6Z8-8z210U0O0/b=c.6W8KcS848ObYcZ1}8T0i8ddabRc;8k7ic^8*8tc{b58/8;8?8^d27 6O8~90df9$9HcPc7aX9Gcackccbrc*dFd6cccmbObydy01bA6W9t2BcDbEbG9A0NbJ9Dc2cPcUdOdKc%c6b%dGcfcXcidJbod,bqd.a%bxb:c=cBcCa:b#aE7ZcH04aIdDcccLaOc2c4cnb#dCdLd:04chdQ6,d)b/d@dVa4dIe89aa)eqcsa-c,bccr9RctcvcW7wcy0j0`7}d eBa9e39:d{7=e6cPeaaPetaRc3d(bzd;dQc#d?d=eWa`d+eweCc)e*9Vc+d2800`a?aqdh8#dj8ob1dlb48.b7b90ibb3~cCe@04bhbjdAcJ6Wc$e-bqfgcVexdJezeh3^dS9sbW9ybH9BbK6BdJeda4end|epfkd-9TdQb*e)eQaYe,fEd_fGd/fpe#fQ9wfBcod~0{e0e184eOe5e7fK84eUecdBe!ejfJbTfLfDdWcdfT1Scgf:c5bUf?apeydtf!dMe/fodbave$eI045BaAeMe2cFb`e:b|eSfeaLc0ebfyfzaVf.cYf_0=e%gic9f grfHfSg61Sgwf)9OfMf@eDg14t06du8}d4bWgKgB040F7-gDgvgaazf}fLfXgN8{f9fbdQbPgxbme(el9eg:gu9_9ka-bzbBdUfNb#ftdZd#bLd%glfVf=f|g~b)gCd^7`gacAeedEgza#gseH7Cfmg%f89Kf$c8aHeTgneVgGeuaSf-g?gXg^eshxaRhia9dNb/cpeAd37ld5hcclg5hQ3D7vgVhl3:e{hMgOa;bgdxg@g-hF9wegf;hhbWhEh.gHhHb#hJd|fnhTcfg|fsbF9zbI9Ch3fyeZhBh|418Xg@fIg9hmgx9Wg@aya-hobdb@71ghh+f`cIg.b aNhwh=hyeYglh-g#h/g;f^hCf{iDh6iCg@bugLhMf982iDgSib0`hWid7|hZf7g)dvh%big,fdisa5i7fhb#h;iBh?gRg`fHh~iDh0i2fwh_bUgqhji+h93Diij0f@cUcwhbi,3bgFiwaRb;c-aohqgge4hsirip3oitcMif9Hi~a9iAj1eiekiKiajmgyh:fjgJiMiYaCi!hOgRhSj9hUiTgWi81}7{gci/hyik8Gg*h(hCh*jch,jDerj(fljqb:g{dTh dYi`d$i5h5j*6Dj3j,h@jagZijg2jH9Rhrgxhtglf+gphAiSf/iHj_figTjxhCemkeh^jFgdhN7N7Pg}f@k45r0x670w2C2%kx5@1w5_2F2H2D1%1)2F0Z1NkA0x5^0|kN0$0(0*04.

Évaluations restantes : 10/10

.1280131=0(P-5tiS8;lmsf+àok.e/9cw,[):!n23phuvrby_]dg 467ja050S0w0i0Z0j0n0p0U0z0n0Z0p0p0c010i0j0J010406050p0L0o0o0Z0N0P040k0t0n0L0@0t0G050x0~1012140|0J041d1k051n0x1n1p1k0|0S0j0M0,0.0:0=0K0j0T0K0n1D0K0i0`050%0O0n0w1y0/0;011C1E1G1E0i1M1O1K0i0O0t0S141L0N1l0i0K0,170p0J0Z0G0=0H011Q1A010q0)0w0G0Z0o0w1K1=1@1|1S1 1O22240`0a0U0f0N0t0J0t0p0j1a0G0U0#1:0N0N0w0z2p1d270G1l0x1.2C0i1,1+1-0S290=1G0G212m1K1v1x0-1R2M0j2O0G1(1w1K0J2v1l2A2C2*0}1?2q2U1}2Z0N110n0`0U0b2z2.0{2-282:1S2=2@2_0H2|1@2~2A2L01330Z2^040U0I372B0|3a310=3d3f0U0V3j392.3b3p2_0h3t3l3v3n3c0t2?3e2_0W3A2 2/1z323F343g0X3K3m3N3o3P3H3g0l3T3C3V3E3G3q0y3#303%3x040b0d3,3M2V3(3Q0b2{1e2}3B3-3^3/0b363}383 3@2;3X3f0b3i453k3L3w4a0`0b3s4e3u40493)4j3z4m474h4q3:3J4t4g3D423S4z3U414i3:3!4E3$4G4w0b3+4K4o3O4w0H3=4Q484S3Q0H3|2*4u4B4H0H444$4A3.4)4d4,4F4p4Z4l4;4L4?3Y0H4s4_4R3W4T4y4 4X514Z4D544v4Z4J594(4T4P5d4.4w0I4V5h4M3Q0I4#3~4-5n3Y0I4+5r4=4Y5u4:5x4`5z3f0I4^5C503_5u4~5I555K5F535N5a5u585S5e5o5c5W5i5o5g5!5t3f0V5l5(4{5*5q381m2(1d2S2F0S2J3b0z1(251l5^1o5?2,4m055}0#2)5D0=0u0`0#0q3t5s1}0A2_6g5y3o0q0`1?0M0Z0T0w0Q2G0j0t0o2X2m6l6a010_040e6C5J0G0`1c656m6E0`0B3t0U6h320`0j6v2j0L6I5O6F6R4m6T6O6K040Y6Y0t6!6N6D6F0D0E3A0U6{6*6D6,2v0~0n0%0i6S6U0=0t0`0c756O6F0C0R6`6|76016c040j6f6)7i6,6M2*6}5J78040c7a7o6O6z4j6#3b6F6_4t6|7I7t5O7k2v0i0L0N7r2}7K3w0`700L720Z747H7h6+0`0o7b6D7v7y7s7p6L7*7u0`0x0x7;5O7B045w467I7i7k7m7_7U7l6/6;7.6O7v02720m834B7(7D3D7F6S7T3D0z0b0`030U1O0U2G6:0U0w0p0i8w2q0K0Z197g7J8l3%817n886~0`6.8u877S7i8a8c8e3.8g6=5J8j6)8H3^8n8p8r1P8P8w8y0U0s0U0T8D0z0K0w8F8G7$6D7k0q3F8V3^6F6H8Y5O6,0j8h3%6%912;8N99926Q9c6V040p9f1}6@9i776j7l7R388$9d046q6s6u6w6y6A9l957E0`942,7%047)9F8i9h7z8M858P9m1S9b9Q6J8N869U0=6@7G4$8{9*9v9j7W7Y7!9J7+0`0v9#3c0`0Z0J0J210S9^939I2}7/7la09P8L9Y6-a6046(a8960`9E9;8Z0`0D0D8`9*a40p21ah8R89799p017{5,7~9+6{a49.739^7v9@9N8W049{9}0G9 aJ9g6Ga25;9K9Mai6$a7at9RaWa37caZ9uaparabalan8|5J7k0w0*8_aQ9n0`9(7S9,0=8(048q8s8,8x8z8:0S2j2oa^9)aBa~7j0`8 0Naw939^97abada!a90Ybnaw6,asaU6?akaw0t9r2Xbt6p0Z6r6t6Y6x6z2Zbv2B7ibka_9ja$bwajacbD9S6Zbs9Xaf6-9!b!3b7v0gbWbSbNa(046^a/aBaD8x7XaFbQ779?bl9`9|9~ab0eaTb.9R98b{6PbVb(8faacb3%7v0rb,bZae84bM69bUa.7#b?9Kaq0Gcmbe7,aw7{5:3kbdbe6 b^9/aGb}c86,aMc1c8a1b~9Lcjbpb#b-3g8S0`b+ce3^czcRa*csa,cNakamcqbea=a@aba|9ubeb0b28+6Z8-8z210U0O0/b=c.6W8KcS848ObYcZ1}8T0i8ddabRc;8k7ic^8*8tc{b58/8;8?8^d27 6O8~90df9$9HcPc7aX9Gcackccbrc*dFd6cccmbObydy01bA6W9t2BcDbEbG9A0NbJ9Dc2cPcUdOdKc%c6b%dGcfcXcidJbod,bqd.a%bxb:c=cBcCa:b#aE7ZcH04aIdDcccLaOc2c4cnb#dCdLd:04chdQ6,d)b/d@dVa4dIe89aa)eqcsa-c,bccr9RctcvcW7wcy0j0`7}d eBa9e39:d{7=e6cPeaaPetaRc3d(bzd;dQc#d?d=eWa`d+eweCc)e*9Vc+d2800`a?aqdh8#dj8ob1dlb48.b7b90ibb3~cCe@04bhbjdAcJ6Wc$e-bqfgcVexdJezeh3^dS9sbW9ybH9BbK6BdJeda4end|epfkd-9TdQb*e)eQaYe,fEd_fGd/fpe#fQ9wfBcod~0{e0e184eOe5e7fK84eUecdBe!ejfJbTfLfDdWcdfT1Scgf:c5bUf?apeydtf!dMe/fodbave$eI045BaAeMe2cFb`e:b|eSfeaLc0ebfyfzaVf.cYf_0=e%gic9f grfHfSg61Sgwf)9OfMf@eDg14t06du8}d4bWgKgB040F7-gDgvgaazf}fLfXgN8{f9fbdQbPgxbme(el9eg:gu9_9ka-bzbBdUfNb#ftdZd#bLd%glfVf=f|g~b)gCd^7`gacAeedEgza#gseH7Cfmg%f89Kf$c8aHeTgneVgGeuaSf-g?gXg^eshxaRhia9dNb/cpeAd37ld5hcclg5hQ3D7vgVhl3:e{hMgOa;bgdxg@g-hF9wegf;hhbWhEh.gHhHb#hJd|fnhTcfg|fsbF9zbI9Ch3fyeZhBh|418Xg@fIg9hmgx9Wg@aya-hobdb@71ghh+f`cIg.b aNhwh=hyeYglh-g#h/g;f^hCf{iDh6iCg@bugLhMf982iDgSib0`hWid7|hZf7g)dvh%big,fdisa5i7fhb#h;iBh?gRg`fHh~iDh0i2fwh_bUgqhji+h93Diij0f@cUcwhbi,3bgFiwaRb;c-aohqgge4hsirip3oitcMif9Hi~a9iAj1eiekiKiajmgyh:fjgJiMiYaCi!hOgRhSj9hUiTgWi81}7{gci/hyik8Gg*h(hCh*jch,jDerj(fljqb:g{dTh dYi`d$i5h5j*6Dj3j,h@jagZijg2jH9Rhrgxhtglf+gphAiSf/iHj_figTjxhCemkeh^jFgdhN7N7Pg}f@k45r0x670w2C2%kx5@1w5_2F2H2D1%1)2F0Z1NkA0x5^0|kN0$0(0*04.