Occupy a field with tetrominos

Question

You have a square 8x8 board, and tetrominoes of all possible shapes. Each individual square on a tetromino is the same size as one square on the board (i.e. any given tetromino will cover exactly 4 board squares). You can put the tetrominoes on the board in any orientation (rotated, flipped), but they must be aligned with the squares on the board, and can't extend off the board or overlap another tetromino.

The task:

Place tetrominoes on the board in such a way that it is impossible to add another tetromino, using the fewest number of tetrominoes possible. You will end up with many blank spaces on the board, of up to 3 squares in size.

What is the smallest number of tetrominoes that can be placed on the board, fulfilling the requirements above?

Answer 1

Here is yet another solution with 9 pieces. This one is nice and symmetrical.

I have been trying to think of a way to show that 8 will not work by arguing in terms of the number of edge squares that need to be covered. However, I have not got very far with this. Here is a diagram I have been pondering.

Update

I haven't really given this a lot more thought. Call a piece an "edge piece" if it covers at least one edge square (by which I mean the 28 squares that have orthogonal borders with fewer than 4 other squares). It is easy enough to show that a solution must have at least 4 edge pieces. It is also easy to show that if a solution has exactly 4 edge pieces then it needs another 5 pieces, so it follows that any solution with at most 8 pieces needs at least 5 edge pieces.

Update 2

Here is another approach that may be more promising. Consider the set of all square-edges, that is to say: each of the 64 squares in the board has 4 square-edges but most are shared between two adjacent squares (some are unique to a single square, that is to say those at the edges of the board). There are 9 * 8 * 2 = 144 square-edges.

Each tetromino accounts for at most 13 square-edges, considering both its external and internal square-edges. So if you have 8 of them you've accounted for 8 * 13 = 104 square-edges, leaving 40. Of these 40 some of them are the internal square-edges of gaps, and some of them are square-edges at the board edge where there is a gap. Per the second diagram above, at most 21 edge squares may belong to gaps. We have to take into account that some might be edge squares at the corner, so an upper bound for square-edges at the board edge where there is a gap is 25.

This leaves 15 for internal square-edges of gaps. It's fairly easy to show that you can have at most 21 of these. If we could show that at least 7 external square-edges of tetrominoes are shared between two tetrominoes, we'd have an argument. So the roadblock here is showing that in any solution, there are at least 7 spots where two tetromino squares border each other orthogonally.

Update 3: There is no 8-piece solution in the case of a torus

This problem came back into my mind this evening and I came up with a proof that 8 pieces are not sufficient on a torus. By "on a torus" I mean replacing the chessboard of the original problem by an 8*8 tiled torus ("donut-shaped" surface); think of the original chessboard but the squares on the top row border those in the bottom row, and the squares in the leftmost column border those in the rightmost column. Tetronimoes may be placed so that they straddle these newly-invented borders.

Consider that a tetromino has either 8 border edges (if it is the 2x2 square tetromino) or 10 border edges (if it is any other tetromino). In contrast to this, a gap (being at most 3 squares in size) has no internal vertices and has a fixed number of border edges (dependent on the size of the gap). A gap of size 3 has 8 border edges, a gap of size 2 has 6 border edges, and a gap of size 1 has 4 border edges.

Suppose we have a solution with 8 tetrominoes. There are 64 - 8*4 = 32 squares not covered by any tetromino. These must be arranged into gaps of size at most 3. The way of doing this that leads to the least total border edges of gaps is to maximise the number of gaps of size 3. This means 10 gaps of size 3 and 1 gap of size 2. This gives rise to 10*8 + 1*6 = 86 border edges of gaps (and none are counted twice, because if they were then the two gaps would not be distinct). However, each border edge has to also be the border edge of a tetromino, and each tetromino border edge can be paired with only one gap border edge. There are only 8 tetrominoes by hypothesis, and as remarked previously each tetromino can have at most 10 border edges, so this gives us at most 8*10 = 80 tetromino border edges, which is less than the 86 we require.

I should justify the claim that the way of decomposing the 32 squares (in fact any number of squares) into gaps (of size at most 3) that gives rise to the fewest gap border edges is to make as many gaps of size 3 as possible. First observe that to achieve the fewest possible gap border edges, we should not have both a gap of size 2 and a gap of size 1, for if we did, then these two gaps would contribute 6 + 4 = 10 gap border edges between them whereas we could combine them together into a gap of size 3 and have only 8 border edges. Secondly, observe that we should not have 3 gaps of size 2, as this would give us 18 gap border edges against the 16 we would have with 2 gaps of size 3. (Of course, we should not have 3 gaps of size 1 either.) Lastly, observe that if we have 2 gaps of size 2 then we are no worse off by switching to one gap of size 3 and one gap of size 2 (2*6 = 12 = 8 + 4).

