Covering an 8x8 grid with X pentominoes

Question

What is the minimum number of X pentominoes you need to cover every cell of an 8x8 grid? Pentominoes may overlap each other and sit outside the boundary of the grid. An X pentomino looks like this:

Answer 1

I can prove that the answer is exactly

16 pentominoes

Several people, including Jaap Scherphuis, have shown that the square can be covered with this many pentominoes, so it only remains to show that at least this many pentominoes are needed. (A matching lower bound).

Let us start with the magic board given by A. Rex:

 13  7  6  8  8  6  7 13
  7  1  6  5  5  6  1  7
  6  6  9  3  3  9  6  6
  8  5  3  7  7  3  5  8
  8  5  3  7  7  3  5  8
  6  6  9  3  3  9  6  6
  7  1  6  5  5  6  1  7
 13  7  6  8  8  6  7 13 

As mentioned by A. Rex, any pentomino placed on this board will cover squares totaling at most 27 - exactly 27 if the center is on the board, and at most 13 if not. The numbers on the board total 400.

As a first lower bound,

at least 15 pentominoes are required, because 14 pentominoes can cover squares totaling at most 14*27 = 378, and hence not all of the squares.

However,

15 pentominoes can only cover squares totaling at most 15*27 = 405. This means that if 15 pentominoes cover the board, they cannot double-cover any square or squares totaling at least 6, and no pentomino can be centered off the board. If squares totaling at least 6 were double-covered, then the sum would be at least 406, which is impossible.

Therefore, we can try placing pentominoes

under the assumption that 15 can cover the board, and see what deductions we can make. Let's label the squares like a chess board, and start by looking at the square h1, in the bottom right corner.

To cover that square,

We must place a pentomino centered at either h1, g1 or h2. h2 and g1 are symmetrical, so we only need to consider one.

Let's start by

placing a pentomino centered at h1, and see where that gets us. We now must cover the square g2. We can't do so by placing a pentomino centered at g1, g2 or h2, because those would double-cover too much. Therefore, we must place a pentomino centered at either f2 or g3. These are symmetrical, so without loss of generality let's place a pentomino centered at f2. Next, we must cover the square h3. We can't do so by placing a pentomino centered at h2, h3 or g3, because those would double-cover too much. Therefore, we must place a pentomino centered at h4. Next, we must cover the square g3. We can't do so in any way without double-covering too much. Thus, if we start with a pentomino centered at h1, we will definitely double-cover too much to cover the square with only 15 pentominoes.

On the other hand, let's try starting by

placing a pentomino at g1. I'll abbreviate what follows, using "the only option" to mean "the only option that doesn't double cover squares totaling at least 6". We need to cover h2, the only option is to place a pentomino centered at h3. We need to cover f2, the only option is to place a pentomino centered at e2. We need to cover d1, the only option is to place a pentomino centered at c1. We need to cover a1, the only option is to place a pentomino centered at a2. We need to cover b3, the only option is to place a pentomino centered at b4. There is no option available to cover c3. Thus, there is no way to cover the square with 15 pentominoes starting with a pentomino centered at g1.

As a result, we have found that

It is impossible to cover the square with 15 X-pentominoes. Any such cover must cover h1, so it must include a pentomino centered at either h1 or g1, or equivalently h2. In either case, we would be required to double-cover a set of squares totaling at least 6, which means that the overall squares covered will total at least 406, which is impossible, since each pentomino covers at most 27, for a total of at most 405.

As a result, we have a matching lower and upper bound of

16 pentominoes.

Answer 2

The X-pentomino tiles the plane, so that tiling is a good way to start. There are two ways to cut an 8x8 region out of that tiling. If one of the 4 central squares of the 8x8 region has an X centred on it, you get this

19 pentomino solution

or else you get this

20 pentomino solution

The latter can be easily improved by replacing the ones at the edges to give this

16 pentomino solution

A different way to get the same result is

to take four pentominos from the tiling. These cover a 4x4 area. By using 4 sets of 4, you get this solution.

Answer 3

Here's another proof of the lower bound in Sriotchilism O'Zaic's answer.

Consider the following 8x8 grid of seemingly magically-chosen numbers:

 13  7  6  8  8  6  7 13
  7  1  6  5  5  6  1  7
  6  6  9  3  3  9  6  6
  8  5  3  7  7  3  5  8
  8  5  3  7  7  3  5  8
  6  6  9  3  3  9  6  6
  7  1  6  5  5  6  1  7
 13  7  6  8  8  6  7 13
 

Note that if you place an X pentomino with its center anywhere on this grid, the numbers it covers sum to exactly 27. (If you place a pentomino with its center off of the grid, the numbers it covers sum to less than 27.) The sum of all of the numbers in the grid is 400. If you cover all of the numbers in the grid with X pentominoes, and each pentomino covers a sum of at most 27, it follows you must use at least 400/27 ~ 14.8 pentominoes. Since there are an integer number of pentominoes, there must be at least 15.

Answer 4

People have given some good upper bounds, how about a lower bound.

Our first lower bound can be $13$. This is the number of spaces to be filled ($64$), divided by the size of the tile ($5$) and rounded up, since we cannot have a fractional piece. This would be the number of X pentaminos required if we could fill the space with only 1 square extra (either outside the grid or overlapping)

However we can improve this ...

to $14$.
To do this we look at the corners of the square. These need to be filled by at least $1$ X pentamino so we can look at all the ways to do this. There are 3 (up to reflection symmetry); illustrated here on the lower right corner:
Now every way of doing this has at least $1$ square of the pentamino outside of the square. Additionally since the square is $8\times 8$ no pentamino can be on two corners. Thus there are at least $4$ tiles left outside the square. This means our pentaminos must fill a footprint at least $4$ larger than the square, or size $68$. If we divide by $5$ and round up we get $14$.

