Tiling a 2^N by 2^N Grid with L-Shaped Trominoes When students are first taught about the proof technique of mathematical induction, a common example is the problem of tiling a 2N&times;2N grid with L-shaped trominoes, leaving one predetermined grid space empty. (N is some nonnegative integer.)

I will leave it to you to go over the proof if you do not already know it. There are many resources that discuss it.

Your task here is to write a program that takes in a value for N, as well as the coordinates of the grid space to leave empty, and prints an ASCII representation of the resulting tromino tiled grid.

The character O will fill the empty space, and the 4 rotations of our tromino will look like this:

|
+-

 |
-+

-+
 |

+-
|


(Yes, it can be ambiguous which + goes with which - and | for certain arrangements, but that's ok.)

Your program must work for N = 0 (for a 1&times;1 grid) up to at least N = 8 (for a 256&times;256 grid). It will be given x and y values that are the coordinates for the O:


x is the horizontal axis. x = 1 is the left grid edge, x = 2N is the right grid edge.
y is the vertical axis. y = 1 is the top grid edge, y = 2N is the bottom grid edge.


Both x and y are always in the range [1, 2N].

So for a given N, x, and y, your program must print a 2N&times;2N grid, tiled completely with L-shaped trominoes, except for the x, y grid coordinate which will be an O.

Examples

If N = 0, then x and y must both be 1. The output is simply

O


If N = 1, x = 1, and y = 2, the output would be

-+
O|


N = 2, x = 3, y = 2:

+--+
||O|
|+-|
+--+


N = 2, x = 4, y = 1:

+-|O
||+-
|+-|
+--+


N = 3, x = 3, y = 6 (e.g. the image on this page):

+--++--+
|+-||-+|
||+--+||
+-|-+|-+
+--+||-+
||O|-+||
|+-||-+|
+--++--+


Details


You may write a function that takes the 3 integers instead of writing an entire program. It should print or return the grid string.
Take input from stdin, command line, (or function args if you write function).
The output may optionally contain a single training newline.
You are not required to use the tiling method that the proof normally suggests. It only matters that the grid is filled with L-shaped trominoes besides the O. (Trominoes may not be cut or go out of the grid bounds.)


The shortest code in bytes wins. Tiebreaker is earlier post. (Handy byte counter.)
C, 399 bytes

char*T=&quot; |-+ | +-| &quot;,*B;w;f(N,x,y,m,n,F,h,k,i,j){w=B?F=0,w:1&lt;&lt;N|1;char b[N?w*w:6];for(k=w;k--;)b[k*w-1]=10;B=!B?F=1,m=0,n=0,x--,y--,b:B;if(N&gt;1){h=1&lt;&lt;N-1;i=x&gt;--h,j=y&gt;h;while(++k&lt;4)if(k%2-i||k/2-j)f(N-1,!(k%2)*h,!(k/2)*h,m+k%2*(h+1),n+k/2*(h+1));f(1,h&amp;i,h&amp;j,m+h,n+h);h++;f(N-1,x-h*i,y-h*j,m+h*i,n+h*j);}else while(++k&lt;4)B[w*(n+k/2)+m+k%2]=T[5*x+2*y+k];if(F)B[y*w+x]=79,B[w*w-w-1]=0,puts(N?B:&quot;O&quot;),B=0;}

No one's come forward with anything yet, so I'll offer up a meager solution. Mark my words, this is not the end. This will get shorter.
We define a function f that takes 10 arguments, but you need only call it with f(N, X, Y). Output goes to stdout.
Here's a readable version:
char*T=&quot; |-+ | +-| &quot;,*B;
w;
f(N,x,y,m,n,F,h,k,i,j){
    w=B?F=0,w:1&lt;&lt;N|1;
    char b[N?w*w:6];
    for(k=w;k--;)
        b[k*w-1]=10;
    B=!B?F=1,m=0,n=0,x--,y--,b:B;
    if(N&gt;1){
        h=1&lt;&lt;N-1;
        i=x&gt;--h,j=y&gt;h;
        while(++k&lt;4)
            if(k%2-i||k/2-j)
                f(N-1,!(k%2)*h,!(k/2)*h,m+k%2*(h+1),n+k/2*(h+1));
        f(1,h&amp;i,h&amp;j,m+h,n+h);
        h++;
        f(N-1,x-h*i,y-h*j,m+h*i,n+h*j);
    }
    else
        while(++k&lt;4)
            B[w*(n+k/2)+m+k%2]=T[5*x+2*y+k];
    if(F)B[y*w+x]=79,B[w*w-w-1]=0,puts(N?B:&quot;O&quot;),B=0;
}

A taste of output for f(3, 2, 7):
+--++--+
|+-||-+|
||+--+||
+-|-+|-+
+--+||-+
|-+|-+||
|O|||-+|
+--++--+

It's a fairly simple recursive algorithm to fill the grid. I may upload an animation of the algorithm drawing trominoes since I think it's pretty neat. As usual, feel free to ask questions and shout at me if my code breaks!
Try it online!