Answer 2

Here is a solution with 9 tetrominos:

I made some calculations for an upper limit to see if bruteforcing 8 tetrominos would be possible, and it doesn't look good:

• 64 starting positions for the first tetromino
• 60 for the second
• 56 for the third
• ...
• per starting position 2*3*3 possibilities

End result: 3.7e23

Answer 3

There are many solutions with:

9 tetronimos.

Here is another one:

!
_{(source: jinchess.com)}

(Thanks Sleafar for showing me how to post a solution without my poor drawing skills!)

Here is a (tentative) proof that you can have no less than the aforementioned number of tetrominos:

We can prove it with any 9-tetromino solution, but it is clearest with Sleafar's answer. All spaces are in sets of 3 squares, except for one of them, which is a 1-square space. To reduce the number of tetrominos further, 4 more squares need to become spaces, i.e. 10 trinominos plus 1 domino. Hereon we will consider the placement of these trinomino "spaces".
Now, tile an 8x8 board with trinominos such that no two trinominos are touching (think Blokus, only corners can touch). It is easy to see that a maximum of 11 trinominos can be placed. Let's call the set of such trinomino solutions $S$. Using the pigeonhole principle, it is clear that there are no solutions in this set where the majority of interstitials are 4 or more squares.
To get to the set of 10 trinominos plus 1 domino, we only need to move one of the trinomino squares from set $S$. However, no matter which square we pick, the majority of other interstitials are still not going to 4 or more squares. 9 tetrominos is therefore the best solution.

Answer 4

Here is one with 8 tetrominos and 1 square (black).

Maybe it's possible to rearrange some tetrominos and get rid of that last square?

Answer 5

OPTIMALITY SOLUTION GUIDELINES

As several people pointed out already, it is not hard to give an example with 9 tetraminos. I also believe this is the correct answer and even though proving it rigorously requires long and tedious case analysis, I will give some guidelines.

Start by assuming the contrary, i.e. it is possible to use only 8 tetraminos.

STEP 1.

Prove that if a rectangle 4x8 is covered by 4 tetraminos with no space for more, then its top row of length 8 both either contains at most 2 squares covered by tetraminos or does not contain covered squares at positions {1,2,7,8} or {3,4,5,6}. This implies that it is impossible both the bottom and the top half of the checkboard contain 4 full tetraminos.

STEP 2.

Prove that it is impossible that both the top and the bottom half of the checkboard to contain one full tetramino and to share 6 more tetraminos. Prove that it is impossible that the top half of the checkboard to contain only 3 full tetraminos and a part from another one. Similarly for the bottom half. These two are fairly easy.

STEP 3.

Now the remaining cases are:

the top and the bottom half share 4 tetraminos and each of them contains entirely 2 more tetraminos;

the top and the bottom half share 3 tetraminos and each of them contains entirely 2 or 3 more tetraminos;

the top and the bottom half share 2 tetraminos and each of them contains entirely 3 more tetraminos;

All of these 3 cases require lots of consideration, including number of squares covered by tetraminos by a half checkboard, squares covered on the middle rows (the 2 middle rows should contain at least 6 covered squares), etc. Also I think it is good to consider the four 4x4 corners of the checkboard, since each of them either contains one full tetramino or contains many partials. It may be possible to simplify the case analysis even more, but I'm not sure it is worth to work on it. I hope these guidelines help someone find a complete proof.

Answer 6

So I was thinking about this and there's the beginnings of a proof. Think about the perimeters of the shapes. The tetronimos have perimeters of length 10 (or less in the case of the square). The outside has 32. There's at least two edges touching at each side, so that removes 8 edges at least, so there's a maximum of 96 free edges. Any additional edge that's touching will reduce that number by 2.

Now count the spaces in between. We intuitively think that these will generally be trionimos, but they could be smaller. They will never share an edge with each other (obviously) just with the outsides and the tetronimos. There are 32 spaces. If they were all dominoes then you'd have a perimeter of 16 dominoes times 6 edges, or a total of at least 96. Since that equals the 96 from the first paragraph we know that if there is just one additional overlap (between the edges of two tetronimos or a tetronimo and the side of the board) then it cannot be done with just dominoes.