However we can improve this ...

to $15$. To do this we return to the corner argument given a moment ago. Let us consider the covering of the corner that only has one outside of the square. Looking at the square outlined in red below:
Since it is inside of the square the outlined space must be covered and there are $5$ ways to cover it:
Now we notice that each way of doing it either adds overlap or area outside of the square. Our best case scenario is the fourth one which has only one redundant space. This means that this way of filling the corner is at least as bad as the next worse, which left two squares out of the grid. And after verifying that the square is still to wide to cause overlap this raises our effective size to $72$ and our lower bound to $15$.

Answer 5

I’m thinking:

16

The solution:

  1  2  2  2  3  4  4  4
  1  1  2  3  3  3  4  5
  1  8  7  7  3  6  5  5
  8  8  8  7  6  6  6  5
  9  8 15 15 16  6 14 14
  9  9 15 11 16 16 14 13
  9 10 11 11 11 12 13 13
 10 10 10 11 12 12 12 13

Answer 6

This problem can also be called

finding the domination number of a grid graph.

In Computing the Domination Number of Grid Graphs by Samu Alanko, he highlights many of the formulas known for different-sized grid graphs. In particular, he quotes Hare's work "Algorithms for Grids and Grid-Like Graphs" for a m x n grid graph for m = 7, 8. Using the formula listed for m = 8 with $m\leq n$, the domination number $\gamma$ is $$\gamma_{8,n}=\Bigl\lfloor\frac{15n+14}{8}\Bigr\rfloor$$

Plugging in 8 for n, we get

16 which is the smallest number needed to cover an 8x8 grid with pentominoes :)

Answer 7

Proof with brute-force procedure. Here I used fact that we for sure can cover with 16 pentominoes, so I tried to cover half with 8 or less and then see if two such half-covers cover the whole board. It takes about 15 seconds on my PC to get the answer.

#include <iostream>
#include <vector>

const int kHalfUpperBound = 8;
const int kSide = 8;
const int kExtendedSide = 10;

class Field {
    std::vector<int> _pentas;
    std::vector<char> _data;
    int _linesCovered = 0;

    void UpdatePenta(int i, int inc) {
        _data[i] += inc;
        int r = i / kExtendedSide;
        int c = i % kExtendedSide;
        if (c > 0) _data[i - 1] += inc;
        if (c < 9) _data[i + 1] += inc;
        if (r > 0) _data[i - kExtendedSide] += inc;
        if (r < 9) _data[i + kExtendedSide] += inc;
    }

public:
    Field() : _data(10 * 10, 0) {}

    void PushPenta(int i) { UpdatePenta(i, 1); _pentas.push_back(i); }
    void PopPenta() { UpdatePenta(_pentas.back(), -1); _pentas.pop_back(); }
    void MoveTopPenta(int to) { PopPenta(); PushPenta(to); }

    const auto& Pentas() const { return _pentas; }
    const auto& Data() const { return _data; }

    int LinesCovered() {
        for (int i = 10; i < 100; i += 10) {
            if (_data[i + 1] == 0 ||
                _data[i + 2] == 0 ||
                _data[i + 3] == 0 ||
                _data[i + 4] == 0 ||
                _data[i + 5] == 0 ||
                _data[i + 6] == 0 ||
                _data[i + 7] == 0 ||
                _data[i + 8] == 0
                ) {
                return i / 10 - 1;
            }
        }
    }
};

char RowToNumber(const Field& field, int r, bool reverse) {
    char teeth = 0;
    int offset = reverse ? 7 : 0;
    int sign = reverse ? -1 : 1;
    for (int b = 0; b < kSide; ++b) {
        if (field.Data()[r*10 + 1 + offset + sign * b] != 0) {
            teeth += (1 << b);
        }
    }
    return teeth;
}

std::vector<int> solve() {
    Field field;

    int best = kHalfUpperBound + 1;
    std::vector<int> pentas;
    int gi = 0;
    const int linesToFullyCover = kHalfUpperBound / 2;
    // After first 5 extended lines we should have covered 3 primary lines
    for (int i = 0; i < (linesToFullyCover + 1) * 10; ++i) {
        field.PushPenta(i);
        if (field.LinesCovered() >= linesToFullyCover) {
            const char teethIn = RowToNumber(field, linesToFullyCover, false);
            const char teethOut = RowToNumber(field, linesToFullyCover + 1, true);
            if (teethIn ^ teethOut == 1 << (sizeof(teethIn) * 8)) {
                const int curBest = field.Pentas().size();
                if (curBest < best) {
                    best = curBest;
                    pentas = field.Pentas();
                }
            }
        }
        while (i + 1 == 50) {
            field.PopPenta();
            i = field.Pentas().back();
            if (field.Pentas().empty()) return pentas;
            field.MoveTopPenta(++i);
        }
        if (field.Pentas().size() == kHalfUpperBound) {
            i = field.Pentas().back();
            field.PopPenta();
        }
        if (++gi % 1000000 == 0) std::cout << gi << std::endl;
    }
}

int main() {
    const auto pentas = solve();
    for (auto p : pentas) std::cout << (p / 10) << ',' << ((p - 10) % 10) << "  ";
    std::cout << std::endl;

    return 0;
}

Output for the upper half is

1,2 1,6 2,4 2,8 3,1 3,5 4,3 4,7

So the number the minimum number of pentominoes needed is

16