45
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ @IanMacDonald It does! It took me a lot of time to ensure it. $\endgroup$ – Alexandros Mar 2 '17 at 15:11
  • 1
    $\begingroup$ Do the black sections support weight or not? $\endgroup$ – KRyan Mar 2 '17 at 22:11
  • 3
    $\begingroup$ @KRyan No, they are void. $\endgroup$ – Alexandros Mar 2 '17 at 23:05
  • 4
    $\begingroup$ @Alexandros You should add that to the question. $\endgroup$ – KRyan Mar 2 '17 at 23:07
  • 1
    $\begingroup$ 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. $\endgroup$ – CJ Dennis Mar 4 '17 at 9:03
49
$\begingroup$

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!

$\endgroup$
  • 7
    $\begingroup$ 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 :) $\endgroup$ – Megha Mar 3 '17 at 1:58
  • 2
    $\begingroup$ Incredible answer. The best 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. $\endgroup$ – Rand al'Thor Mar 4 '17 at 14:01
  • 1
    $\begingroup$ Aw, you used more than four colors. (though I think this particular picture's chromatic number is 3) $\endgroup$ – Nic Hartley Mar 4 '17 at 18:24
  • $\begingroup$ @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. $\endgroup$ – Victor Stafusa Mar 4 '17 at 20:10
22
$\begingroup$

I think that this tiling is a valid Tetris stack:

Tetris tiling

$\endgroup$
4
$\begingroup$

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

My solution

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Rubio Mar 3 '17 at 13:16
  • 2
    $\begingroup$ +1 for the approach used. I was pretty certain on reading the question the most upvoted answer used far more power than necessary. $\endgroup$ – Joshua Mar 4 '17 at 15:33
  • $\begingroup$ 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. $\endgroup$ – Darren Ringer Mar 5 '17 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.