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

Quiz Summary

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:

Golomb's inductive proof

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:

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:

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:

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:

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!

1. Kero
2. David Tran
3. Dominik Bathon
4. Matthew Westcott
5. David Tran (2)
6. Jannis Harder
7. Pedro
8. Bill Atkins
9. David Tran (3)
10. atgeirr

Download Solutions

Back to Quiz Listing