Dominik Bathon
5/22/2005 10:42:00 PM
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