Tetris and dominoes

Have you ever experienced deja vu? I just discovered that it’s most likely not deja vu, but rather a sort of precognition. Still, it’s a pretty strange sensation, and when they call it precognition you fell all Minority Report like. Let’s just be happy they don’t put us in a pool of water and hook us up to some supercomputer.

Twice I’ve got this sudden urge to know everything about tiling problems. The first time I didn’t know the proper terminology so I never really got started. I was driven by this puzzle game, IQ-Block, and somehow I just had to know how many solutions it had and if there was some established theory on the subject. On my second attempt I inevitably stumbled upon Colin Ramsay’s paper: The IQ-Block: an interesting polyomino puzzle. From there on I devoured about 20 more papers on polyominoes and related topics before my brain was forced to do a context switch1 (why on earth do we have to sleep all the time?), and I forgot all about it.

Actually, I believe it was my conscience that somehow convinced me that polyominoes weren’t “decent” enough. While I was sleeping my sneaking backstabbing conscience was crawling around my brain, replacing all references to polyominoes with pointers to exams and other school related material. At that time my next exam was more than five days away so I had plenty of time to practice anyway. No reason to get all medieval on my brain cells like that.

A polyomino is basically a collection of one (monomino) or more squares connected to form a geometric figure. Just like dominoes consist of two squares and blocks in Tetris (created by Alexey Pajitnov and named after tetraminoes and tennis) have four squares. A polyomino is naturally a figure with several interconnected squares and tiling (sometimes called tessellation in mathematics) is basically the act of combining several polyomiones with each other. When those polyominoes are of different shapes and sizes things become very interesting, both from the view of mathematicians and computer scientists.

One common tiling problem is to combine a given set of different polyominoes into a rectangle, or possibly even a square (or any other geometric shape for that matter) of a certain size. You know the total area of the square because you know the total number of squares each polyomino has, but you still have to put them together in the right way.

There is also a similar problem where you have to find the least amount of copies of a given polyomino that is required to tile a rectangle covering the least amount of space. This number is usually referred to as the polyomino’s (rectangular) order. Each polyomino might also have different properties that can be exploited in order to find solutions more efficiently. Then you have the problem of enumerating all the different of polyominoes of a given size, which is not trivial when you get to a certain size. Many of these problems are yet to be solved and this is what makes it interesting.

About one week ago I was checking out my wish list on Amazon and saw Polyominoes: Puzzles, Patterns, Problems and Packings by Solomon W. Golomb. Golomb is known as the inventor of polyominoes and so this book is the definitive guide. Needless to say, I simply had to buy it.

A few days later my lecturer in discrete mathematics mentioned that Douglas Rogers (a mathematician within the field of combinatorics) would be coming over (Norwegian page) for a talk and the topic would be Catalan numbers and tiling. Of all the possible places and things in the world, he was coming here and he was going to talk about tiling. It was like all the pieces in my own little puzzle were falling into place. The sequence of events that was unfolding was like a sign from a higher power. A power of a sufficiently large integer to say the least.

Douglas Rogers visited the Institute of Mathematics and Science here at the University of Stavanger (UiS) today (2007-01-23). I was the only student attending so I guess that leaves more knowledge for me and more problems I can solve without interference. Less people, more for me. That’s my basic trail of thought. More people dropping out of school, more work for me, and so on.

Rogers gave a talk about the sequence of Catalan numbers and how they relate to jigsaws, computer science and models for biological growth. He talked about different approaches to enumerate all n-ominoes for a given integer n and binary coding of polyominoes and rooted tree structures. At the end we finished up with a Douglas Adams joke involving the Catalan number 42 for which a certain type of problem was still unresolved.

Douglas Rogers referred to the following sources for further reading:

To summarize it basically went something like this: Deja vu, tiling, Coling Ramsay, IQ-Block, Solomon W. Golomb, polyominoes, Douglas Rogers, Douglas Adams, 42.

Now, where did I leave my copy of The Hitchhiker’s Guide to the Galaxy…

Notes on the bottom of my foot

1 Both No Silver Bullet (see section on time-sharing) by Frederick P. Brooks and Human Task Switches Considered Harmful by Joel Spolsky support the claim that context/task switching affects certain creative processes negatively.

NOTE: This post has been imported from my old it’s learning ePortfolio blog.

And so it begins

I, Myself & Irene. That just so happens to be a memorable movie, and a good start for this blog. At least now nobody can claim that I never mentioned a halfway comprehensible topic. For those who still aren’t satisfied, here you have another one: Peter Pan. Yes, now you know what I’m going on about here.

Really? I’m not making any sense you say? Well, what can you expect from this first post. I’m just setting the bar here so that I can raise it at a later time when I feel like it. Begone!

In case you didn’t leave I might as well comment on this whole ePortfolio service that those it’s learning people added in version 3.1. First of all it’s interesting and second, I can’t figure out how to edit the tagline for the site. It simply states “My ePortfolio” for the time being. I would much rather like to put something like “Incomprehensible and proud of it” or “Binary ate my dog”. Either way I’m probably better off not being able to change it. That way I can fill in all those crazy ideas here where nobody will ever read them.

There was supposed to be a criticism of Steve Gillmor’s blog here (notice how I intentionally left out the link), but I was afraid he might be offended by that. In short I don’t really understand what he is writing, and why he refuses to use links in his blogs. Well, I do recognize the words and all. At least most of the time, but still I can’t seem to be able to wrap my mind around what he’s really saying, or writing, or something. When another person (Joel Spolsky might not be just-some-other-person, but still) has to use three hours to translate his work from no-one-writes-like-that-around-here-anymore to sane English, then you know your time can be better spent on more important other matters.

Tune in for more comprehensible and sane posts in the future. If you’ve read this far you’ve passed the test. The test with a small ‘t’. Not that a small ‘t’ makes it any less significant that a big ‘T’. It just is, for all practical purposes.

It is.

At least so it was.

NOTE: This post has been imported from my old it’s learning ePortfolio blog.