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.

###(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,:ag)1ikn9/àS=vmsuhb.84;y7e[6+j2o-dt c0(!w]r5_P3plf050J0B0K0d0h0Y0r0L0M0Y0d0r0r0o010K0h0X010406050r0s0q0q0d0S0z040n0H0Y0s0@0H0j050l0~1012140|0X041d1k051n0l1n1p1k0|0J0h0p0,0.0:0=0t0h0e0t0Y1D0t0K0`050%0u0Y0B1y0/0;011C1E1G1E0K1M1O1K0K0u0H0J141L0S1l0K0t0,170r0X0d0j0=0G011Q1A010Z0)0B0j0d0q0B1K1=1@1|1S1 1O22240`0a0L0V0S0H0X0H0r0h1a0j0L0#1:0S0S0B0M2p1d270j1l0l1.2C0K1,1+1-0J290=1G0j212m1K1v1x0-1R2M0h2O0j1(1w1K0X2v1l2A2C2*0}1?2q2U1}2Z0S110Y0`0L0g2z2.0{2-282:1S2=2@2_0G2|1@2~2A2L01330d2^040L0W372B0|3a310=3d3f0L0x3j392.3b3p2_0T3t3l3v3n3c0H2?3e2_0D3A2 2/1z323F343g0A3K3m3N3o3P3H3g0w3T3C3V3E3G3q0k3#303%3x040g0N3,3M2V3(3Q0g2{1e2}3B3-3^3/0g363}383 3@2;3X3f0g3i453k3L3w4a0`0g3s4e3u40493)4j3z4m474h4q3:3J4t4g3D423S4z3U414i3:3!4E3$4G4w0g3+4K4o3O4w0G3=4Q484S3Q0G3|2*4u4B4H0G444$4A3.4)4d4,4F4p4Z4l4;4L4?3Y0G4s4_4R3W4T4y4 4X514Z4D544v4Z4J594(4T4P5d4.4w0W4V5h4M3Q0W4#3~4-5n3Y0W4+5r4=4Y5u4:5x4`5z3f0W4^5C503_5u4~5I555K5F535N5a5u585S5e5o5c5W5i5o5g5!5t3f0x5l5(4{5*5q381m2(1d2S2F0J2J3b0M1(251l5^1o5?2,4m055}0#2)5D0=0i0`0#0Z3t5s1}0Q2_6g5y3o0Z0`1?0p0d0e0B0U2G0h0H0q2X2m6l6a010_040O6C5J0j0`1c656m6E0`0b3t0L6h320`0h6v2j0s6I5O6F6R4m6T6O6K040F6Y0H6!6N6D6F0f0c3A0L6{6*6D6,2v0~0Y0%0K6S6U0=0H0`0o756O6F0C0R6`6|76016c040h6f6)7i6,6M2*6}5J78040o7a7o6O6z4j6#3b6F6_4t6|7I7t5O7k2v0K0s0S7r2}7K3w0`700s720d747H7h6+0`0q7b6D7v7y7s7p6L7*7u0`0l0l7;5O7B045w467I7i7k7m7_7U7l6/6;7.6O7v02720y834B7(7D3D7F6S7T3D0M0g0`030L1O0L2G6:0L0B0r0K8w2q0t0d197g7J8l3%817n886~0`6.8u877S7i8a8c8e3.8g6=5J8j6)8H3^8n8p8r1P8P8w8y0L0m0L0e8D0M0t0B8F8G7$6D7k0Z3F8V3^6F6H8Y5O6,0h8h3%6%912;8N99926Q9c6V040r9f1}6@9i776j7l7R388$9d046q6s6u6w6y6A9l957E0`942,7%047)9F8i9h7z8M858P9m1S9b9Q6J8N869U0=6@7G4$8{9*9v9j7W7Y7!9J7+0`0v9#3c0`0d0X0X210J9^939I2}7/7la09P8L9Y6-a6046(a8960`9E9;8Z0`0f0f8`9*a40r21ah8R89799p017{5,7~9+6{a49.739^7v9@9N8W049{9}0j9 aJ9g6Ga25;9K9Mai6$a7at9RaWa37caZ9uaparabalan8|5J7k0B0*8_aQ9n0`9(7S9,0=8(048q8s8,8x8z8:0J2j2oa^9)aBa~7j0`8 0Saw939^97abada!a90Fbnaw6,asaU6?akaw0H9r2Xbt6p0d6r6t6Y6x6z2Zbv2B7ibka_9ja$bwajacbD9S6Zbs9Xaf6-9!b!3b7v0IbWbSbNa(046^a/aBaD8x7XaFbQ779?bl9`9|9~ab0OaTb.9R98b{6PbVb(8faacb3%7v0Eb,bZae84bM69bUa.7#b?9Kaq0jcmbe7,aw7{5:3kbdbe6 b^9/aGb}c86,aMc1c8a1b~9Lcjbpb#b-3g8S0`b+ce3^czcRa*csa,cNakamcqbea=a@aba|9ubeb0b28+6Z8-8z210L0u0/b=c.6W8KcS848ObYcZ1}8T0K8ddabRc;8k7ic^8*8tc{b58/8;8?8^d27 6O8~90df9$9HcPc7aX9Gcackccbrc*dFd6cccmbObydy01bA6W9t2BcDbEbG9A0SbJ9Dc2cPcUdOdKc%c6b%dGcfcXcidJbod,bqd.a%bxb:c=cBcCa:b#aE7ZcH04aIdDcccLaOc2c4cnb#dCdLd:04chdQ6,d)b/d@dVa4dIe89aa)eqcsa-c,bccr9RctcvcW7wcy0h0`7}d eBa9e39:d{7=e6cPeaaPetaRc3d(bzd;dQc#d?d=eWa`d+eweCc)e*9Vc+d2800`a?aqdh8#dj8ob1dlb48.b7b90Kbb3~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}d4bWgKgB040P7-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@k45r0l670B2C2%kx5@1w5_2F2H2D1%1)2F0d1NkA0l5^0|kN0$0(0*04.

