Aller au contenu

Pavage de carré particulier avec trominos

Les deux exercices de cette page peuvent être résolus indépendamment.

Partie 1

Cette partie ne traite pas de récursivité !

Définitions : Tromino, sens d'orientation, pavage

On considère le plan, muni d'un repère orthonormé.

  • Un tromino est un assemblage, côté contre côté, de 3 carrés, en forme de L.
    • Le carré central du tromino est celui qui a deux voisins.
  • Il y a 4 sens d'orientation possibles si on souhaite garder les côtés parallèles aux axes.
    • NO indique que les deux autres carrés sont au Nord et à l'Ouest
    • NE indique que les deux autres carrés sont au Nord et à l'Est
    • SO indique que les deux autres carrés sont au Sud et à l'Ouest
    • SE indique que les deux autres carrés sont au Sud et à l'Est

trominos

On peut alors paver, par exemple, un carré de côté 8, percé à la case ligne 5, colonne 4. On a utilisé 21 trominos.

trominos

Exercice 1

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.

Coder une fonction est_pavage qui renvoie un booléen, True si le pavage est valide, False sinon. La fonction prend en paramètres :

  • n : le côté du carré
  • i_trou : la ligne du trou
  • j_trou : la colonne du trou
  • trominos : une liste de trominos. Un tromino 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.
Exemples du codage de tromino

trominos

  • (7, 7, "NO") désigne le tromino vert en bas à droite
  • (7, 0, "NE") désigne le tromino rouge en bas à gauche
  • (0, 1, "SO") désigne le tromino jaune en haut à gauche
  • (6, 3, "SE") désigne le tromino bleu en bas au milieu
Exemples de pavages, ou de tentative

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
>>> trominos = [(0, 0, "SE")]
>>> est_pavage(n, i_trou, j_trou, trominos)
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
>>> trominos = [(0, 0, "SE"), (2, 1, "NO")]
>>> est_pavage(n, i_trou, j_trou, trominos)
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
>>> trominos = [(0, 1, "SO"), (2, 1, "SO"), (0, 2, "SE"), (2, 3, "NO"), (3, 2, "NE")]
>>> est_pavage(n, i_trou, j_trou, trominos)
False

Un pavage valide.

