48

The goal is to tile all the white squares using T-tetrominos when there is gravity pulling the tetrominos downwards like regular tetris. The black squares are void and the ground is just below the bottom row.

enter image description here

If you have played tetris, it is obvious what gravity means but just for clarity here is an example: The red one is not allowed because it will fall down. The green one is okay.

enter image description here

This is a logical deduction problem so no guesswork is needed. In your solutions try to explain at least the trickier deductions.

Rand al'Thor
  • 116,845
  • 28
  • 322
  • 627
Alexandros
  • 1,137
  • 10
  • 16
  • I wonder if this is guaranteed to have a unique solution. – Ian MacDonald Mar 02 '17 at 15:05
  • 2
    @IanMacDonald It does! It took me a lot of time to ensure it. – Alexandros Mar 02 '17 at 15:11
  • Aahhhh, I glossed over the "only T" bit. Now it makes more sense that you'd be able to make it unique. :) – Ian MacDonald Mar 02 '17 at 15:17
  • I came to the same solution as posted below - I didn't see any particularly tricky deductions. I mostly worked from constrained areas on the top/bottom and worked my way in. (I did accidentally violate the gravity constraint, but it was an easy fix once I realized it.) – Nathan S. Mar 02 '17 at 17:06
  • 1
    Do the black sections support weight or not? – KRyan Mar 02 '17 at 22:11
  • 3
    @KRyan No, they are void. – Alexandros Mar 02 '17 at 23:05
  • 4
    @Alexandros You should add that to the question. – KRyan Mar 02 '17 at 23:07
  • @KRyan I don't thing that it is needed. If they supported weight, then there wouldn't be any gravity at all. – Alexandros Mar 02 '17 at 23:09
  • @Alexandros It is absolutely needed. What you say isn’t strictly true, and I for one assumed the opposite at first. – KRyan Mar 02 '17 at 23:10
  • @KRyan I made the change you suggested. But I still think that what I said is true and it was not necessary. Thanks for the comment anyway! – Alexandros Mar 02 '17 at 23:16
  • 1
    I didn't understand the question until I was 3/4 of the way through the first answer! Having played Tetris, I thought the goal was to clear the area by placing additional pieces in the black areas. The goal is not to tile the area, but to identify how the white area is already uniquely tiled. – CJ Dennis Mar 04 '17 at 09:03

3 Answers3

52

TLDR: I'll fill the board and prove that the solution is unique.

First, let's start by:

Looking for corners where T tetrominoes could only be filled in by no more than one unique way.

I'll paint those green:

green

Let's repeat those steps a few more times, using orange, blue, red and purple, in precisely that order:

green, orange, blue, red and purple

Now,

let's focus on the topmost white square.

It can't be filled by a right-looking T tetromino, because this would imply a sequence of two white squares in the left, where one of then couldn't be filled in any way. It also can't be a left-looking or down-looking because this would leave a isolated sole white square. Thus, it must be up-looking (brown):
added brown

We can easily fill the topmost white squares by that reasoning. They can't be filled in any other way:

more colors

Now, let's look at:

The bottommost white cells, at the right side of a green tetromino.

The white cell at the very right of the green-painted tetromino could only be filled with an up-looking tetromino, or a right-looking one. However the right-looking one would leave a isolated white cell. So it must be filled with an up-looking one (brown again):
enter image description here

And by repatedly filling the remaining squares with the only obvious possibility every time:

advanced in solution

Now the problem is divided in two. Let's start with the upper part:

There is more than one way to fill this with tetrominoes. But only one of them respect gravity.

Look at the white spaces right to the light blue tetromino. If you put a right-looking or a down-looking one, it would leave isolated white cells. So the tetromino at this spot must be either up-looking or left-looking. Let's try a left-looking. Under it, we won't have space to put a right-looking or a left-looking tetromino, so we can try a down-looking or a up-looking one:

Down-looking:
NOOO!!!
Up-looking:
Neither

So it must be up-looking:
new red

The rest of the upper part:

Let's start with the bottommost part of the upper white spaces. If you put a right-looking tetromino or an up-looking tetromino, you would leave single white cells hanging around.

What if we put a left-looking one?

defying gravity

So:

It must be down-looking. The remaining cells in the uppermost part can also only be filled in one way respecting gravity:
top part finished

To the bottom part:

Let's start with the rightmost white cell. An up-looking or left-looking tetromino would leave solitary white cells. So it must be either right-looking or down-looking.

Let's try a right-looking one:

bad choice
Trying to change the position or flipping the blue tetromino is also hopeless. There is no way to fill both the white cells at the red tetromino's left.

So, using a down-looking and filling the obvious spaces:

almost done

And there is only a single way to finish without defying gravity:

done

DONE!

  • 7
    Wow, this answer is nice. The sequence of pictures is really helpful in visualizing not only what the answer is, but how to reach it. And extra bonus points, if I could, for the bits of added humor :) – Megha Mar 03 '17 at 01:58
  • 3
    Incredible answer. The best [tag:logical-deduction] answers are those that not only give the correct solution but also explain the thought processes needed to reach it, in a clear and understandable way. – Rand al'Thor Mar 04 '17 at 14:01
  • 2
    Aw, you used more than four colors. (though I think this particular picture's chromatic number is 3) –  Mar 04 '17 at 18:24
  • @QPaysTaxes I didn't care about minimizing the number of colors. I just tried to use the ones that would make it better for me at explaining what is going on. M. Oehm answered it with three colors, so this is an upperbound. It is also easy to find a few places where three different tetrominoes are neighbouring one to the other (the first red tetromino that I added in the second picture and his light blue and orange neighbours, for example), so 3 is also a lowerbound. Thus, 3 is the chromatic number. – Victor Stafusa - BozoNaCadeia Mar 04 '17 at 20:10
23

I think that this tiling is a valid Tetris stack:

Tetris tiling

M Oehm
  • 60,621
  • 3
  • 208
  • 271
4

This is my solution (just incrementally adding only valid pieces):

My solution

user34890
  • 41
  • 1
  • 2
    Welcome to PSE! (Take the Tour!) How does your answer add to the identical ones already given? You should always look at existing answers before providing one of your own, to ensure you are not just adding a duplicate. – Rubio Mar 03 '17 at 13:16
  • 2
    +1 for the approach used. I was pretty certain on reading the question the most upvoted answer used far more power than necessary. – Joshua Mar 04 '17 at 15:33
  • I agree, applying formal logic when the solution is never more than two or three hypotheses away at any given time is a bit of overkill. – Darren Ringer Mar 05 '17 at 03:32