[SOLUTION] Ruby Quiz #33 Tiling Turmoil

[David_Tran1 (David Tran)]

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

[David_Tran1 (David Tran)]

The solution for 2x2 and 4x4 is unique.
But start from 8x8, the solution is no more unique.

Here is my other version to solve this puzzle.
It uses simple back-tracking to find all possible solution.
It is not efficient at all, but it can find all solutions.

I am not sure is there a math formula to find all solution number.
Base on my program, I found, for example, for 8x8 and
missing cell at (0,0), there are total 30355 possible solutions.

Because it is not efficient, I will not try board big then 8x8

# ------------------------------------------------------------------------------
# Program : Solution for Ruby Quiz Tiling Turmoil (#33)
# Author : David Tran
# Date : 2005-05-23
# Vesion : Use Simple Backtracking to compute all solutions
# Note : Simple backtracking, no use any math theorem or
# pattern analyse. It is not efficient at all!
# BTW. The total solution for 8x8 and missing cell at [0,0] is 30355.
# ------------------------------------------------------------------------------

def help
  puts "Usage: #$0 n [sol]"
  puts " Tiling Turmoil for board of 2^n x 2^n cases with one random
missing case"
  puts " sol: Optional."
  puts " Number solution desire. Default value equals 1."
  puts " Equals to zero : Compute total solution number without
print solutions."
  puts " Less then zero : Print all possible solutions."
  exit
end

# To make sure back tracking all possible solutions, the tiling order
is important.
# This program will tile trimino from top to bottom and left to right.

···

#
# So, the 4 possible L-tromino will have this relation coordination (x, y):
TROMINOS = [ [ [1, 0], [0, 1] ], # o*
                                    # *
                                    #
             [ [1, 0], [1, 1] ], # o*
                                    # *
                                    #
             [ [0, 1], [1, 1] ], # o
                                    # **
                                    #
             [ [0, 1], [-1,1] ] ] # o
                                    # **

def tile_next(a, n, count)
  (0...n).each do |y|
    (0...n).each do |x|
      next if a[y][x]
      TROMINOS.each do |tromino|
        x1 = x + tromino[0][0]
        y1 = y + tromino[0][1]
        x2 = x + tromino[1][0]
        y2 = y + tromino[1][1]
        next if ( x1 < 0 || x1 >= n ||
                  y1 < 0 || y1 >= n ||
                  x2 < 0 || x2 >= n ||
                  y2 < 0 || y2 >= n ||
                  a[y1][x1] || a[y2][x2] )
        a[y][x] = a[y1][x1] = a[y2][x2] = count
        tile_next(a, n, count+1)
        a[y][x] = a[y1][x1] = a[y2][x2] = nil # back tracking
      end
      return
    end
  end
  print_solution(a)
end

def print_solution(a)
  @solutions += 1
  if @show_solution
    puts "solution ##@solutions"
    a.each {|row| puts row.inject('') {|s, e| s + e.to_s.rjust(@digits+1) } }
    puts
  end
  exit if @num_solutions != nil && @solutions >= @num_solutions
end

help if ARGV.size <= 0 || ARGV[0].to_i <= 0
n = 2 ** ARGV[0].to_i
option = ARGV[1] ? ARGV[1].to_i : 1
@num_solutions = (option <= 0) ? nil : option
@show_solution = (option != 0)
@digits = (n*n).to_s.size
@solutions = 0
a = Array.new(n) { Array.new(n) }
a[rand(n)][rand(n)] = 'X'
tile_next(a, n, 1)
puts "Total possible solutions = #@solutions" if @num_solutions.nil?

[David_Tran1 (David Tran)]

=begin

  * Program : Solution for Ruby Quiz #33 Tiling Turmoil
  * Author : David Tran
  * Version : Fast, less iteration version

  Here is my other solution.
  
  Below note is only apply for n >= 3 ( start from 8x8 )
  for n =1 (2x2) and n=2 (4x4) the solution is unique.
  
  It still has a special case need to solve.
  (Do not want google to find solution for the special case)

  The small rectangle form by tromino is 2x3 (or 3x2) note as R(2,3).
  Below, it discuss only for 2x3 case. (for 3x2, just rotate it)
  
  This means all area of 2nx3m can tile by the small rectangle of 2 tromino.

  So, for 2^n x 2^n cases:
  1. If the missing cell is in the central square of 2^(n-1) x 2^(n-1)
     (see graph below, form by 6 + 7 + 10 + 11)
     then the around central square could tile by R(2,3).

     +----+----+----+----+ The big square is 2^n x 2^n

···