###(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,:ag)1ikn9/àS=vmsuhb.84;y7e[6+j2o-dt c0(!w]r5_P3plf050J0B0K0d0h0Y0r0L0M0Y0d0r0r0o010K0h0X010406050r0s0q0q0d0S0z040n0H0Y0s0@0H0j050l0~1012140|0X041d1k051n0l1n1p1k0|0J0h0p0,0.0:0=0t0h0e0t0Y1D0t0K0`050%0u0Y0B1y0/0;011C1E1G1E0K1M1O1K0K0u0H0J141L0S1l0K0t0,170r0X0d0j0=0G011Q1A010Z0)0B0j0d0q0B1K1=1@1|1S1 1O22240`0a0L0V0S0H0X0H0r0h1a0j0L0#1:0S0S0B0M2p1d270j1l0l1.2C0K1,1+1-0J290=1G0j212m1K1v1x0-1R2M0h2O0j1(1w1K0X2v1l2A2C2*0}1?2q2U1}2Z0S110Y0`0L0g2z2.0{2-282:1S2=2@2_0G2|1@2~2A2L01330d2^040L0W372B0|3a310=3d3f0L0x3j392.3b3p2_0T3t3l3v3n3c0H2?3e2_0D3A2 2/1z323F343g0A3K3m3N3o3P3H3g0w3T3C3V3E3G3q0k3#303%3x040g0N3,3M2V3(3Q0g2{1e2}3B3-3^3/0g363}383 3@2;3X3f0g3i453k3L3w4a0`0g3s4e3u40493)4j3z4m474h4q3:3J4t4g3D423S4z3U414i3:3!4E3$4G4w0g3+4K4o3O4w0G3=4Q484S3Q0G3|2*4u4B4H0G444$4A3.4)4d4,4F4p4Z4l4;4L4?3Y0G4s4_4R3W4T4y4 4X514Z4D544v4Z4J594(4T4P5d4.4w0W4V5h4M3Q0W4#3~4-5n3Y0W4+5r4=4Y5u4:5x4`5z3f0W4^5C503_5u4~5I555K5F535N5a5u585S5e5o5c5W5i5o5g5!5t3f0x5l5(4{5*5q381m2(1d2S2F0J2J3b0M1(251l5^1o5?2,4m055}0#2)5D0=0i0`0#0Z3t5s1}0Q2_6g5y3o0Z0`1?0p0d0e0B0U2G0h0H0q2X2m6l6a010_040O6C5J0j0`1c656m6E0`0b3t0L6h320`0h6v2j0s6I5O6F6R4m6T6O6K040F6Y0H6!6N6D6F0f0c3A0L6{6*6D6,2v0~0Y0%0K6S6U0=0H0`0o756O6F0C0R6`6|76016c040h6f6)7i6,6M2*6}5J78040o7a7o6O6z4j6#3b6F6_4t6|7I7t5O7k2v0K0s0S7r2}7K3w0`700s720d747H7h6+0`0q7b6D7v7y7s7p6L7*7u0`0l0l7;5O7B045w467I7i7k7m7_7U7l6/6;7.6O7v02720y834B7(7D3D7F6S7T3D0M0g0`030L1O0L2G6:0L0B0r0K8w2q0t0d197g7J8l3%817n886~0`6.8u877S7i8a8c8e3.8g6=5J8j6)8H3^8n8p8r1P8P8w8y0L0m0L0e8D0M0t0B8F8G7$6D7k0Z3F8V3^6F6H8Y5O6,0h8h3%6%912;8N99926Q9c6V040r9f1}6@9i776j7l7R388$9d046q6s6u6w6y6A9l957E0`942,7%047)9F8i9h7z8M858P9m1S9b9Q6J8N869U0=6@7G4$8{9*9v9j7W7Y7!9J7+0`0v9#3c0`0d0X0X210J9^939I2}7/7la09P8L9Y6-a6046(a8960`9E9;8Z0`0f0f8`9*a40r21ah8R89799p017{5,7~9+6{a49.739^7v9@9N8W049{9}0j9 aJ9g6Ga25;9K9Mai6$a7at9RaWa37caZ9uaparabalan8|5J7k0B0*8_aQ9n0`9(7S9,0=8(048q8s8,8x8z8:0J2j2oa^9)aBa~7j0`8 0Saw939^97abada!a90Fbnaw6,asaU6?akaw0H9r2Xbt6p0d6r6t6Y6x6z2Zbv2B7ibka_9ja$bwajacbD9S6Zbs9Xaf6-9!b!3b7v0IbWbSbNa(046^a/aBaD8x7XaFbQ779?bl9`9|9~ab0OaTb.9R98b{6PbVb(8faacb3%7v0Eb,bZae84bM69bUa.7#b?9Kaq0jcmbe7,aw7{5:3kbdbe6 b^9/aGb}c86,aMc1c8a1b~9Lcjbpb#b-3g8S0`b+ce3^czcRa*csa,cNakamcqbea=a@aba|9ubeb0b28+6Z8-8z210L0u0/b=c.6W8KcS848ObYcZ1}8T0K8ddabRc;8k7ic^8*8tc{b58/8;8?8^d27 6O8~90df9$9HcPc7aX9Gcackccbrc*dFd6cccmbObydy01bA6W9t2BcDbEbG9A0SbJ9Dc2cPcUdOdKc%c6b%dGcfcXcidJbod,bqd.a%bxb:c=cBcCa:b#aE7ZcH04aIdDcccLaOc2c4cnb#dCdLd:04chdQ6,d)b/d@dVa4dIe89aa)eqcsa-c,bccr9RctcvcW7wcy0h0`7}d eBa9e39:d{7=e6cPeaaPetaRc3d(bzd;dQc#d?d=eWa`d+eweCc)e*9Vc+d2800`a?aqdh8#dj8ob1dlb48.b7b90Kbb3~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}d4bWgKgB040P7-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@k45r0l670B2C2%kx5@1w5_2F2H2D1%1)2F0d1NkA0l5^0|kN0$0(0*04.