Tiling tilted tori

November 15th, 2016 by munizao

A friend of mine recently complained about not being able to tile anything nice with the full set of polyominoes of size 1 though 5. (No, I didn’t make that up! I have weird friends. Who are not made up.) The area of these pieces is 89, which is prime. So our usual tactic of making a rectangle using divisors of the area won’t work.

But there is in fact something highly symmetrical that these pieces can tile. And its existence follows from the fact that while 89 may not be composite, it is the sum of two squares. 89 = 25 + 64 = 52 + 82.

Taking the sum of two squares may remind you of the Pythagorean Theorem, and that is exactly where I was headed. Make a right triangle where the legs have length 5 and 8, and the hypotenuse will have a length of sqrt(89). And then, naturally, if you make a square out of four sides with that length, it will have an area of 89:

So I have something that indeed has the desired area, but you might complain that having sides that slice obliquely to the square grid makes it entirely unsuitable for tiling with a set of polyominoes. But suppose we stitched the pairs of opposite sides together. That would turn the figure into a torus, which “unwraps” into a repeated, plane-filling pattern:

Which we can tile! If fact, tori are generally relatively easy to tile because they have no edges, and the edge is typically the hardest part of a pattern to tile. Having small pieces in the mix, as we do here, also tends to make tiling easier. So for a challenge, we could try something harder.

Problem #44:

Find a a tiling of the torus above with the 1–5-ominoes where none of the pieces of size 4 or smaller are adjacent to each other. Touching at corners is okay, but if you can find a solution without that, that’s even better. (Weird, it’s been three years since I’ve posed a numbered problem on this blog.)

This problem runs into a wall in my current setup for solving polyform tiling problems. I typically add ugly hacks to my copy of David Googer’s Polyform Puzzler. It’s reasonably handy because it’s open source and written in my language of choice, Python. But it doesn’t include a hook for pruning the search tree when you come to a configuration that doesn’t meet a desired condition. For problems with a small enough search space this doesn’t matter; you can just filter finished solutions as long as the time needed to run a complete search is reasonable. But here the high tilability is actually a curse: the solver starts in an area of the search space where the adjacency condition isn’t met, and because the pieces are so numerous and so tilable, it can stay there for an extremely long time before it decides to change out any of the tiles placed early on. (There are technical reasons why hacking in the hook I would need appears to be difficult, but I won’t get into those here.)

Coincidentally, the area of the 1–4-ominoes, 29, is also a sum of squares:

Any parallelogram can be used as the fundamental domain of a torus. Rectangle and rhombus shaped fundamental domains can have just as much symmetry as a tilted square. (Because the square is tilted, flipping it over isn’t a valid symmetry action, though rotating it still is.) But the tilted square tori still strike me as particularly pleasing and unexpected patterns for tiling.

1. Bryce Herdt says:

I’ve partially solved the problem for just 1-4-ominoes on the smaller torus. Numerous small adjustments on your tiling rendered it unrecognizeable:

TTLLL1IO
TI%%%SIO
1IOOSSI2
SIOOS#TT
SI22L##T
#TTTLLL1
##TI%%%S
LL1IOOSS

But then I noticed a much easier solution. In your figure, take the tetrominoes LST plus the monomino and L-tromino as one symmetric shape (area 16, more than half the 29) and flip it.

I don’t know if either problem is solvable with no corners touching. Inflating every non-largest polyomino by a half-unit gives them a simulated area of 4+6+8+8=26 in the 1-4 case and 26+40+9=75 in the 1-5 case, so that doesn’t rule anything out.

At least in the 1-4 case, you could start with the four inflated polyominoes and three filler monominoes to start a search space, with the benefit that the filler monominoes correspond to the only 3 candidate positions for the O tetromino.

2. munizao says:

Nice. I think when I found that 1-4-omino solution, I was looking for a solution that separated the smaller polyominoes and that also grouped the tetrominoes so that they didn’t wrap around the torus. When I couldn’t find one that did both, I settled for one that only did the latter.

3. The mono- to pentominoes have a solution with no sub-pentominoes touching at edges or corners.

4. munizao says:

Very nice. The standard follow-up question: can it be done without crossroads?