[SUMMARY] Tiling Turmoil (#33)

The quiz mentioned a mathematical proof (by Solomon Golomb), that could be used
in solving this problem.  Most of the submissions used this technique and most
of them even figured it out without Google's help.  Proof positive that coding
in Ruby increases the IQ.

Let's cover that proof.  The easiest instance of the provided challenge is when
n = 1.  No matter which square is missing from that, exactly one L-tromino fits
in the remaining squares.  Here are all four possibilities:

	X 1    1 X    1 1    1 1
	1 1    1 1    X 1    1 X

Obviously, larger values on n require a little more thinking.  Only a little
though, if we're clever.  When n = 2, we can divide the board into quadrants to
get four 2 x 2 boards:

	_ _ | X _
	_ _ | _ _
	---------
	_ _ | _ _
	_ _ | _ _

We can easily see that one of those is just the trivial case from above.  The
key insight is that the other three quadrants could be made into the same
trivial case, with one well-placed L-tromino in the center:

	_ _ | X _
	_ 1 | _ _
	---------
	_ 1 | 1 _
	_ _ | _ _

Now we have four simple problems to solve, no thought required:

	2 2 | X 3
	2 1 | 3 3
	---------
	6 1 | 1 5
	6 6 | 5 5

What about n = 3 and beyond?  Well, dividing n = 3 into quadrants, with another
well-placed center L-tromino, gives us four n = 2 problems.  We can solved each
of those, as we did above.  Then n = 4 can be divided into four n = 3 problems. 
By now, you should see the pattern.

No matter how big the board gets, we can drop an L-tromino in the middle and
divide it into quadrants.  We can keep reducing those sections into quadrants of
their own, until we get all the way back to a bunch of trivial n = 1 problems.

Here's a link to a nice graphical display of that proof, for those who still
need to see it in action:

	http://www.cut-the-knot.org/Curriculum/Geometry/Tromino.shtml

Jannis Harder's solution produced pretty HTML output similar to what you see at
the above link, but uses a different strategy to obtain the answers.  You might
want to run it a few times, to examine that technique.

The solutions emulating the proof, were all fairly similar in function. 
Differing mainly is code style.  Let's break down one such solution by Dominik
Bathon.  Here's the helper class from Dominik's code:

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

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

The comment tells you what we're looking at here, a two-dimensional Array. The
internal storage format (setup in initialize()) is really just a normal Array,
with some clever indexing that you can see in the []() and []=() methods.

The to_s() method is pretty interesting.  You can see that is just generates
each x and y combination and feeds those to []() to get each square.  A couple
of join()s at the end of the method create first rows and then a final String
from that, separating the squares with spaces and the rows with newlines. 
There's a nice use of blocks here though.  Each square is passed to a block (if
given), so that it may format the square for display.

Now we're ready to examine the solution class:

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

These two methods make up the public face of the solver.  First, initialize()
creates an instance of the Array2D we just examined.  Don't let the bit shifting
throw you, 1 << n is just another way to say the 2**n from the quiz.

The other method, tile_with_empty(), takes an x and y position for the empty
square and kicks-off the process to find a solution.  We can see that it sets
some kind of counter, calls tile_recursive() with the dimensions of the board
and the empty square coordinates, then returns the modified Array2D.  Clearly we
need to see tile_recursive() to make sense of this:

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

This is the heart of Dominik's solution.  The method is a code representation of
the proof I outlined earlier.  It starts by locating the center of the board. 
It can branch two different ways from there.  The first is when the center is 1,
showing that we're dealing with the trivial n = 1 case from the proof.  When
that's the case, the code fills the board with the counter we saw initialized in
the previous method.  That will actually fill four squares instead of the needed
three, but if you glance at the last line of the program you'll see that the
empty square is cleared before we return.

The other case the method deals with (the else clause), is for all bigger values
of n.  Here, the method memorizes its counter, because it will be increased by
the coming recursion.  Then, using the earlier found half-way point, the board
is divided into four equal quadrants.  When created, the corner at the center of
the board is used as the new empty square, which represents our "well placed
center L-tromino" from the quiz.  The code then corrects that auto-generated
empty square for the quadrant that already had one.  Finally, the method
recurses by passing the dimensions of the new quadrant and the empty square for
that quadrant.  After the quadrant is filled by that call, the corners are set
to the counter value memorized earlier.

That method will fill the entire board with numbered L-trominos by the time it
returns.  The application code needed to finish off the solution is minimal:

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

Dominik reads the specified size or defaults, then uses two lines of clever math
to determine what the largest numbered L-tromino is going to be in the result. 
The code memorizes the size of that number, for use in the output block.

Then we get to the solver.  An instance of TrominoTiler is created and
tile_with_empty() is called not for one random square by for all possible empty
squares.  Those results are shown using Array2D's to_s() method.  The passed
block pads small numbers to the maximum width memorized earlier.  That gives us
a complete solution.

Many thanks to all you clever tilers out there.  Golomb would be proud.

Ruby Quiz for next week:  Send in some fresh suggestions.  We're out of topics
and need some new material.  Ruby Quiz will take a one week break to give you
all time to find some and me time to participate in one of the codefests.  Enjoy
the break, but don't forget to send in those ideas!