Domino tiling on 8x8 checkerboard with four squares removed

Question

I once posted this problem on the (now deleted) Area 51 Math Puzzles proposal. It was well-received there, but obviously I didn't get an answer. I still don't know the answer, and I'm not even sure if it can be solved by pure mathematics. But I'm still curious, so here it goes.

---

Imagine a 8 × 8 checkerboard.

If you remove two opposite corner squares from the board, it is well known that you can't tile it with 31 dominoes.

But if you remove any two squares of opposite color (one black and one white), it is also known that you can always tile it with 31 dominoes.

Then, is the following statement true or false?

if you remove any two black and two white squares (removing four in total) so that the resulting board is still connected, you can always tile the remaining 60 squares with 30 dominoes.

Answer 1

Here is my attempt at a proof.

First I'll prove a useful set of shapes that can be covered by dominoes when two opposite-coloured squares are removed.

Take any polyomino, a shape made of square units, joined edge to edge. If you split its units into 2x2 smaller squares, then there will be a Hamiltonian cycle, i.e. a closed loop path that visits all the small squares. It is easiest to see in a picture:


You could prove this by considering the graph with as its vertices the centres of the original polyomino units, and where two vertices are connected if their units are adjacent. Take a spanning tree of this graph, and this forms a skeleton around which you have a loop of the smaller squares.

The standard proof of the existence of a domino covering of a chessboard with one white and one black square removed also applies to any such polyomino made of 2x2 units.

Now let's apply this to the problem at hand.

Think of the chessboard as consisting of a 4x4 grid of units, each of which is subdivided as a 2x2. Suppose the four holes lie in four different units. It is then easy to split the board into two polyominoes that each have one white and one black hole. This is because the 4x4 grid of units itself has a Hamiltonian cycle, and whatever order this cycle visits the holes, you can split it in two places so that each part has one white and one black hole. Each of those two parts is then a polyomino made of 2x2 units, which can be covered by dominoes regardless of where its white and its black hole are.


It gets a little trickier when a 2x2 unit contains more than one hole.

If a unit contains 4 holes, then the rest of the board is a single polyomino that can be covered by dominoes.

If a unit contains three holes, then the rest of the board is a single polyomino to which you can append a 1x2 or 2x1 part of this unit that contains only one hole. See the picture below. Even if the unit is in the corner of the board, at least one of these two options will be available.

If a unit contains a white an a black hole, then take that unit to be a single monomino, and the rest of the board the other polyomino, and both can be covered by dominoes.

