```Here is my solution, it is kind of short ...

#--------------------------------------------------------------------
# Program : Solution for Ruby Quiz #33 Tiling Turmoil
# Author  : David Tran
# Date    : 2005-05-20
# Version : 1.0
#--------------------------------------------------------------------
def tile(a, n, m, s, x)
@count += 1
h = m/2
new_s = [s, s+h, s+h*n, s+h*n+h]
new_x = [s+(h-1)*n+(h-1), s+(h-1)*n+h,  s+h*n+h-1, s+h*n+h]
p = ((x-s) / n < h) ? ((x-s) % n < h) ? 0 : 1 \
: ((x-s) % n < h) ? 2 : 3
new_x.each_index{ |i| a[new_x[i]] = @count if i != p }
return if h == 1
new_x[p] = x
new_s.each_with_index { |e, i| tile(a, n, h, e, new_x[i]) }
end

(puts "Usage: #\$0 n"; exit) if (ARGV.size != 1 || ARGV[0].to_i <= 0)
n = 2 ** ARGV[0].to_i
@count = 0
a = Array.new(n*n)
x = rand(a.size)
a[x] = 'X'
tile(a, n, n, 0, x)
format = "%#{2 + Math.log10(a.size).to_i}s"
a.each_with_index {|e, i| print(format % e); puts if (i+1)%(n) == 0}
# End of Program------------------------------------------------------

=======================================================================
It is base on S. Golomb gave an inductive proof :
http://www.cut-the-knot.com/Curriculum/Geometry/Tromino.shtml
Here is some explanation for my program about tile method:
a - is a dimension one array of n x n ( flat of orign dimension 2 array)
n - is the number side ( 2 ** input number )
m - is the number side of sub square
s - is the start point index ( top-left corner index for sub square )
x - is the missing cell index
=======================================================================

Base on The four color theorem, we could color the tile by using max 4 colors.
http://www.math.gatech.edu/~thomas/FC/fourcolor.html

So, I modified again my solution to show by using 4 color codes:
http://mathworld.wolfram.com/Four-ColorTheorem.html

#--------------------------------------------------------------------
# Program : Solution for Ruby Quiz #33 Tiling Turmoil
# Author  : David Tran
# Date    : 2005-05-20
# Version : Using 4 color codes
#--------------------------------------------------------------------
def tile(a, n, m, s, x)
h = m/2
new_s = [s, s+h, s+h*n, s+h*n+h]
new_x = [s+(h-1)*n+(h-1), s+(h-1)*n+h,  s+h*n+h-1, s+h*n+h]
around_tile = [new_x[0]%n == 0      ? nil : new_x[0]-1,
new_x[0] < n         ? nil : new_x[0]-n,
new_x[1] < n         ? nil : new_x[1]-n,
(new_x[1]+1)%n == 0  ? nil : new_x[1]+1,
new_x[2]%n == 0      ? nil : new_x[2]-1,
new_x[2]/n + 1 >= n  ? nil : new_x[2]+n,
new_x[3]/n + 1 >= n  ? nil : new_x[3]+n,
(new_x[3]+1)% n == 0 ? nil : new_x[3]+1]

p = ((x-s)/ n < h) ? ((x-s)% n < h) ? 0 : 1 \
: ((x-s)% n < h) ? 2 : 3

around_tile[p*2, 2] = new_x[p]
(1..4).each do |color|
use = false
around_tile.each do |i|
next if i.nil?
(use = true; break) if a[i] == color
end
if (!use)
new_x.each_index{ |i| a[new_x[i]] = color if i != p }
break;
end
end

return if h == 1
new_x[p] = x
new_s.each_with_index { |e, i| tile(a, n, h, e, new_x[i]) }
end

(puts "Usage: #\$0 n"; exit) if (ARGV.size != 1 || ARGV[0].to_i <= 0)
n = 2 ** ARGV[0].to_i
a = Array.new(n*n)
x = rand(a.size)
a[x] = 0
tile(a, n, n, 0, x)
colorCode = [' ', '*', 'o', '+', '-']
a.each_with_index { |e, i| print(" #{colorCode[e]}"); puts if (i+1)%n == 0 }
# End of Program------------------------------------------------------
=======================================================================

This gives a solution presents like:

\$> tiling2.rb 4

o o + + o o + + o o + + o o + +
o * * + o * * + o * * + o * * +
+ * o o + + * o + * o o + + * o
+ + o * * + o o + + o * * + o o
o o + * o o + + o o + + * o + +
o * + + o * * + o * * + o o * +
+ * * o + * o o + + * o + * * o
+ + o o + + o * * + o o + + o o
o o + + o o + * o o + + o o + +
o * * + o * + + o * * + o * * +
+ * o o + * * o + * o o + + * o
+ + o * + + o o + +   o * + o o
o o + * * o + + o o + * * o + +
o * + + o o * + o * + + o o * +
+ * * o + * * o + * * o + * * o
+ + o o + + o o + + o o + + o o

=======================================================================

My first and second solution always recalculation next "missing" cell
possition, it is kind of waste time, because, except the "missing" cell
all will be one of top-left, top-right, bottom-left, bottom-right
coner "missing"
on next iteration and so on.

So, one ugly and quickly improve is like:

#--------------------------------------------------------------------
# Program : Solution for Ruby Quiz #33 Tiling Turmoil
# Author  : David Tran
# Date    : 2005-05-20
# Version : Without always recalculate "missing" cell
#--------------------------------------------------------------------

DIRECTION = [ [ 0,  3,  0,  1],
[ 2,  1,  0,  1],
[ 2,  3,  2,  1],
[ 2,  3,  0,  3] ]

def tile(a, n, m, s, x, p)
@count += 1
h = m/2
new_s = [s, s+h, s+h*n+h, s+h*n]
new_x = [s+(h-1)*n+(h-1), s+(h-1)*n+h,  s+h*n+h, s+h*n+h-1]

if p < 0
pp = ((x-s) / n < h) ? ((x-s) % n < h) ? 0 : 1 \
: ((x-s) % n < h) ? 3 : 2
else
pp = p
end

new_x.each_index{ |i| a[new_x[i]] = @count if i != pp }
return if h == 1
dir = DIRECTION[pp]
if p < 0
dir = dir.dup
dir[pp] = -1
end
new_s.each_with_index { |e, i| tile(a, n, h, e, x, dir[i]) }
end

(puts "Usage: #\$0 n"; exit) if (ARGV.size != 1 || ARGV[0].to_i <= 0)
n = 2 ** ARGV[0].to_i
a = Array.new(n*n)
x = rand(a.size)
a[x] = 'X'
@count = 0
tile(a, n, n, 0, x, -1)
format = "%#{2 + Math.log10(a.size).to_i}s"
a.each_with_index {|e, i| print(format % e); puts if (i+1)%(n) == 0}

# End of Program------------------------------------------------------

=======================================================================

Anyway, I still like my first short solution even it seems waste time to
recalculate "missing" cell ...

```