* Date : 2005-05-25
     > 1 | 2 | 3 | 4 | Each small square is 2^(n-2) x 2^(n-2)
     > > > > >
     +----+----+----+----+
     > 5 | 6 | 7 | 8 |
     > > x> > >
     +----+----+----+----+
     > 9 | 10 | 11 | 12 |
     > > > > >
     +----+----+----+----+
     > 13 | 14 | 15 | 16 |
     > > > > >
     +----+----+----+----+
      
     The around central can form by 4 rectangles and can be tile by R(2,3).
     * first-rectangle: 1 + 2 + 3
       start point (0, 0), width = 3 x 2^(n-2), height = 2^(n-2)
       As you can see width is divisible by 3 and height is divisible by 2.
     * second-rectangle: 4 + 8 + 12
     * third-rectangle: 14 + 15 + 16
     * fourth-rectangle: 5 + 9 + 13

     And this reduce the problem downto the central 2^(n-1)x2^(n-1) to solve.
     
  2. If the missing cell is in one of the corner 2^(n-2)x2^(n-2) then
     the problem is downto solve that corner; out of the corner could tile
     by R(2,3). For example: if the missing cell is on top-left corner.
     Out of that corner is:
     * first-rectangle : form by 2 + 3 + 4
       width = 3 x 2^(n-2), hieght = 2^(n-2), can be tile by R(3,2)
     * second-rectangle : form by 5+6+7+8+ ... + 16
       width = 2^n, height = 3 x 2^(n-2), can be tile by R(2,3)
     
     +----+----+----+----+
     > 1 | 2 | 3 | 4 |
     > x | | | |
     +----+----+----+----+
     > 5 | 6 | 7 | 8 |
     > > > > >
     +----+----+----+----+
     > 9 | 10 | 11 | 12 |
     > > > > >
     +----+----+----+----+
     > 13 | 14 | 15 | 16 |
     > > > > >
     +----+----+----+----+
     
  3. We already see the missing cell on center (6+7+10+11) case.
     Also the missing cell on corner (1, 4, 13 or 16) case.
     Now, let's see if missing cell on the center border square
     of 2^(n-2)x2^(n-2) ( For example form by half #2 and half #3 )

     +----+----+----+----+
     > 1 | 2! | ! 3| 4 |
     > > !x| ! | |
     +----+----+----+----+
     >__5_| 6 | 7 | 8 |
     > > > > >
     +----+----+----+----+
     >__ _| 10 | 11 | 12 |
     > 9 | | | |
     +----+----+----+----+
     > 13 | 14 | 15 | 16 |
     > > > > >
     +----+----+----+----+

     The problem reduce to solve that 2^(n-2)x2^(n-2) square only.
     Outside of that square, it could tile by R(2,3).
     * first-rectangle : 5 + 6 + 7 + ... + 16 could tile by R(2,3)
       this rectangle already discussed on 2. (see above corner case)
     * second-rectangle : 1 + half of 2
       width = 2^(n-2) + (2^(n-2) / 2) = 3 x 2^(n-3)
       height = 2^(n-2)
       (width is divisible by 3, height is divisible by 2)
     * third-rectangle : half 3 + 4
       could tile by R(2,3) too, same logic as second rectangle.
       
  4. The rest of missing cell possible is "special" case,
     For example the missing cell on half left of 2, or half right of 3,
     or half top of 5, or half bottom of 9 ... etc
     By using paper and pencil, I could solve it easily (for 8x8, 16x16),
     it is try to place a tromino with one case in central square (6+7+10+11),
     and the problem downto solve the central square; and the around the
     center square is tile by R(2,3).
     Unfortunately, I have not yet come out with a generic logic for it.
     For those special case, I will just back to normal solve-by_inductive
     logic for first iteration.

   Note the code is a little mess, maybe define a rotateFloor method
   to help clean up...

=end

class Floor
    
  attr_accessor :width, :height
  
  def initialize(width, height=width, data=nil)
    @width = width
    @height = height
    @data = data ? data : Array.new(width) { Array.new(height) }
  end

  def [](x, y)
    @data[x][y]
  end

  def []=(x, y, value)
    @data[x][y] = value
  end

  # Maximum tiles needs to cover floor without excess floor
  def number_tiles
    width * height / 3
  end
  
  def include?(x, y)
    0 <= x && x < width && 0 <= y && y < height
  end
  
  def tile(missing_x, missing_y, start_tile_number = 1)
    n = @width
    nb = start_tile_number
    if n <= 4
      tile_by_inductive(missing_x, missing_y, start_tile_number)
      return
    end

    squares = {
      ##### central square case #####
      [n/4, n/4, n/2] => [[0, 0, 3*n/4, n/4], [3*n/4, 0, n/4, 3*n/4],
                          [0, n/4, n/4, 3*n/4],[n/4, 3*n/4, 3*n/4, n/4] ],
                          
      ##### corner square case #####
      [0, 0, n/4] => [ [n/4, 0, 3*n/4, n/4], [0, n/4, n, 3*n/4] ],
      [3*n/4, 0, n/4] => [ [0, 0, 3*n/4, n/4], [0, n/4, n, 3*n/4] ],
      [0, 3*n/4, n/4] => [ [0, 0, n, 3*n/4], [n/4, 3*n/4, 3*n/4, n/4] ],
      [3*n/4, 3*n/4, n/4] => [ [0, 0, n, 3*n/4], [0, 3*n/4, 3*n/4, n/4] ],
      
      ##### middle border square case #####
      [3*n/8, 0, n/4] => [[0,0,3*n/8,n/4], [5*n/8,0, 3*n/8,n/4], [0,
n/4, n, 3*n/4]],
      [0, 3*n/8, n/4] => [[0,0,n/4,3*n/8], [0,5*n/8, n/4, 3*n/8],
[n/4, 0, 3*n/4,n]],
      [3*n/8, 3*n/4, n/4]
=>[[0,3*n/4,3*n/8,n/4],[5*n/8,3*n/4,3*n/8,n/4],[0,0,n,3*n/4]],
      [3*n/4, 3*n/8, n/4] =>[[3*n/4,0,
n/4,3*n/8],[3*n/4,5*n/8,n/4,3*n/8],[0,0,3*n/4,n]]
    }

    squares.each do |(from_x, from_y, size), rectangles|
      x = missing_x - from_x
      y = missing_y - from_y
      floor = subFloor(from_x, from_y, size)
      if floor.include?(x, y)
        rectangles.each do |(from_x, from_y, width, height)|
          rectangle_floor = subFloor(from_x, from_y, width, height)
          rectangle_floor.tile_without_missing(nb)
          nb += rectangle_floor.number_tiles
        end
        floor.tile(x, y, nb)
        return
      end
    end

    ##### at this point, the missing cell is on the "special cases" #####
    tile_by_inductive(missing_x, missing_y, start_tile_number)
  end
  
  protected
  
  def tile_by_inductive(missing_x, missing_y, start_tile_number)
    half_width = width / 2
    half_height = height / 2
    shifts = [ [0, 0], [half_width,0],
               [0, half_height], [half_width, half_height] ]
               
    missings = [ [half_width - 1, half_height - 1], [0, half_height - 1],
                 [half_width - 1, 0], [0, 0] ]

    floors = shifts.inject([]) do |floors, (from_x, from_y)|
      floors << subFloor(from_x, from_y, half_width, half_height)
    end
    
    nb = start_tile_number + 1
    shifts.each_with_index do |(from_x, from_y), i|
      x = missing_x - from_x
      y = missing_y - from_y
      if !floors[i].include?(x, y)
        x = missings[i][0]
        y = missings[i][1]
        floors[i][x,y] = start_tile_number
      end
      if width > 2 && height > 2
        floors[i].tile(x, y, nb) # call normal tile (not tile_by_inductive) !
        nb += floors[i].number_tiles
      end
    end
  end

  def tile_without_missing(start_tile_number)
    nb = start_tile_number - 1
    if (width % 2 == 0 && height % 3 == 0)
      (0...width).step(2) do |x|
        (0...height).step(3) do |y|
          self[x,y] = self[x+1,y] = self[x+1,y+1] = (nb += 1)
          self[x,y+1] = self[x,y+2] = self[x+1,y+2] = (nb += 1)
        end
      end
    elsif (width % 3 == 0 && height % 2 == 0)
      (0...width).step(3) do |x|
        (0...height).step(2) do |y|
          self[x,y] = self[x,y+1] = self[x+1,y] = (nb += 1)
          self[x+1,y+1] = self[x+2,y] = self[x+2,y+1] = (nb += 1)
        end
      end
    else
      fail "Without missing cell, this can only tile a " +
           "floor area of 2nx3m or 3nx2m rectangle."
    end
  end
  
  private

  def subFloor(from_x, from_y, width, height=width)
    floor = Floor.new(width, height, @data)
    class << floor
      attr_accessor :from_x, :from_y
      alias :old_get :[]
      alias :old_set :[]=
      
      def [](x, y)
        old_get(@from_x + x, from_y + y)
      end
      
      def []=(x, y, value)
        old_set(@from_x + x, from_y + y, value)
      end
    end
    floor.from_x = from_x + (respond_to?(:from_x) ? self.from_x : 0)
    floor.from_y = from_y + (respond_to?(:from_y) ? self.from_y : 0)
    floor
  end
  
end

(puts "Usage: #$0 n"; exit) if ARGV.size <= 0 || ARGV[0].to_i <= 0
n = 2 ** ARGV[0].to_i
floor = Floor.new(n)
missing_x = rand(n)
missing_y = rand(n)
floor[missing_x, missing_y] = 'X'
floor.tile(missing_x, missing_y)
format = "%#{(n*n/3).to_s.size+1}s"
(0...n).each {|y| (0...n).each {|x| print(format % floor[x,y]) }; puts }

=begin
# Simple unit test
n = 16
(0...n).each do |x|
  (0...n).each do |y|
    floor = Floor.new(n, n)
    floor[x,y] = 0
    floor.tile(x, y)
    a = Array.new(n*n/3+1, 0)
    (0...n).each { |i| (0...n).each { |j| a[floor[i,j]] += 1 } }
    a[0] += 2
    a.each { |e| fail "FAIL: missing at #{x}, #{y}" if e != 3 }
    puts "Missing at #{x}, #{y} => OK"
  end
end
=end