Gengulphus wrote:cinelli wrote:... Instead of going from top left to bottom left. I made a closed loop as follows:

...

This choice is by no means unique but it has a pleasing symmetry. The squares lie with alternating colours along the closed path. The removal of two squares of opposite colours from any two spots along the path will cut the path into two open-ended segments (or one if the two removed squares are adjacent on the path). Since each segment must consist of an even number of squares, each segment, and therefore the entire board, can be completely covered by dominoes.

...

As a follow-up puzzle that I don't have the answer to (or at least not yet!), suppose we remove two black squares and two white squares, without isolating any of the corner squares by removing the two adjacent squares and not removing the corner square itself. Can one always cover the remaining squares with dominoes, or are there other cases in which they cannot be covered?

One small point that has occurred to me about that follow-up puzzle. Often, one can still find a closed loop through all the squares and visits black and white removed squares alternately, in which case the four segments of that closed loop that the removed squares split it up into each contain an even (possibly zero) number of squares and so can separately be covered by dominoes. This isn't possible for the configurations I described, because the loop must visit two squares adjacent to the corner square immediately before and after visiting the corner square itself. The point that has occurred to me is that such a closed loop also isn't possible if the four removed squares are all on the edge of the board and appear in a black/black/white/white order (or some rotation of that order) as one goes around the edge of the board, as opposed to a black/white/black/white (or white/black/white/black) order. For example, if the removed squares are the ones I've marked B1, B2, W1 and W2 in the following diagram, no such closed loop exists:

+--+--+--+--+--+--+--+--+

|xx| |xx| |B1| |xx| |

+--+--+--+--+--+--+--+--+

|W2|xx| |xx| |xx| |xx|

+--+--+--+--+--+--+--+--+

|xx| |xx| |xx| |xx| |

+--+--+--+--+--+--+--+--+

| |xx| |xx| |xx| |xx|

+--+--+--+--+--+--+--+--+

|xx| |xx| |xx| |xx| |

+--+--+--+--+--+--+--+--+

| |xx| |xx| |xx| |B2|

+--+--+--+--+--+--+--+--+

|xx| |xx| |xx| |xx| |

+--+--+--+--+--+--+--+--+

|W1|xx| |xx| |xx| |xx|

+--+--+--+--+--+--+--+--+

The reason why no such closed loop exists is simply that if one did, it would be divided into four segments by the removed squares and those segments would have to be between each combination of Bi and Wj, for i = 1,2 and j = 1,2. Now look at the segment between B1 and W1 and the segment between B2 and W2: because their endpoints are all on the edge of the board, they have to cross each other somewhere, i.e. to have at least one square in common - but that's incompatible with them being two of the segments into which the removed squares split a closed loop.

So what that says is that there are many other configurations of the removed squares besides the ones I described for which there is no 'closed loop' solution. That doesn't mean that I've found any extra configurations of the removed squares that are unsolvable, just that one may have to look beyond 'closed loop' solutions. For example, the above board has an easy 'open path' solution using the path that starts in the top left corner, goes left to right along the top row, right to left along the second row, left to right along the third row, etc, until it goes right to left along the bottom row and ends in the bottom left corner:

+-----+-----+--+-----+--+

| : :B1: : |

+--+--+--+--+--+-----+ |

|W2: : : : |

+..+--+--+--+--+--+--+--+

| : : : |

+-----+-----+-----+--+..+

| : : : |

+..+--+-----+-----+-----+

| : : : |

+--+--+--+--+--+--+--+..+

| : : : :B2|

| +-----+-----+-----+--+

| : : : : |

+--+-----+-----+-----+ |

|W1: : : : |

+--+-----+-----+-----+--+

As I said, it's a small point - not noticeably closer to a solution, just an indication of where one

won't find a solution, and just possibly a source of inspiration for further thoughts about the problem.

Gengulphus