🐍 Console Python
>>> n = 5
>>> i_trou, j_trou = 4, 0
>>> trominos = [(0, 0, "SE"), (0, 2, "SE"), (1, 4, "NO"), (2, 1, "NE"), (2, 3, "SE"), (3, 0, "NE"), (4, 2, "NO"), (4, 4, "NO")]
>>> est_pavage(n, i_trou, j_trou, trominos)
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 : ∞/∞
.128013/.Tr;nbOylaeu)*d63m?(P+02è-],59fq!78 _o=pcwgv4F1kéhtsSàj[i:E050q0m0!0l0*0k0#0L0Q0k0l0#0#0O010!0*0P010406050#0n0t0t0l0e0j040$0N0k0n100N0g050b17191b1d150P04051t1m1w0b1t150q0*0T0^0`0|0~0Z0*0S0Z0k1K0Z0!13050:0h0k0m1F0{0}011J1L1N1L0!1T1V1R0!0e1u0!0Z1X1H010G0=0m0g0l0t0m010^1g0#0P0l0g0~0z1R22241=1Z1^1V1{1}130a0L0w0e0N0P0N0#0*1j0g0L0.200e0e0m0Q2r1m290g1u0b1:2E1-1/1.1S0q2b0~1N0g1`2o1R1C1E0_1Y2O0*2Q0g0N2U1R0P2x1u2C2E2,16232s2W1?2#0e1a0k130L0W2B2:142/2a2=1Z2@2_2{0z2~24302C2N01350l2`040L0s392D153c330~3f3h0L0U3l3b2:3d3r2{0E3v3n3x3p3e0N2^3g2{0r3C312;1G343H363i0J3M3o3P3q3R3J3i0K3V3E3X3G3I3s0F3%323)3z040W0y3.3O2X3*3S0W2}1n2 3D3/3`3;0W383 3a413_2?3Z3h0W3k473m3N3y4c130W3u4g3w424b3+4l3B4o494j4s3=3L4v4i3F443U4B3W434k3=3$4G3(4I4y0W3-4M4q3Q4y0z3@4S4a4U3S0z3~2,4w4D4J0z464(4C3:4+4f4.4H4r4#4n4?4N4^3!0z4u4{4T3Y4V4A514Z534#4F564x4#4L5b4*4V4R5f4:4y0s4X5j4O3S0s4%404/5p3!0s4-5t4@4!5w4=5z4|5B3h0s4`5E523{5w505K575M5H555P5c5w5a5U5g5q5e5Y5k5q5i5$5v3h0U5n5*4}5,5s485u5:130U5y5?5A583!0U5D5|5F5~5,5J625L3;0U5O675Q695T6c5V5,5X6g5Z5 5#6k5%5 5)6o5+130E5.6s5^040E5=4h5}5R6u5{6C636E6z616H684J0E662D1x2*1m2U2H0q1/2M3F0Q2$1~1u6V1v6T2.4o056#0.2+6I0X130.0G3v5@1Z0R2{6`6D0g0G130m0#0!0M230T0l0S0m6 6I12040v7d68131l6-6D7f0D3v0L6{3q130*0M1-0N0n7i5Q7o7q7s3e130(7w2l7z7m7e137p4o7r70137x0t2Z2o7A3d7f0o0+3C0L7%7Q6I0Q0W13030L0!740!2t000;2x0L0g0Y0Q740#7^1W0/0L170G1^7 0g7:7$7(7E6?040*6_7P7E7U136L3i7E0N130p7D700h132e7X3F7f7h7L7j047T7V0#8w3)7Z8r6I8o040x8J5L8j3=8O5Q8L0I0O8S3y7k8X3F8L8q8h7R047l2.7n137#4v7(8;7)5L8d2x0!0n0e8+2 8?5Q0X0Q130V3g0#7c4v068;7E7+7-0L0i2s0m852y8`1W6#0g0Q0e0A7:1}880L1V0L787a974(9a8)9x7b8!3)8L8W8(7M040)0)8G3`9193959z8~8c130G3H9F437G9Z1?0N6}8e8}3a8 3y8t040e249E8A7B138z8,6I0g8Z9@7Y130o0C9$1Z8d9X0ea47t8ea9019(7u9+2D9-4D9/9;0g9?9{5L8y9O2?9~ao9^04a28a7%7E9}049D9T3a7E7f9N9 4D7u7I7yar1Z7f0CaIau8Y047H7x7KaT8x13a39J5L9Hac9Q040d0e0naE3m9B6=9W9Ya%av9`2 aA7uaO0~7Ca_aU0(a 01b12,ai3:13960g8FaJ8Ha1acae9*acaB8D2#beaZbg048/9A8=az6D9c047.0Q1b0e0Y0^1`1-3gay8=9V8e8gb88n9)2#0!ac8ya{aF6D8Q6wah8n13020k0!0f9IbO8)0*bib$b(0fblata|8-awbi9)240qbT9_b5bYb/04b%b)b+9U8)b4b28#b:b)b?8*b57Z7!bJbvbwa?9:0/8{ag8m6Da+940?a:3ib93`by7.1`2t0m0Z3H0@0Ick8bct7ubNc89|13aDch13aSb^cQabbf3`aQcVbWcXcabqc!a#bt40clbKcMco8`8|a*9204cv967qcz1?cB2t0Y0(0%9w0l0TbEcJ8:clbL0mcwcTbscKbva}aCd69ydfc$6Rb-dfaRb5aBc)cWapa#c3c79,8cc_a-a/c}9b7,bz0L1kd50T0m0cdP3C99dbbxdIcC2s0Z0l1i0DdK0n0LcD0h0{2td%bB2wbE7}889;0k0L0udhc~a5cNcfbcbpdwavdo6;8P0*13bZe4ava$b,8K130OdAb!6D0#2704010$01dfc-9,d{0~d0d)0{d`a=8@d}cbbacYeca(138NeB3`8Q6Bcsedc40Sc6cfcraG8.exdTcn8_cqc^9Rde7Pes01eu2s0.cG0ecIeVcmezbMcfcScZ1?aHdta~eI9%eGaceKdre3djdvc%dx040Ceqa;c/eWe=eYc@e~a5c_c{cxe;5Qd00qd2d478d8e:e(aBe^c*e`cUe|eDcPeF8Mf1e68Re_aPa#f4c9drdze!a,a.fme(d0dL78dOdQdadic;ddc|fKb0eUe%dH9dcDdY1ifvbL8fcfb.fi0~8L0BfH4lc3c5b=f{01c2f*b6f,bufdc:eXcpfheE90fk9SdGdUf/e+cFcH0Ld9gafdf@cOdB9Cdlane1a09LfCf`gg3df}f fJfzfLf9fNc(drfb14gbf$gdc?cre(cugjf-gldJfqd3dMfuf#gtgx79gzf7e2gDc3f~g4f2g7c#fCf6dp9KebfE8TeefRdEfUf.dJfXd6fZ0cdRc/h77.d40SdZ0Q0Z0md#7y0Ld40q2l2q1W0qd-bCd:bGd?d^d`gud~1`e0g:gBgNe5g0g`dyg49HegeM5Lej13010,eohMdgg!7*dVhp2ths89g+hec;f^g4duc3eHgF3Fg_h?9Gb$ePb*eRepfvey9013fggWdCe#f)b8fVh$cDe,gpgrc.gShDh/cRgycxeTgCg7aBgEgAa!gMg|h;gIeLinfai0cLgUeZg4gYe$i9hfd1g(ftgqf?g-dmhYhJ6de}gKf+iuip9#hOf0g^fIiyb_h0gweNhQgXdDfTgkh#9dh9dNdPhch+iCe=f(imb_gQfn3dd0hhhjhliOcnh.h_9!aVg?ixg1b;gIe8ingQdSgSi|i2c=iEjb1?iGi88~iagmcEe-e/i{gTe=jah1aUfyisbriSaUirhHitdsiYjdi!04g@js1Zh^jJc+f9jljni13d8^gei5ctgiiHjwiJg%fsd6g*gsh,cXjIjOjKg=hYjQiV7FjSjWf|13jVjGh@i%fPjTi-i6fSdFh!5LfW2sfYi_hdjoj3h$d70e8f0*bB2r0L0Ha/7/7y7=7;0L2x0t0P1NbJiJ0L0b0I097%0v0G0l0Q0nb(0l100G0Lha0Q9u1W2)0m7U0m0e7/kE0q7@0*2x0okKc;a7f_b{afblak9=i 9KbVg~8BeSb_cjjCgXa@a8ijk4k99G9)2Zk~i3l0dfl3e9aUl69Kl8j_fejpjFi+a(bQ0NbSldj|l4g;jRjNlEgBk1jZaslej}j!iAl9j`ffj+fRfli;kjh$0=0L1a0gkz1WdZl#0N2Z0@0n2Q0^0{cx06jmjxdJ0dkCd(750L0hdL0Im2k^iDgflf9Pi/kh4.0b6/0m2Ek)2E6)2F6X1m2Iml0l1Ume6U1D300b0.0:0=0#04.

Partie 2

Cet exercice traite de la récursivité et peut être réalisé sans avoir réussi le précédent. Cependant, il faut en avoir compris les notations.

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 trominos pour le paver. On utilisera le même codage des trominos que dans l'exercice précédent.

Exercice 2

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

Coder une fonction pavage_trominos 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 trominos qui pavent le carré troué. Chaque tromino 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 tromino, et sens indique son orientation.

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

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é.
  • la fonction dessine qui vous permettra de voir vos pavages 👍 (help(dessine))
Exemples

Ici le pavage est unique.

🐍 Console Python
>>> pavage_trominos(2, 1, 1)
[(0, 0, "SE")]
>>> est_pavage(2, 1, 1, pavage_trominos(2, 1, 1))
True

Ici le pavage n'est pas unique.

🐍 Console Python
>>> pavage_trominos(4, 0, 1)
[(0, 3, "SO"), (1, 0, "NE"), (2, 2, "NO"), (3, 0, "NE"), (3, 3, "NO")]
>>> est_pavage(4, 0, 1, pavage_trominos(4, 0, 1))
True

Ici le pavage n'est pas unique.

🐍 Console Python
>>> est_pavage(8, 5, 4, pavage_trominos(8, 5, 4))
True

Une fois l'exercice résolu (ou pas), vous pourrez dessiner votre pavage (ou tentative).

  • Inutile de fournir les coordonnées du trou à la fonction dessine,
  • uniquement la taille et la liste des trominos.
🐍 Console Python
>>> n = 8
>>> dessine(n, pavage_trominos(n, 5, 4))
###(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 : ∞/∞
.128013x/.r;nbOylaeu)*d63m(Pô+02-],59f!78 N_o=pcwgv4F1kéhtsSàj[i:E050q0m0Z0l0)0k0!0J0P0k0l0!0!0N010Z0)0O010406050!0n0t0t0l0e0j040#0M0k0n0 0M0g050c16181a1c140O04051s1l1v0c1s140q0)0S0@0_0{0}0Y0)0R0Y0k1J0Y0Z12050/0h0k0m1E0`0|011I1K1M1K0Z1S1U1Q0Z0e1t0Z0Y1W1G010F0;0m0g0l0t0m010@1f0!0O0l0g0}0z1Q21231;1Y1@1U1`1|120a0J0v0e0M0O0M0!0)1i0g0J0-1 0e0e0m0P2q1l280g1t0c1/2D1,1.1-1R0q2a0}1M0g1_2n1Q1B1D0^1X2N0)2P0g0M2T1Q0O2w1t2B2D2+15222r2V1=2!0e190k120J0V2A2/132.292;1Y2?2^2`0z2}232 2B2M01340l2_040J0s382C143b320}3e3g0J0T3k3a2/3c3q2`0D3u3m3w3o3d0M2@3f2`0r3B302:1F333G353h0H3L3n3O3p3Q3I3h0I3U3D3W3F3H3r0E3$313(3y040V0y3-3N2W3)3R0V2|1m2~3C3.3_3:0V373~39403^2=3Y3g0V3j463l3M3x4b120V3t4f3v414a3*4k3A4n484i4r3;3K4u4h3E433T4A3V424j3;3#4F3%4H4x0V3,4L4p3P4x0z3?4R494T3R0z3}2+4v4C4I0z454%4B3/4*4e4-4G4q4!4m4=4M4@3Z0z4t4`4S3X4U4z504Y524!4E554w4!4K5a4)4U4Q5e4/4x0s4W5i4N3R0s4$3 4.5o3Z0s4,5s4?4Z5v4;5y4{5A3g0s4_5D513`5v4 5J565L5G545O5b5v595T5f5p5d5X5j5p5h5#5u3g0T5m5)4|5+5r475t5/120T5x5=5z573Z0T5C5{5E5}5+5I615K3:0T5N665P685S6b5U5+5W6f5Y5~5!6j5$5~5(391w2)1l2T2G0q1.2L3E0P2#1}1t6v1u6t2-4n056B0-2*62010W120-0F3u5?1Y0Q2`6U5|3d0F12220S0l0R0m0L1,0M0t2Y2n6Z6O11040u6?67121k6J6!6^0C3u0J6V3p120)6-2k0n6{5P7173753d120%790M7b6 6@120o0*3B0J7t746!0g120e0X160k0/0Z7f6!0M120N7F7o040(0B7s7u7g6Q040)6T4n7v6O7x046~2+7X5K7H040N7J7W7g6:4k7c3c6^7r4u7u7_7%5P0P0V12030@0`2s1V0h0`0m0C0J1j0J0l0J0Z0m2@2Y0X7P7`7{3c7S2w0Z0n0e7#2~8l4C7y7A0n7C0l7E4u067_7g7}7 0J0#6;0g888a2T0)0!1V1U0@0w0Z0X0J220e830n0b8j8u3/120t7K7(7I8,6c6}8/3c7)0c0c8=3E7/045`3l8D7Q6!8G04800v0l6)6+2s0n812v8W6.0n0X880p0p0.9j8X0_0P0m1|0g0Z9a8d2k6:2!0@1_1,3f8%7R777V7$7g7Z789f8`3(7)027C0f9M428*7;3E7?738(3_93808S9f0J0m0!9t1_0J0Y0l1h8%8E6!7S7U9S2=7i7k7m9H7G129P0Z9R7-7w9U7n5K9X7W9Z1=9#0J9%7a9)9+0J0$0J0R9:0P0Y0m9=8kac1Y7S0F3G9`1Y6^6`a88:7T9V3(7ea57Y7iaG3_aI9 aK040!aM1=6^0oaz0}0M6X7T8s39au76046(6*6,6.9x6=aD7=12aC2-a6048+a;9W1272aJ6|7T9}aTaAa~aX7h047j9La|aH7p7@4%atbha(b87z7B7Db4aY120dbob80l0O0O1_0qbsaBa@2~9I77bzb6b0aE0%bF04a aPb1aSbcaN7paW7^bi7tbDaR1_bPbN5P7)7,b#3c0!2604010K0i01as8kbXbl8ybnbQ1=7)brb{3312bubw0gbyb 0}bAbs7Za{a^7LbM8tbXcbbC70bGb)8vbY0gb!ci7L0obTbgat9E040m0=arc601aa7$bjaeag7lai9tal0q2k2pcAcubVcwax0eb7aBc9bEcBaOcfa_bJcZckc#aQcp6rcj04ctc*7(a!2Yb77Za+6+7ka/c,2C7gcWcBcabKcea%bX9K7ad4c^9|bbcl9N120Adba`bK7qb=bib@8x8z8Bcc8-04b~dsaEc2bxbK0ubBc-aQ0)dabH3xaLdH3E7)0xdichdDa9c)d6a_c~6NdRc/c:47bVbWdUbZb7b%b7b+12b.0+b;bUcRa_b^dqbsb}cX04dyc4dAdCc a_dPe1cddOd)dgb78|5;e4dXd52Cbj7Z8QcodkdZ3l9?6O7Scy8QbKbf8tcF7~94af1V9(9*9,2r85dV90b?9@9Fdibad9dKdf04a2a4de9Tdjc(04eta%ev8HcH9beBakamaoaqdmen5KawayeNbR6_d{dFeVee3hbXc%dwa=bLdidVd07pd)c?a$efbXc`a-9w6;f2c.e0dWaEe3fhe e`eg77b3e;b|e8fqc0eUe~a}f0fta)eL7ldkeXemd#e-aEd@b`fweOdvcqb1d}c5fLe=dBe@e704dNfzb8fjf3fyeS9{b9dGf(fufecrel13fGbXeidVbjd*fZd,b-0#b:e,91aQfJ8Ad_bqd{fQd d{fjf_fsf,0}eaf+c;fighdTc+d(eVcsdmcweqcPfO7d12fE3heZexe#cJe(cM0McOg0d$eo12cTcVa?fVe_eKgkf8dUdkf577f7e{a_fac|fddAgagRgYdEfpge017)dhfZd3gPg;dceMg-g/e6gogxeGfGfn04g3drgu8?g6d2c1bvdzeVfUh8aFfZdMg|fSaUdSgSaQe}gih6fXhih5fxfmf?ekgHh1f@fWb(hp3Ef|010#d/hydobmg4cBd`heg8hcfgcgfWg:g-ggg?g-g=g`gdhD3(hXhjb5f%h%eThAgof:06g 8Few9597a,830?6.8P8b1h2w0?0P1abl8b0S2x0J0n2r9(0q230?ib1 c@d;bj9^9Gh-f)h/h#040GhCgl5KhFb/d:h*c7gwgqeI04gLfZd1iAb8e^iJc!ivbIg)hzgUhgf6dig!a.g$hcg(hYiofugb7gg{fZh)htbdh,iOdIfvi$bp04hVi?01i,dQgvc/g~f=d?dpfKi-3_hOiJ7ZhQiMa?hSa_iLj5hki/hmb1hoi}flf1hxikcw9_g@cnf^i)12itd+b,d.izjgh+j0cviEiGg-iIjDa)jfjmhugQi#i:cmf.dXf:f_iUjtiWfc2!jUi~jdaQf#c.hve2hUe90)7:jRjj5P8|5-jOi.dlikbhhKb_hMiJj7jLbthad~hRgOjbjig*jkfWfYhZa7kbj-c+jpcQileJjtiqi`7)jyf{jAf~jCj{e=jFeHgJiFe:jJgNhejNeci~kkkej?kdaEj%e jWi)jYkha*h`c{iXj$g%hej+e5i+j;04j`kKjnjti(a0i^j:j=kbj}knj j2hLh4kzfrdug7k7fRk5c8kIkfhsl0h+kMiPkOiRh:9DiEjskWkrjSeOkug-hFhHkyk.fxkB7`cSkFi`jKlbjMiQe|lEgTgogVa#iVkYfb6/iYkbj)b1k(edk@k,lG6Oj_fDhJk}k1k lufMl3c3l5lCcCjckaks12kgi`h!l6hlkPi;jlj@hql@lneTlTkLjolh8CfH3cae0Uijkncw8o8qgXh1h33L0c6L0m2D2(mo6u1C6w2G2J2E0l1Tmr0c6v14mB0.0:0=04.