From: David Tran <email55555@...>
Date: 2005-05-23T00:34:38+09:00
Subject: [SOLUTION] Ruby Quiz #33 Tiling Turmoil

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 ...