[QUIZ] Tiling Turmoil (#33)

[Ruby Quiz]

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Greg Brown

This weeks quiz is based off of a mathematical proof we were taught in my
discrete mathematics class a few weeks ago. Though I can already hear some of
you running for the hills at the mention of the four letter word that is math, I
can assure you that this is more of a thinking problem than it is number
crunching. The basic idea is pretty simple.

You're going to tile L-trominos on a 2**n by 2**n board that is missing a single
square. What's an L-tromino? It's simply a 2 by 2 square with a corner missing
that looks like an L.

For further clarification, this is what they look like:

#
# #

Well, I guess it's time to stop being vague and give you the problem definition.

For any 2**n by 2**n board with a single square missing in a random location,
you must write a program that will tile L-trominos in such a way that the grid
is completely filled in.

Your program should take the value for n as the input, and somehow display the
board with the trominos properly laid out as the output. It should place the
missing square at random each time the board is generated. (Otherwise this would
be too easy!)

For example, the empty board of n = 2 would be something like this:

_ _ _ _
_ _ X _
_ _ _ _
_ _ _ _

The solution for that might look like:

1 1 2 2
1 5 X 2
3 5 5 4
3 3 4 4

As you can see, all squares are completely filled with the exception of the
empty square which was randomly placed.

It may look simple on a 4 by 4 board, but once you get up to a 128 by 128 or
even 4096 by 4096, it becomes more and more obvious that guess and check is just
not going to work.

The level of difficulty of this problem depends entirely on how much you already
know about it. If you want an easy ride, look for the proof and just implement
it.

If you want more of a challenge, avoid Googling the topic and try to find clever
ways to actually show how your program solves the problem.

Hope you have fun with this quiz, and if you write a really good one, you can
help me tile my bathroom floor next week as a prize.

 

[Kero]

For any 2**n by 2**n board with a single square missing in a random location,

you must write a program that will tile L-trominos in such a way that the grid
is completely filled in.

Your program should take the value for n as the input, and somehow display the
board with the trominos properly laid out as the output. It should place the
missing square at random each time the board is generated. (Otherwise this would
be too easy!) [snip]
The level of difficulty of this problem depends entirely on how much you already
know about it. If you want an easy ride, look for the proof and just implement
it.

Yeah. I knew the problem, I didn't need google.

So I decided to
- generate* all (sub)tiles and
- have only that part of the board in memory that needs to be printed
(quadtree into details for current line, by using the Ruby stack;
If anyone knows how to keep less administration, let me know

Hope you have fun with this quiz, and if you write a really good one, you can
help me tile my bathroom floor next week as a prize.

Not a chance

Besides I fear my code is more cryptic than it could be.

Bye,
Kero.

+--- Kero ------------------------- kero@chello@nl ---+
| all the meaningless and empty words I spoke |
| Promises -- The Cranberries |
+--- M38c --- http://members.chello.nl/k.vangelder ---+


# 1) There is no regular coverage of trominos over a 2**n square board (3 does
# not divide 2**n)
# 2) however, tromino's can cover 3/4 of such a board. the factor three has
# been introduced. Which three quarters? Let me show you:
#
# +---+ Which in itself is a tromino-shaped area, but twice as big.
# | | You can't miss the factor 2 which also appears in 2**n, so
# | +-+ this basically gives the algorithm for the solution away.
# | | |
# +-+ +-+-+ 3) We shall display the board. I'm going to try to use the
# | | | | recursion efficiently and not keep the entire board in
# | +---+ | memory.
# | | |
# +---+---+ 4) Line-by-line we see one or two squares of a tromino that we
# must know. Three squares, four orientations, twelve ids.

# F T L J, clockwise numbered :F1 :F2 :F3 etc
# We would have, from the above shape
# :L => [
# [ :F2, :F3, 0, 0 ],
# [ :F1, :L3, 0, 0 ],
# [ :L3, :L2, :L1, :J1 ],
# [ :L2, :L1, :J3, :J2 ]
# ],
# but that's not recursive, so we get (clockwise):
# :L1 => [:L1, :J1, :J2, :J3],
# :L2 => [:L3, :L2, :L1, :L2],
# :L3 => [:F2, :F3, :L3, :F1],
# We're lazy (and we hate typos) so we'll generate this

class Array
# shift element and append it again, name from CPU registers
def rotate!()
push(shift)
end
# substitute first occurrence of +orig+
def sub(orig, replace)
result = dup
result[index(orig)] = replace
result
end
end

Trominos = [ :J0, :T0, :F0, :L0 ] # rotating J counterclockwise gives T, F, L
Sub = {}

# Set tromino in 2x2 square, clockwise, using :X0 as 'empty'
# With only these set, the script already works for n==1
a = (0..3).to_a # clockwise numbering of :J, 0 being 'empty' (excluded square)
Trominos.each { |sym|
str = (0..3).collect { |i| ":#{sym}#{a}".sub(/0/, "") }.join(", ")
Sub[sym] = eval("[#{str}]")
a.rotate! # rotate counterclockwise
}

# For all 12 possibilities, set subsquare, clockwise
(0..3).each { |i|
counter = Trominos[(i+1) % 4]
sym = Trominos
clockwise = Trominos[(i+3) % 4]
first = eval(":#{sym}".sub(/0/, "1"))
Sub[first] = Sub[counter].sub(counter, first)
second = eval(":#{sym}".sub(/0/, "2"))
Sub[second] = Sub[sym].sub(sym, second)
third = eval(":#{sym}".sub(/0/, "3"))
Sub[third] = Sub[clockwise].sub(clockwise, third)
}

def base(n, x, y)
case [x>>(n-1), y>>(n-1)]
when [0, 0]; Sub[:J0]
when [1, 0]; Sub[:L0]
when [1, 1]; Sub[:F0]
when [0, 1]; Sub[:T0]
end
end

def solve(n, x, y, *fields)
if n == 1
puts fields.join(" ").sub(/.0/, " ")
else
n = n - 1
nn = 2 ** n
x, y = x % nn, y % nn
subs = fields.collect { |f|
# subsquares can be looked up, for :X0 we need proper tromino
Trominos.include?(f) ? base(n, x, y) : Sub[f]
}
solve(n, x, y, *subs.collect { |s0, s1, s2, s3| [s0, s1] }.flatten)
solve(n, x, y, *subs.collect { |s0, s1, s2, s3| [s3, s2] }.flatten)
end
end

if ARGV[0].to_i == 0
STDERR.puts "Usage: #{$0} n # where the field is 2**n square"
else
n = ARGV[0].to_i
size = 2 ** n
x, y = rand(size), rand(size)
puts "Hole at (#{x}, #{y}) # note that (0, 0) is top left"
b = base(n, x, y)
solve(n, x, y, *b.values_at(0, 1))
solve(n, x, y, *b.values_at(3, 2))
end

 

[Dominik Bathon]

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

 

[Matthew Westcott]

Here's my solution (and my first attempt at a Ruby Quiz) - also
completed without googling.

The distinguishing feature here compared to the other solutions posted
so far, is that I'm doing the recursion by creating a tree of Square
objects beforehand, in an effort to make it more OOPish.



#!/usr/bin/ruby

# Proof by induction
# Base case: a 2x2 board with one missing square.
# Trivially, the remaining 3 squares form an L-tromino.
# Step:
# Assume that any (2**(n-1) x 2**(n-1)) board with a square missing
can be solved.
# A (2**n x 2**n) board can be divided into four (2**(n-1) x 2**(n-1))
quadrants.
# One of these quadrants contains the missing square.
# An L-tromino can be placed in the centre of the board, rotated such
that it occupies
# one square of each of the other three quadrants.
# The result of this is four quadrants, each of which has one square
missing.
# By our original assumption, each of these can be solved.

# Note that at each stage of subdivision, each quadrant contains
precisely one
# square that is either 1) the missing square, or 2) occupied by an
L-tromino
# that overlaps onto other quadrants.

class Square
# Represents a square portion of the board.

attr_reader :central_corner_x, :central_corner_y

def initialize(size, left = 0, top = 0, central_corner_x = nil,
central_corner_y = nil)
@size = size # Size of this square
@left = left # X coordinate of leftmost point
@top = top # Y coordinate of topmost point
@central_corner_x = central_corner_x
@central_corner_y = central_corner_y
# Coordinates of the corner closest to the middle
# of the parent square (or nil if the square has no parent)

if size > 1
# divide into quadrants
quad_size = @size / 2
@quadrants = [
Square.new(quad_size, @left, @top, @left + quad_size - 1, @top +
quad_size - 1),
Square.new(quad_size, @left + quad_size, @top, @left + quad_size,
@top + quad_size - 1),
Square.new(quad_size, @left, @top + quad_size, @left + quad_size -
1, @top + quad_size),
Square.new(quad_size, @left + quad_size, @top + quad_size, @left +
quad_size, @top + quad_size)
]
end
end

def contains?(x, y)
# Determine whether this square contains the given point
(@left...(@left+@size)) === x && (@top...(@top+@size)) === y
end

def solve(board, missing_x, missing_y, count = 1)
# board = a board which is to have the portion indicated by this
Square object filled with L-trominos
# missing_x, missing_y - the coordinates of a square not to be filled
# count = the current L-tromino number
# Returns the next available unused L-tromino number
if @size == 1
board[@top][@left] = count unless contains?(missing_x, missing_y)
count
else
next_count = count + 1
@quadrants.each { |quadrant|
if quadrant.contains?(missing_x, missing_y)
# a square in this quadrant is already missing - can solve the
quadrant straight off
next_count = quadrant.solve(board, missing_x, missing_y, next_count)
else
# artificially 'create' a missing square before solving the quadrant
board[quadrant.central_corner_y][quadrant.central_corner_x] = count
next_count = quadrant.solve(board, quadrant.central_corner_x,
quadrant.central_corner_y, next_count)
end
}
next_count
end
end
end

puts "Board magnitude? (1 = 2x2, 2 = 4x4, 3 = 8x8, 4 = 16x16...)"
n = gets.to_i
size = 2**n
digits = (n*2) / 5 + 1 # how many base-32 digits we need to give each
L-tromino its own ID

board = (0...size).collect{ (0...size).collect { 0 } }
Square.new(size).solve(board, rand(size), rand(size))

board.each do |row|
puts row.map{ |i| i.to_s(32).rjust(digits) }.join(' ')
end

 

[Jannis Harder]

--Apple-Mail-5--1016462680
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
delsp=yes;
format=flowed

The algorithm I use is the result of 5 (successful) min trying to
fill an
16x1 square with pencil and paper.

It use the fact that 4 Ls can create a new L with the size doubled:

1 1
1 4
2 4 4 3
2 2 3 3

I use this to create Ls in any n**2 size.

Example of the algorithm:

Board:

. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . X . . . .
. . . . . . .
. . . . . . .


The first step is to apply a 2x2 grid to the board:

.|. .|. .|. .
.|. .|. .|. .
".|.".|.".|.".
.|. .|. .|. .
".|.".|.".|.".
.|. X|. .|. .
".|.".|.".|.".
.|. .|. .|. .

Now if fill the square with the X:

.|. .|. .|. .
.|. .|. .|. .
".|.".|.".|.".
.|. .|. .|. .
".|1"1|.".|.".
.|1 X|. .|. .
".|.".|.".|.".
.|. .|. .|. .

I repeat the steps with an 4x4 and 8x8 grid:
4x4:
. . .|. . . .
. . .|. . . .
. . .|. . . .
. . .|. . . .
2"2 1"1|.". .".
2 5 1 X|. . . .
3 5 5 4|. . . .
3 3 4 4|. . . .
8x8:
7 7 8 8 a a b b
7 9 9 8 a d d b
6 9 i i j j d c
6 6 i l l j c c
2 2 1 1 l k e e
2 5 1 X k k h e
3 5 5 4 g h h f
3 3 4 4 g g f f

My solution does the same thing but instead of applying a grid to the
board it
uses some bit shifting and multiplication. The Ls are created using a
recursive
method.

It generates HTML output (tested with Safari and Firefox)

--
Jannis Harder


--Apple-Mail-5--1016462680
Content-Transfer-Encoding: 7bit
Content-Type: text/x-ruby-script;
x-mac-type=2A2A2A2A;
x-unix-mode=0644;
x-mac-creator=48647261;
name="tiling.rb"
Content-Disposition: attachment;
filename=tiling.rb

class Board
def initialize(size,x,y)
raise unless self.logcheck(size)
@size = size
@x,@y = x,y
clear
end
SUBDIV = [[:bottom_left,2,0],[:top_left,1,1],[:top_left,2,2],[:top_right,0,2]]
TRANSFORM_O = {
:top_left => {
:top_left => :top_left,
:top_right => :top_right,
:bottom_right => :bottom_right,
:bottom_left => :bottom_left
},
:top_right => {
:top_left => :top_right,
:top_right => :bottom_right,
:bottom_right => :bottom_left,
:bottom_left => :top_left
},
:bottom_right => {
:top_left => :bottom_right,
:top_right => :bottom_left,
:bottom_right => :top_left,
:bottom_left => :top_right
},
:bottom_left => {
:top_left => :bottom_left,
:top_right => :top_left,
:bottom_right => :top_right,
:bottom_left => :bottom_right
}
}
TRANSFORM_C = {
:top_left => Proc.new{|x,y|[x,y]},
:top_right => Proc.new{|x,y|[2-y,x]},
:bottom_right => Proc.new{|x,y|[2-x,2-y]},
:bottom_left => Proc.new{|x,y|[y,2-x]}
}

def add_l_tromino(x,y,size,orientation)
if size == 1
case orientation
when :top_left
self[x+1,y ,true] = :top_left_a
self[x ,y+1,true] = :top_left_b
self[x+1,y+1,true] = :top_left_c
when :top_right
self[x ,y ,true] = :top_right_a
self[x ,y+1,true] = :top_right_b
self[x+1,y+1,true] = :top_right_c
when :bottom_left
self[x ,y ,true] = :bottom_left_a
self[x+1,y ,true] = :bottom_left_b
self[x+1,y+1,true] = :bottom_left_c
when :bottom_right
self[x ,y ,true] = :bottom_right_a
self[x+1,y ,true] = :bottom_right_b
self[x ,y+1,true] = :bottom_right_c
else
raise
end
elsif size > 1
ns = size/2
SUBDIV.each do |subl|
no,nx,ny = subl
nx,ny = TRANSFORM_C[orientation][nx,ny]
nx,ny = nx*ns,ny*ns
no = TRANSFORM_O[orientation][no]
self.add_l_tromino(x+nx,y+ny,ns,no)
end
end
nil
end
HTML_HEAD =
'<html>
<head>
<title>Ruby Quiz #33</title>
<style>
tr{padding:0;margin:0;}
td{font-size:2px;width:9px;height:9px;margin:0;padding:0}
.nil{border: 1px solid #777}
.tla{border-top:solid 1px #000;border-right:solid 1px #000;border-left:solid 1px #000;background:#E00}
.tlb{border-top:solid 1px #000;border-bottom:solid 1px #000;border-left:solid 1px #000;background:#E00}
.tlc{border-bottom:solid 1px #000;border-right:solid 1px #000 ;background:#E00}
.tra{border-top:solid 1px #000;border-right:solid 1px #000;border-left:solid 1px #000;background:#090}
.trb{border-bottom:solid 1px #000;border-left:solid 1px #000;background:#090}
.trc{border-top:solid 1px #000;border-right:solid 1px #000;border-bottom:solid 1px #000;background:#090}
.bra{border-top:solid 1px #000;border-left:solid 1px #000;background:#00F}
.brb{border-bottom:solid 1px #000;border-top:solid 1px #000;border-right:solid 1px #000;background:#00F}
.brc{border-left:solid 1px #000;border-right:solid 1px #000;border-bottom:solid 1px #000;background:#00F}
.bla{border-top:solid 1px #000;border-left:solid 1px #000;border-bottom:solid 1px;background:#EC0}
.blb{border-top:solid 1px #000;border-right:solid 1px #000;background:#EC0}
.blc{border-left:solid 1px #000;border-right:solid 1px #000;border-bottom:solid 1px #000;background:#EC0}

.missing{background:#000}
</style>
</head>
<body>
<table cellspacing="0">'
S_ORI = [[:top_left,:bottom_left],[:top_right,:bottom_right]]
def solve(from=1,to=@size>>1)
tx,ty = @x,@y
s = from
tx/=from
ty/=from
raise unless self.logcheck(from) and self.logcheck(to)
while s<=to
dx,dy = tx & 1, ty &1
tx,ty = tx >>1, ty>>1

self.add_l_tromino(tx*(s<<1),ty*(s<<1),s,S_ORI[dx][dy])
s<<=1
end
self
end


def to_html
out = HTML_HEAD.dup
(0..@size-1).each do |y|
out << '<tr>'
(0..@size-1).each do |x|
e = self[x,y]
out << "<td class=\"#{e ? e.to_s.gsub(/([^_])[^_]*_/,'\1') : 'nil'}\">&nbsp;</td>"
end
out << '</tr>'
end
out << '</table></body></html>'
end
def clear
@data =(1..@size).map{[nil]*@size}
self[@x,@y] = :missing
nil
end

def show
File.open("/tmp/tiling.html","w") do |f|
f.puts self.to_html
end
`open /tmp/tiling.html`
end

def [](x,y)
@data[x][y]
end
def []=(x,y,v,q=false)
if q == false
@data[x][y] = v
elsif @data[x][y] == nil
@data[x][y] = q
else
raise
end
end
protected
def logcheck(n)
("%b" % n).tr("0","") == "1"
end
end

if __FILE__ == $0
def logcheck(n)
("%b" % n).tr("0","") == "1"
end
size = nil
until size
STDERR.print "Size?: "
STDERR.flush
e = STDIN.gets
u=Integer(e) rescue nil
size = u if logcheck(u)
end
x = nil
until x
STDERR.print "X?: "
STDERR.flush
e = STDIN.gets
u=Integer(e) rescue nil
x = u if (u)<size and u >= 0
end
y = nil
until y
STDERR.print "Y?: "
STDERR.flush
e = STDIN.gets
u=Integer(e) rescue nil
y = u if (u)<size and u >= 0
end
puts Board.new(size,x,y).solve.to_html
end



--Apple-Mail-5--1016462680
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
format=flowed



--Apple-Mail-5--1016462680--

 

[Jim Freeze]

Here's my solution, and without googling!.

I'm new in Ruby, and I have a little doubt in my solution. The to_s
method is too slow in the way I implemented it, Is there any better
approach?.

Yes. There are a couple of things you can do.

def to_s
cad = ''
@tiles.each_index { |i|
# cad += @tiles + ' ' cad << @tiles << ' '
# cad += "\n" if i%@w==@w-1 cad << "\n" if i%@w==@w-1
}
return cad
end

The other thing you can do (with some extra modification) is start with:

cad = []

and when you are done, do
cad.join("\n")

 

[James Edward Gray II]

Here's my solution, and without googling!.

Nice job.

I'm new in Ruby,
Welcome!

and I have a little doubt in my solution. The to_s method is too
slow in the way I implemented it, Is there any better approach?.
[snip]

def to_s
cad = ''
@tiles.each_index { |i|
cad += @tiles + ' '
cad += "\n" if i%@w==@w-1
}
return cad
end

I haven't tested or timed it, but one way might be:

def to_s
@tiles.join(" ").sub!(/((?:[0-9X]+\s+){#{@w}})/, "\\1\n") + "\n"
end

Hope that helps.

James Edward Gray II

 

[Bill Atkins]

Here's my solution. It defines a class called Square to represent the
board. Most of the work is done in the recursive #do_tile function.

The algorithm works by breaking down a board into four quadrants and
determining which of these quadrants has a non-empty square. It then
places a tile so that the tile will bracket the edge of the quadrant
with the non-empty square. It then recursively tiles these quadrants.
Each of these quadrants will have an empty space because the tile
placed in the last step has one square in each of the three quadrants
that didn't already have a non-empty square.

I didn't google, but I did have this problem in my Discrete Structures
class earlier in the year.

class Square
def initialize n
raise "n must be > 0" unless n > 0

# create a 2**n x 2**n board filled with dashes
@size =3D 2 ** n
@board =3D Array.new @size do=20
Array.new @size do=20
=09"-"=20
end=20
end
=20
# a randomly-placed X indicates the hole
@board[ rand(@size) ][ rand(@size) ] =3D "X"
@cur_tile =3D 1
end

def to_s
@board.collect { |row| row.collect { |item|=20
=09"%#{Math.log(@size).to_i}s" % [item] }.join " " }.join "\n"
end
=20
def tile!
# (0, 0, @size) means the @size x @size square extending to the right a=
nd
# downward from (0, 0)
do_tile 0, 0, @size
end

def do_tile row, col, size
# base case
if size < 2
return
end

sub_size =3D size / 2

# define each quadrant
top_left =3D [row, col, sub_size]
top_right =3D [row, col + sub_size, sub_size]
bottom_left =3D [row + sub_size, col, sub_size]
bottom_right =3D [row + sub_size, col + sub_size, sub_size]

# one of the quadrants will have a non-empty tile; bracket that quadran=
t
# with a tile
if has_filled_tile? *top_left
@board[row + sub_size - 1] [col + sub_size] =3D @cur_tile
@board[row + sub_size] [col + sub_size] =3D @cur_tile
@board[row + sub_size] [col + sub_size - 1] =3D @cur_tile
elsif has_filled_tile? *top_right
@board[row + sub_size - 1] [col + sub_size - 1] =3D @cur_tile
@board[row + sub_size] [col + sub_size - 1] =3D @cur_tile
@board[row + sub_size] [col + sub_size] =3D @cur_tile
elsif has_filled_tile? *bottom_left
@board[row + sub_size - 1] [col + sub_size - 1] =3D @cur_tile
@board[row + sub_size - 1] [col + sub_size] =3D @cur_tile
@board[row + sub_size] [col + sub_size] =3D @cur_tile
elsif has_filled_tile? *bottom_right
@board[row + sub_size - 1] [col + sub_size - 1] =3D @cur_tile
@board[row + sub_size] [col + sub_size - 1] =3D @cur_tile
@board[row + sub_size - 1] [col + sub_size] =3D @cur_tile
else
raise "broken"
end

@cur_tile +=3D 1

# recursively tile the quadrants
do_tile *top_left
do_tile *top_right
do_tile *bottom_left
do_tile *bottom_right
end
private :do_tile
=20
def has_filled_tile? row, col, size
size.times do |r|
size.times do |c|
=09if @board[row + r] [col + c] !=3D "-"
=09 return true
=09end
end
end
false
end
end

s =3D Square.new 2
s.tile!
puts s.to_s

The three rules of Ruby Quiz:
=20
1. Please do not post any solutions or spoiler discussion for this quiz = until
48 hours have passed from the time on this message.
=20
2. Support Ruby Quiz by submitting ideas as often as you can:
=20
http://www.rubyquiz.com/
=20
3. Enjoy!
=20
-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-= =3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D=
-=3D-=3D-=3D
=20
by Greg Brown
=20
This weeks quiz is based off of a mathematical proof we were taught in my
discrete mathematics class a few weeks ago. Though I can already hear som= e of
you running for the hills at the mention of the four letter word that is = math, I
can assure you that this is more of a thinking problem than it is number
crunching. The basic idea is pretty simple.
=20
You're going to tile L-trominos on a 2**n by 2**n board that is missing a= single
square. What's an L-tromino? It's simply a 2 by 2 square with a corner mi= ssing
that looks like an L.
=20
For further clarification, this is what they look like:
=20
#
# #
=20
Well, I guess it's time to stop being vague and give you the problem defi= nition.
=20
For any 2**n by 2**n board with a single square missing in a random locat= ion,
you must write a program that will tile L-trominos in such a way that the= grid
is completely filled in.
=20
Your program should take the value for n as the input, and somehow displa= y the
board with the trominos properly laid out as the output. It should place = the
missing square at random each time the board is generated. (Otherwise thi= s would
be too easy!)
=20
For example, the empty board of n =3D 2 would be something like this:
=20
_ _ _ _
_ _ X _
_ _ _ _
_ _ _ _
=20
The solution for that might look like:
=20
1 1 2 2
1 5 X 2
3 5 5 4
3 3 4 4
=20
As you can see, all squares are completely filled with the exception of t= he
empty square which was randomly placed.
=20
It may look simple on a 4 by 4 board, but once you get up to a 128 by 128= or
even 4096 by 4096, it becomes more and more obvious that guess and check = is just
not going to work.
=20
The level of difficulty of this problem depends entirely on how much you = already
know about it. If you want an easy ride, look for the proof and just impl= ement
it.
=20
If you want more of a challenge, avoid Googling the topic and try to find= clever
ways to actually show how your program solves the problem.
=20
Hope you have fun with this quiz, and if you write a really good one, you= can
help me tile my bathroom floor next week as a prize.
=20
=20

--=20
Bill Atkins