From: Dominik Bathon <dbatml@...>
Date: 2005-05-23T07:41:40+09:00
Subject: Re: [QUIZ] [Solution] Tiling Turmoil (#33)

Hallo,

here is my solution. I didn't know this problem and I didn't google ;-)
It works recursive:

For n=1 it is easy: just place one tromino, so that the empty square is  
empty.

For bigger n, divide the problem into four n-1 sub problems. For example:

________
________
_____x__
________
________
________
________
________

This can be solved by solving the following problems:

____
____
____
___o

____
____
_x__
____

___o
____
____
____

o___
____
____
____

Putting their solutions together we get:

11112222
11112222
11112x22
111o2222
333oo444
33334444
33334444
33334444

So the last missing tromino can easily be placed.

The program accepts one optional argument (n), it defaults to 3.
It outputs solutions for all possible empty squares.

Dominik


#######################################################

# A simple 2D array, the width and height are immutable once it is created.
# #to_s accepts an optional block that can format the elements.
class Array2D
         attr_reader :w, :h
         def initialize(w, h, defel=nil)
                 @w, @h=w, h
                 @array=Array.new(w*h, defel)
         end
         def [](x, y)
                 @array[(y%h)*w+(x%w)]
         end
         def []=(x, y, v)
                 @array[(y%h)*w+(x%w)]=v
         end

         def to_s
                 (0...h).collect { |y|
                         (0...w).collect { |x|
                                 v=self[x, y]
                                 block_given? ? yield(v) : v
                         }.join " "
                 }.join "\n"
         end
end


class TrominoTiler
         def initialize(n)
                 n=[1, n].max
                 # initialize the working array
                 @a=Array2D.new(1 << n, 1 << n)
         end

         def tile_with_empty(x, y)
                 @tilenum=0 # counter
                 tile_recursive(0, @a.w, 0, @a.h, x, y)
                 @a
         end

         private

         # tiles the area of @a determined by xb,xe and yb,ye (b is begin,  
e is
         # end, so xb,xe is like the range xb...xe) with trominos, leaving
         # empty_x,empty_y empty
         def tile_recursive(xb, xe, yb, ye, empty_x, empty_y)
                 half=(xe-xb)/2
                 if half==1
                         # easy, just one tromino
                         @tilenum+=1
                         # set all 4 squares, empty is fixed below
                         @a[xb  , yb  ]=@tilenum
                         @a[xb+1, yb  ]=@tilenum
                         @a[xb  , yb+1]=@tilenum
                         @a[xb+1, yb+1]=@tilenum
                 else
                         # tile recursive
                         mytile=(@tilenum+=1)
                         # where to split the ranges
                         xh, yh=xb+half, yb+half
                         [ # the 4 sub parts:
                         [xb, xh, yb, yh, xh-1, yh-1],
                         [xh, xe, yb, yh, xh  , yh-1],
                         [xb, xh, yh, ye, xh-1, yh  ],
                         [xh, xe, yh, ye, xh  , yh  ]
                         ].each { |args|
                                 # if empty_x,empty_y is in this part, we  
have
                                 # to adjust the last two arguments
                                 if (args[0]...args[1]).member?(empty_x) &&
                                    (args[2]...args[3]).member?(empty_y)
                                         args[4]=empty_x
                                         args[5]=empty_y
                                 end
                                 tile_recursive(*args)
                                 @a[args[4], args[5]]=mytile
                         }

                 end
                 # fix empty square
                 @a[empty_x, empty_y]=nil
         end
end


if $0 == __FILE__
         n=(ARGV[0] || 3).to_i
         d=1 << n
         maxw=((d*d-1)/3).to_s.size
         tiler=TrominoTiler.new(n)
         # show solutions for all possible empty squares
         d.times { |y|
                 d.times { |x|
                         puts tiler.tile_with_empty(x, y).to_s { |v|
                                 v.to_s.rjust(maxw)
                         }, ""
                 }
         }
end