Hexominoes and Cube Nets

I have always been fascinated by polyominoes — geometrical shapes made by connecting unit squares edge to edge. (There’s a lot about polyominoes online, so take a few moments to familiarize yourself with them if they’re new to you.)

Today I’ll talk about hexominoes (using six unit squares), since I use them in the design of my current website.  There are a total of 35 hexominoes — but I didn’t want all of them on my home page, since that seemed too cluttered. But there are just 11 hexominoes which can be folded into a cube — I did want my choice to have some geometrical significance! These are called nets for a cube, and formed a reasonable subset of the hexominoes to work with. Note that the count of 11 nets means that rotating or turning over a net counts as the same one. (And if you want an additional puzzle — show that aside from rotating or reflecting, there are just 11 nets for a cube.)

Now how should I arrange them? I also wanted to use the hexominoes for a background for other pages, so I thought that if I made a 6 by 11 rectangle with them, that would be ideal — I could just tile the background with rectangles.

This is not possible, however — I wrote a computer program to check (more later). But if you imagine shifting a row of the 6 by 11 rectangle one or two squares, or perhaps a column — you would still occupy 66 square units, and the resulting figure would still tile the plane. This would still be true if you made multiple row/column shifts.

So I wrote a program which did exactly that — made random row and column shifts of a 6 by 11 rectangle, and then checked if the 11 hexominoes tiled that figure. After several hours of running, I found one — the one you see on my home page. If you look carefully, you can see the row and column shifts for yourself.

Is this the only possibility? I’m not sure, but it’s the only one I found — and I liked the arrangement enough to use it on my website. If you look at some of the other pages — like one of my course websites — you’ll see a smaller version of this image tiling the background. However, to repeat the pattern in the background, I needed to make a “rectangular” version of the image:

The colors are muted since I didn’t want the background to stand out too much.  And you’ll notice that some of the hexominoes leave one edge of the rectangle and “wrap around” the opposite edge.  But if you look closely, you can definitely find all 11 hexominoes in this 6 by 11 rectangle.

This wasn’t my first adventure with hexominoes — a few years ago, I created a flag of Thailand since I was doing some workshops there. Flags are generally rectangular in shape.

But you can’t create a rectangle with the 35 hexominoes! Let’s see why not. Imagine a rectangle on a checkerboard or chessboard. When you place a hexomino, it will cover some black squares and some white squares.

Now some hexominoes will always cover an odd number of black and white squares — let’s call those odd hexominoes. The others — even hexominoes — cover an even number of black and white squares. As it turns out, there are 24 odd hexominoes and 11 even hexominoes. This means that any placement of all the hexominoes on a checkerboard will cover an even number of white squares and an even number of black squares.

However, any rectangle of 210 = 6 x 35 hexominoes must cover 105 white squares and 105 black squares — both odd numbers of squares. But we just saw that’s not possible — an even number of each must be covered. So no rectangles. This is an example of a parity argument, by the way, and is a standard tool when proving results about covering figures with polyominoes.

To overcome this difficulty, I threw in 6 additional unit squares so I could make a 12 x 18 rectangle — and to my surprise, I found out that the flag of Thailand has dimensions 2:3 as well. You can read more about this by clicking on “the flag of thailand” on the page referenced above — and see that the tiling problem can be solved with a little wiggle room. But no computer here — I cut out a set of paper hexominoes and designed the flag of Thailand by hand….

 

Writing code to solve polyomino problems is not a simple task — and I won’t go into great detail here. But I would like to talk about the structure of such a program.

Before you even begin programming, you’ve got to think about how to represent the various polyominoes. Maybe you create a list of points, each one being the lower left-hand corner of a unit square. Or maybe you use the centers of the squares.

But now you’ve got to think about the fact that you can rotate and turn over polyominoes — and how will you do that? You can use matrices, naturally — in the most general case, a non-symmetric polyomino will have eight possible orientations in the plane. Four rotations will be possible, and each of these may be combined with a flip.

A colleague (thanks, Juris!) pointed me to work by Jaime Rangel-Mondragon.  Here, he uses complex numbers to represent squares. Why might this be easier?

It turns out that the operations of rotation and reflection are easy to perform using complex numbers. All that is needed is the usual multiplication of complex numbers, as well as the conjugate. Remember that if is a complex number, then we define the conjugate of to be

If we can represent all eight rotations and reflections of as shown in the diagram below.

Now it’s easy to apply this to a polyomino. If you want to rotate it counterclockwise by 90 degrees, just multiply each of the complex numbers representing it by Or for each representing the polyomino, replace with to get the reflection across the -axis.

I find this to be a particularly fascinating use of complex numbers — it’s one of those ideas which is so elegant you wish you would have thought of it yourself. This element of “surprise” in mathematics — a connection between two ideas you thought might have no relationship to each other — never ceases to amaze me, and is one of the reasons I so enjoy being a mathematician.