Pavage possible avec triominos (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

Évaluations restantes : 5/5

.128013[(lbsS]et.ph4rd;5-ô!jf1890uma"ov+w7g,_F/3=in 6k:é)y àq2Pc030j0c0d0x0L07090U0Z070x09090K0y0d0L0f0y020N03090v0w0w0x0i0T020a0z070v0?0z0M030I0}0 11130{0f02031j1c1m0I1j0{0j0L0A0+0-0/0;0g0L0E0g071A0g0d0_030%08070c1v0.0:0y1z1B1D1B0d1J1L1H0d0i1k0d0g0+16090f0x0M0;0X0y1N1x0y0q0(0c0M0x0w0c1H1)1+1:1P1?1L1_1{0_040U0Y0i0z0f0z090L190M0U0#1'0i0i0c0Z2g1c1~0M1k0I1$2t1Z1#1!1I0j200;1D0M1^2d1H1s1u0,1O2D0L2F0M0z2J1H0f2m1k2r2t2X0|1*2h2L1;2Q0i10070_0U0r2q2#0`2!1 2%1P2(2*2,0X2/1+2;2r2C0y2_0x2+020U0J2}2s0{302@0;33350U0h392 2#313f2,0l3j3b3l3d320z2)342,0O3q2=2$1w2^3v2`360D3A3c3D3e3F3x360s3J3s3L3u3w3g0t3R2?3T3n020r0u3Y3C2M3U3G0r2.1d2:3r3Z3*3#0r2|3/2~3;3)2'3N350r383`3a3B3m3 0_0r3i433k3=3~3V483p4b3|464f3$3z4i453t3@3I4o3K3?473$3Q4t3S4v4l0r3X4z4d3E4l0X3'4F3}4H3G0X3.2X4j4q4w0X3_4R4p3!4U424X4u4e4O4a4$4A4'3O0X4h4*4G3M4I4n4:4M4=4O4s4^4k4O4y4}4T4I4E514Z4l0J4K554B3G0J4Q3:4Y5b3O0J4W5f4%4N5i4#5l4+5n350J4)5q4;3+5i4/5w4_5y5t4@5B4~5i4|5G525c505K565c545O5h350h595S4,5U5e3{5g5Y0_0h5k5#5m4`3O0h5p5*5r5,5U5v5:5x3#0h5A5^5C5`5F5}5H5U5J615L5-5N655P5-5R695T0_0l5W2~1n2V1c2J2w0j1#2B3t0Z2R1|1k6m1l6k2Z4b036s0#2W5;0y090j0_000W0v0z0d0k6K6M6O6Q6N0k3(316H0_0H1a2o0L1a2i0L1)1a0L1K1M0Q3q4S3T6Y020c090d0G1*0A0x0E0c060M0F0U0L0G1Z0z0v730p762a790U1Z6%0w2O2d0S6W3t6?0U7p0U2m0M0A0z0L1M0v2h080z160R1^7m6=6I367q0j0R0d0c2)2O1M2e0U1L0*7g0z7i2Q0*6|1^0d0U7y0+110i0R2i1M0Z0n0d7+2h0x0T1+7$7'770v740M1s6L0R7F3*6?6T6S6L6U856V4i0N6;3*0P0_0#0q3j0U5$2^0q0_6|6~0c7c7h7j093j8l0;0^02068w5+320_1b6A8D8z0F8j8x8E02757{8C6F8J8L8D0M0_7b8Q8H8S0_0S6/4i7q8k8V0_2m0}070%0d8U6F0z0_0K8=5x8z050b3q8)8M8f8O8i4b8*6F8W028G2X965x8@020K8_958M7i488R8{0_8'4R8)908D922m0d0v0i9a2:9c5~8,6^0v8/0x8;8(7q8M980w8`5C9e9h9b9L8F9O319e0I0I9V3t9k025)3a9s6F920L949S8+8O7c789!3T9e008/8a9.970_9N8!9n029p9A9B310Z0r0_017S1M7{0U6^7$1^0U0g0x188 9r7p910_9,9?3?8X9;0vas1;9^9`ax2^9~9m5C8za32~ao8Da7a9ab7f7dae6_0U0V0U0Eak0Z0g0caman9)5x920q3vaB8y0_8Ba09C8OaE318T9i9/0pa;3ta?9|5_0_8va.a=8$a*0y0z0Caq9zaI9T028p6 8s7W8ua`3T8za-2Z9/9 bm8#028Ka@9}9:8Zbpa1bsa}a/8Y7dbi3*8z8%a!a#anbb8-9F8:bEay0_0ebPaC020x0f0f1^0jbTa+8Abl2:bb0Lb#0ya|9Abba_b1a{0_bzb.9/b0bxaF8$7l9JbJaJbu091^b`b^8?8^b49$6h9(c0c1a~02bM9G9Ib{9WbRb+98bWbY7~b+bkb'6ibncsb?b49Mcxbrcza c4cB0Sb~9qa#ap6@0)aZb;bj9o8ja56ra802aa1LaO78aQ7$aT0j2a2fcOcJcdcLa(0ib4bkcnaqcBb@baa^c@cD02c5cvbqcIc69db78Ob92scT3!8o0x6}be7V7X2dcBcu2sbbbob(8Icybtcf8PbDcPbFdobA3maubwd29P0_0mc|dlc a1bHb cd9K9/chbOdtbQ02bSdPbUcpbZdhdi6Edqc{dpbBb49e0BdEd#dw4qa cGd13{dKd8atc}cFd$cl9fc90L9ldJbJbL9Ecib+9edSckd-bVbXdWdTb$06dYdkd+dAdx02dFd78M9edDd`9#d~3$eic_c2d_e8cQ02cHbIcL0ccNcBaHd7d?1;aLcWaNadafae7z0.bIa$5C9+9-eje9bC9=er9@6JaAe%d@emdZb|a2cS8MeMcXacaPeQaTaV0vaXc*3:d=c-a)e*1;c;ed8Nb*f6b-ewcfb:ezducCf3bUc~djdneBd'd42Oc|bd8rdebhf9a,c=eleven9/dre$d,e'02eqfEe+fz36b/avcGeI0`d=eVekdN9He5cmf6coebcrfvb%fxf8fIdQd)fh3eaDf$c^fAbufddmbqf:fLb_d/eUcKb_eyeZfF9Rg13*9$9'fQdKe28.dOfedQe7f@cfdVf#gd1Pctfxe,eK1Pepd}d gkb$f_gpf-fyf/c|c30Mfje-b2eBd:ccbK9t0_eFc3eHe:aKcVe?cZ7|e_2ic(7Mf}gK9*0_c.c:fwfYc?gAf,8Nf?dGe.gwbbgE8MbGfnb8fqdb8qbfdfg@flegcwg,f)bUfCawg-grg-cAh5g42'dydsh60;hbhj8Ne,g^8$fP0NfRdLbufUcjggdBdRfxgib!f$eff'd'0_f+hmhdgub,dvhfbUg/f;9dhId*hefba/h1d0gIg8c,f gDhHd|g-9$5/gJc0gabNfVf6e6hBf!hDhMgmg*gzhmhlhP0;9$5!fkf^hVh dCgseuhWhShYg0g:gGeC8bfS3teXgBifidd{0og3hX31cagPe0hua%g%f2hmf5hM98f(hygGg=c`icf`c2cGg`d5g|dcfs0i8t7YdhgnfKgxhnh)fHi10yi3iZehhai9h+eti4gFb=eBhrf0dMe3gciH3th@h}hCdXhGiLi!98hRi;eAiJiNf$iic+i!imhccEh(i,02iriai:hpe/ixceeWiAc/g-iDi|d9a:j3b/i*f{jbiPfpjgbcg}ddiUbgiWhEiYjAh4i8fGjmjC6Fivjbi@g9i_gbh=hMi~iE0_j0hEh3buiGigi=j9fch)hJi'hLjxffj=hYf|dJcLarjHgCgEi!9ejli.0_g7jojZg#iz02g'jvg)j)jzh{hOite!jVcfhZdHjFd6iMcffrg fukm8AjPkBj}iuetcbj7j|i7i'i0ko3Ti)jYg!9rh:e4h?fXkkj+kBhFh}j/ipi}hUjHhoflkFkpjQjakBjce iyjs93injijSk8hmh,iwjdik3Ta'iBi'jwj:jyk%kJf4knk'jyj6jok-jykse.h#k6fokvj4daiSkzjNk!kDj{lcfgk~kHkq5CjXk;kdh/j#h;hxl83*j(lxdUh_j1k$j@kLlLlylid@j6k6k)hKf.kEgBj jdcL9v9xlpkUi{5#0I6C0c2t2Ul@6l1t6n2w2z2u0x6-2t6m0{0I0#0%0(0902.

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