The best case for these is that there are 10 trionimos, and 1 domino, for a total of 86. So if we can demonstrate that there have to be more overlaps than the basic 2 per side, we'll get closer. You'd just need 5 additional overlaps to get you there. I think you can get 1 in each corner (at least in certain cases), which would mean you'd need just one more shared edge to be required to blow the solution up.

At the very least this should help people looking for a solution!

Edit to take the proof further:

To summarise where we got to:

• We have a minimum perimeter of 86 from the empty spaces.
• We have a maximum perimeter available of 96 from the tetronimos and outer edges
• Any additional overlaps (apart from the 2 squares per side) reduces the maximum perimeter available by 2.
• Meaning that if we can find at least 6 overlaps, we prove that 8 tetronimos is insufficient.

(Aside: The numbers for an 8x7 square are 76 minimum and 88 maximum, which may explain why this is possible, where the 8x8 is (probably) not.)

I will now show that each corner adds at least one additional overlap, essentially getting us 4 of the 6 overlaps we need to prove our case.

Case 1:

Suppose we have three blanks in the corner, as shown in yellow. Then the squares marked X1 and Y1 must be part of two separate tetronimos (call them X and Y respectively). If the squares marked X2 or Y2 were part of their respective tetronimos (X & Y), then we'd have an additional overlap (between tetronimo and the edge).

Hence suppose that X2 and Y2 are not part of their tetronimos. Then X3 and Y3 are. But then the square marked * must be part of either X or Y, and either way X and Y share an edge.

Case 2:

More or less exactly the same argument, but with a different picture. In this case the * can be X, Y or some third tetronimo (which would give us two overlaps). - Thanks to @Sleafar for point out that this proof is wrong. It can however still be proved, I believe, by considering more elaborate cases.

For case 2, we need to extend the scenario to both corners and look for 2 overlaps. See the above diagram. From the basic blank squares three in the top-left corner, you can build up other parts of the board that must be this way or add an additional overlap. Specifically X extends along the bottom of the blank squares, and Y comes out at Y3. There must be three more blanks in the top right, and Z must be at Z1 and Z2. We know we're going to get an extra overlap where Y and Z join, so we need to find one more.

Scenario 1 has Z3, which leads to Y4 and Z4. The two squares below Z1 must be blank, as well as the one below Z4. This creates 3 blanks together, which must be surrounded by tetronimos. Specifically the square A1 must be a tetronimo. That leaves the square with an *, which is a single blank square. A single blank square will push up the minimum by 2, which is equivalent.