If a unit contains two holes of the same colour and it is not in a corner, then you can split it so that it contributes a 1x2 or 2x1 domino to the adjacent units on opposite sides (top and bottom or left and right. There is a Hamiltonian cycle through the 4x4 grid of units that goes straight through this two-holed unit, so the same argument as before allows this to be split into two polyominoes that each can be covered by dominoes regardless of the location of their two opposite-coloured holes. If a corner unit has two holes of the same colour, then it can donate a 1x2 and a 2x1 domino to adjacent units, even though they overlap. This is because that overlap will contain the hole, and hence their domino tilings will not interfere with one another.

Answer 2

Sketch of proof:

Let's call a subset of the board holier than two "ht2" if it can be domino tiled after removing any black-white pair of squares, and, similarly, "ht4" when removing pairs of pairs and "ht0" simply for tileable.

Our strategy to show the entire board is ht4 is to demonstrate that given the four holes, the board can most of the time be split into two ht2 parts (and some ht0 debris if convenient) that each contain one of the black-white pairs. The exceptions will be case bashed to death.

First, let us compile a large enough list of ht2 geometries. We can use:
any connected union of aligned 2x2 squares ("A2x2" for short; "aligned" meaning all coordinates of corners are divisible by 2) (One can show that each pair of A2x2's - in particular, those containing the holes - can be joined by a closed domino path that precisely fills a subset of the A2x2's. This path can be easily adjusted to accomodate the holes.) Also note that if we find two such subssets for two black-white pairs we can simply discard what's left over because any A2x2 is ht0.

Case 1

The four holes fall onto four different A2x2's:
As we are free to pair either white hole with whichever of the blacks we deem more convenient this case is easy: Form a non self intersecting quadrilateral from the four A2x2's and find a pair of non-adjacent non-mochromatic edges. If the quadrilateral lis degenerate handle the tedious but straight forward case work otherwise connect the endpoints of either selected edge by A2x2's. We can guarantee no interference by connecting in an axis parallel L shape with the kink on the outside.

Case 2:

Two or more holes fall on the same A2x2. If they are different color we are done. In the other case we must connect this square to all others. A double connection is required if the other two holes also share an A2x2. Also, some care must be taken to connect in such a way that the two holes fall onto different "lanes" of the A2x2 "highway". (This is where the connectedness assumption comes in.)

Answer 3

Perhaps it is worth pointing out that it isn't necessarily possible to tile a chessboard with 6 squares removed even if there are 3 of each color and the remaining squares are all rook-connected.

........
........
........
........
........
........
X.X..X.X
...XX...

So for any proof that it is possible with 4 squares removed, one should be able to point out where the proof would fail if 6 squares were removed instead. I am not sure that some of the answers given would meet this standard.

Answer 4

It's true.

First of all, let's prove that any rectangular board with an even value of area can be filled with two opposite-colored squares removed.

We can figure out two opposing corners of such a rectangle can be removed to satisfy that:


For this to happen, $a+b-2$ must be odd but at least one of $a$ and $b$ even, so only one of them is even.

Now, any rectangular board with two removed squares of opposing colors and an even value of area can be reduced to the first picture or another rectangle with at least one removed square at most 1 row and 1 column away from the corner. This rectangle can always be filled:

For this reason, an odd-area rectangle can be covered when a single square of the more common color is removed:

If an 8x8 board can be divided into two rectangles lengthwise or widthwise with two removed squares of both colors each, they can be covered unless one rectangle just consists of a single column or row of squares, and even then (O: odd, B: even):

If an 8x8 board can be divided into two rectangles lengthwise or widthwise with three of the removed squares in one and one in another, they can also be covered:

Single pink squares: non-removed "maroon" squares
Single light blue squares: non-removed "dark blue" squares
1 outside: rectangular area with more maroon squares than blue
2 outside: the opposite:

Answer 5

What you claimed is true, and from my side, I think this problem is simple.
I will propose an algorithm for this.

First, I choose two black and two white squares from the board (red tiles are removed tiles) , now start from the pink square, and continue placing dominoes horizontally till the entire row is full. This is important because we need to place dominoes from the starting tile of every row. This will always work if there is no removed tile in that row.

On moving to the next row, we see that there is a removed tile, so by our way there will be a gap of one tile left. Place that with a vertical domino, and continue this with other rows. You will see that the entire board will be covered.

Why This Method Works?

This works because when there is a one tile gap, we are placing a domino vertically, and that domino is also covering one of the squares above it's row. If that row, specifically, has a removed tile, that row will get covered. If not, then that row will also have a one tile gap, and we place another domino vertically, and so on. Notice that in every step, whenever there are two removed tiles, the entire board can be covered. So removing two more tiles does not matter, we can still cover the board.

Note :- This will also work if we consider columns instead of rows.

This topic, however, is interesting because it can make us think that for which $n$ , if we remove $2n$ tiles from an $m * m$ board ($n < \frac{m^2}{2}$) it is always possible to fill it up with dominoes, because for $n = 62$ in this case, this definitely won't work.

An example a tiling requested by @Jaap Scherpuis:-

I have taken an example of two removed tiles in the same bottom row, allowing me to place two vertical tiles, and notice in the end it perfectly fitted with dominoes. Also notice that I have only tried my algorithm, that is I have placed only horizontal dominoes wherever possible.