Exercice 13 - Pavage avec des L

Soit $n$ un nombre positif fixé. On considère une grille carrée de $2^n \times 2^n$ cases. Un case arbitraire est noircie, toutes les autres sont libres. Le problème consiste à paver toute la grille sauf la case noircie avec des pièces en forme de L. Ces pièces occupent trois cases :

1. résolvez le problème pour $n = 0$.
2. résolvez le problème pour tout $n \geq 0$, vous montrerez que si l'on est capable de résoudre ce problème pour une valeur $n$ donnée, alors il est possible de le résoudre pour une valeur $n+1$.
3. programmez cet algorithme en C, remplissez chaque case avec un caractère. Vous représenterez une pièce en affectant le même caractère à toutes les cases occupées par cette pièce. Par exemple (avec $n=4$),

   @ @ ? ? ; ; : : + + * * & & % %
   @ > > ? ; 9 9 : + ) ) * & $ $ %
   A > B B < < 9 = , ) - - ' ' $ (
   A A B 8 8 < = = , , - # # ' ( (
   E E D 8 J J I I 0 0 / # 5 5 4 4
   E C D D J H H I 0 . / / ! 5 3 4
   F C C G K H L L 1 . . 2 6 3 3 7
   F F G G K K L " 1 1 2 2 6 6 7 7
   U U T T P P O " " j i i e e d d
   U S S T P N O O j j h i e c c d
   V S W W Q N N R k h h l f f c g
   V V W M Q Q R R k k l l b f g g
   Z Z Y M M _ ^ ^ o o n b b t s s
   Z X Y Y _ _ ] ^ o m n n t t r s
   [ X X \ ` ] ] a p m m q u r r v
   [ [ \ \ ` ` a a p p q q u u v v
   

   Vous remarquez que la case noircie est celle avec le point d'exclamation. Représentez la matrice en mémoire de sorte à faciliter l'implémentation récursive de l'algorithme. C'est à dire en indicant de la façon suivante (si $n=3$);

    0  1  4  5 16 18 20 21 
    2  3  6  7 17 19 22 23
    8  9 12 13 24 25 28 29
   10 11 14 15 26 27 30 31
   32 33 36 37 48 49 52 53
   34 35 38 39 50 51 54 55
   40 41 44 45 56 57 60 61
   42 43 46 47 58 59 62 63