Scenario 2 has Y4. The square below Y3 must be blank, as well as the square below the blank below Y1 (otherwise we'd have a single blank again). That means the square marked with an * must be a tetronimo (either Z or a new tetronimo). Either way, there's an additional overlap.

Case 3:

Easy peasy. X2 has to be part of X, so you get an extra overlap between X and the edge of the board.

Case 4:

Finally, in the case of the a domino on the side, it either reduces to a similar situation to Case 2 above, or it's surrounded by a tetronimo, shown as X1,X2,X3,X4 in the diagram (call this tetronimo X).

In this scenario, consider the yellow squares marked B2. If any of them are part of another tetronimo, then you have an extra overlap. So suppose they are all blank. Then the square Y1 must be part of a new tetronimo, which is an additional overlap.

Other cases:

Other cases are kind of trivial, but for the sake of completeness:

• If the corner is a single blank square this is effectively the same, because two blank singletons adds to the minimum perimeter by 2.
• If the corner has a tetronimo in it, then one of the adjacent edges must have the same tetronimo, and so you have an additional edge.

Where we are

So each corner definitely creates at least one additional overlap. This brings the maximum available perimeter down to 88, which is almost the minimum perimeter (86).

If we can find two more overlaps then we prove that the 8x8 board cannot be covered by 8 tetronimos.

I suspect that this can be done by considering a few more cases. This may be susceptible to a computer search for all possible cases along one edge.

We can also make the following conclusions, based on the above. A 8 piece solutions would:

• Not use any of the straight tetronimo, because the four squares running along-side the tetronimo must have another tetronimo in it, which would be an additional overlap not covered above.
• Not use the square tetronimo, because this would reduce the maximum available because of its lower perimeter (8 vs 10 for the other tetronimos).
• Have 10 trionimos and 1 domino as the blank spaces.

The first of these is particularly interesting. It eliminates the case where the 8 squares touching the edge of the board are 8 separate tetronimos, because the middle four squares could only have one covered by a straight line tetronimo.

These restrictions certainly seem to support the thesis that 9 is the minimum, but we're not quite there! - Thanks, @Sleafar

Answer 7

I found a few interesting things. Purple and orange are used to highlight recurring structures, green is general, black is the flaw.

8 pieces, no edges touching, no unfilled areas of size 1, near-success.

______

8 pieces, no edges touching, lots of unfilled areas of size 3, near-success.

Answer 8

Here's a slightly easier method (at least easier for me, with a tiling program): 1. Tile the 8x8 with all five tetrominoes, allowing multiple copies of each but no more than 8 total. 2. Also allow both trominoes, the domino and the monomino, as many copies of each as you like, but disallowing them from touching each other, except at a corner.

If you do a complete search and find no tiling, that proves 8 can't be done: Because any tiling of eight non-touching tetrominoes into the 8x8 which has no space left over for another tetromino, has only areas not covered by tetrominoes which conform to one of the four smaller shapes. So you would have found it. This also allows finding all solutions to the 9-tetromino case. Downside is it will take a few days to run.The 9 case even longer.

========

8x8 case is finished. No solutions. Statistics: I ran 12 copies of the program, initially placing the first piece in a corner in all possible ways. Total running time for all 12 copies was 371 hours. Total pieces placed by all 12 copies was 174.6 billion. Yes a logical proof would be nicer.

I tried the same with the 9-tetromino version, I let it get to about 10% complete, with 3.8 million solutions found. So very rough estimate is up to about 40 million solutions. 275 hours to get to 10%, so probably ten days of running with 12 copies to complete it. I'm not going to bother.

Answer 9

Some hints for a proof of 8 tetrominoes being an impossible solution:

Let's flip the question, to lay emphasis on the blanks, rather than the covered spaces.

Fill 32 cells of an 8x8 grid with monominoes, dominoes and/or trinominoes such that:

(a) No two pieces touch each other

(b) The leftover squares can be occupied by 8 tetrominoes

Solving the above Q alone is enough, you may wish to avoid reading the possible method of proving, which I have given below:

Possible method of proving

(Method relies on an intelligent brute-forcing program) For every piece that is placed, there are a certain no. of cells that are adjacent to the piece. No other piece can be placed on them (ofcourse, we will place the tetrominoes there, but forget that for now), hence they are called BLOCKED. The number of cells a piece occupies (1,2 or 3) is called USEFUL. For example, an I-shaped trinomino in the middle of the board will look like this

  B B B   
B X X X B
  B B B

We have 3 Xs (USEFUL) and 8 Bs (BLOCKED). Hence ratio is 3:8.

If the same piece was placed on the edge:

_________
B X X X B
  B B B 

Ratio is 3:5

A piece placement with a high USEFUL is to BLOCKED ratio is more optimal. For the corner, the placing with the best ratio is an L-shaped trinomino (Ratio 3:3). Hence we cover all 4 corners in this manner. For the side of the board, the best placement is an L-shaped trinomino touching the edge with 2 cells, giving a ratio 3:5. (I-shaped trinominoes also have 3:5 ratio, but there is no space to place them.) Hence we cover each edge in such a manner. We now have:

X X   X X   X X
X     X       X

X           X X
X X           X

X       X     X
X X   X X   X X

We have successfully occupied 24 squares. We need to occupy 8 more. Even by trial and error, it appears impossible. Let's trying proving it.

For floating pieces (not touching the edge), the best ratio is still given by the L-shape (3:7), followed by the I-shaped (3:8). A domino gives 2:6, and a monomino gives 1:4. The best option seems to be two L-shaped trinominoes and a single domino. However, we are unable to place them.

Since the "supposedly optimal" solution fails, we try solutions slightly worse than the optimal one. Probably, a program will be good at this. The program should keep trying worser and worser piece placements (in terms of the ratios), until it becomes obvious that there is no solution.

Flaws

1.My method more-or-less ignores rule (b). If there are cases where rule (a) is fulfilled, they should be very few in number, and the program should quickly be able to check for satisfaction of rule (b)

2. And, it ignores the fact that BLOCKED squares are often shared by trinominoes/dominoes/monominoes. Preference should be given to BLOCKED squares shared by three pieces, rather than two. I don't know how to implement this. Hence I said, use a program to test cases slightly worse than optimal also.