Haven't heard of the problem before, but your idea to use divide and conquer, and the 2^n by 2^n size led me to a simple solution:

N=1:

1. place one tromino in any arbitrary orientation

-> you get a 2^1 by 2^1 board with exactly one free square in a corner

N=k+1:

1. split the board into four quadrants

2. solve the tromino placement problem for N=k

3. use that solution to fill each quadrant, and make sure the empty sqare is in the center of the board for three quadrants, and in the corner of the board for the fourth quadrant

4. place another tromino in the center

-> you get a 2^N by 2^N square filled with trominos excpet for one square in a corner

15,964,432 members