Here's my solution.  It defines a class called Square to represent the
board.  Most of the work is done in the recursive #do_tile function.

The algorithm works by breaking down a board into four quadrants and
determining which of these quadrants has a non-empty square.  It then
places a tile so that the tile will bracket the edge of the quadrant
with the non-empty square.  It then recursively tiles these quadrants.
 Each of these quadrants will have an empty space because the tile
placed in the last step has one square in each of the three quadrants
that didn't already have a non-empty square.

I didn't google, but I did have this problem in my Discrete Structures
class earlier in the year.  :P

class Square
  def initialize n
    raise "n must be > 0" unless n > 0

    # create a 2**n x 2**n board filled with dashes
    @size = 2 ** n
    @board = Array.new @size do 
      Array.new @size do 
	"-" 
      end 
    end
    
    # a randomly-placed X indicates the hole
    @board[ rand(@size) ][ rand(@size) ] = "X"
    @cur_tile = 1
  end

  def to_s
    @board.collect { |row| row.collect { |item| 
	"%#{Math.log(@size).to_i}s" % [item] }.join " " }.join "\n"
  end
  
  def tile!
    # (0, 0, @size) means the @size x @size square extending to the right and
    # downward from (0, 0)
    do_tile 0, 0, @size
  end

  def do_tile row, col, size
    # base case
    if size < 2
      return
    end

    sub_size = size / 2

    # define each quadrant
    top_left = [row, col, sub_size]
    top_right = [row, col + sub_size, sub_size]
    bottom_left = [row + sub_size, col, sub_size]
    bottom_right = [row + sub_size, col + sub_size, sub_size]

    # one of the quadrants will have a non-empty tile; bracket that quadrant
    # with a tile
    if has_filled_tile? *top_left
      @board[row + sub_size - 1] [col + sub_size]     = @cur_tile
      @board[row + sub_size]     [col + sub_size]     = @cur_tile
      @board[row + sub_size]     [col + sub_size - 1] = @cur_tile
    elsif has_filled_tile? *top_right
      @board[row + sub_size - 1] [col + sub_size - 1] = @cur_tile
      @board[row + sub_size]     [col + sub_size - 1] = @cur_tile
      @board[row + sub_size]     [col + sub_size]     = @cur_tile
    elsif has_filled_tile? *bottom_left
      @board[row + sub_size - 1] [col + sub_size - 1] = @cur_tile
      @board[row + sub_size - 1] [col + sub_size]     = @cur_tile
      @board[row + sub_size]     [col + sub_size]     = @cur_tile
    elsif has_filled_tile? *bottom_right
      @board[row + sub_size - 1] [col + sub_size - 1] = @cur_tile
      @board[row + sub_size]     [col + sub_size - 1] = @cur_tile
      @board[row + sub_size - 1] [col + sub_size]     = @cur_tile
    else
      raise "broken"
    end

    @cur_tile += 1

    # recursively tile the quadrants
    do_tile *top_left
    do_tile *top_right
    do_tile *bottom_left
    do_tile *bottom_right
  end
  private :do_tile
  
  def has_filled_tile? row, col, size
    size.times do |r|
      size.times do |c|
	if @board[row + r] [col + c] != "-"
	  return true
	end
      end
    end
    false
  end
end

s = Square.new 2
s.tile!
puts s.to_s

On 5/20/05, Ruby Quiz <james / grayproductions.net> wrote:
> The three rules of Ruby Quiz:
> 
> 1.  Please do not post any solutions or spoiler discussion for this quiz until
> 48 hours have passed from the time on this message.
> 
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
> 
> http://www.rubyquiz.com/
> 
> 3.  Enjoy!
> 
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
> 
> by Greg Brown
> 
> This weeks quiz is based off of a mathematical proof we were taught in my
> discrete mathematics class a few weeks ago. Though I can already hear some of
> you running for the hills at the mention of the four letter word that is math, I
> can assure you that this is more of a thinking problem than it is number
> crunching. The basic idea is pretty simple.
> 
> You're going to tile L-trominos on a 2**n by 2**n board that is missing a single
> square. What's an L-tromino? It's simply a 2 by 2 square with a corner missing
> that looks like an L.
> 
> For further clarification, this is what they look like:
> 
>         #
>         # #
> 
> Well, I guess it's time to stop being vague and give you the problem definition.
> 
> For any 2**n by 2**n board with a single square missing in a random location,
> you must write a program that will tile L-trominos in such a way that the grid
> is completely filled in.
> 
> Your program should take the value for n as the input, and somehow display the
> board with the trominos properly laid out as the output. It should place the
> missing square at random each time the board is generated. (Otherwise this would
> be too easy!)
> 
> For example, the empty board of n = 2 would be something like this:
> 
>         _ _ _ _
>         _ _ X _
>         _ _ _ _
>         _ _ _ _
> 
> The solution for that might look like:
> 
>         1 1 2 2
>         1 5 X 2
>         3 5 5 4
>         3 3 4 4
> 
> As you can see, all squares are completely filled with the exception of the
> empty square which was randomly placed.
> 
> It may look simple on a 4 by 4 board, but once you get up to a 128 by 128 or
> even 4096 by 4096, it becomes more and more obvious that guess and check is just
> not going to work.
> 
> The level of difficulty of this problem depends entirely on how much you already
> know about it. If you want an easy ride, look for the proof and just implement
> it.
> 
> If you want more of a challenge, avoid Googling the topic and try to find clever
> ways to actually show how your program solves the problem.
> 
> Hope you have fun with this quiz, and if you write a really good one, you can
> help me tile my bathroom floor next week as a prize.  :)
> 
> 



-- 
Bill Atkins