Page 1 of 1

Dominoes

Posted: June 22nd, 2020, 12:55 pm
by cinelli
.-- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx|
-- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx| | | |
-- -- -- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx|
-- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx|
-- -- -- -- -- -- -- --

If two squares of opposite colours are removed from anywhere on an 8x8 chessboard, can the remaining portion of the board be completely covered with 1x2 dominoes? If so can you show how it can be done? If not prove it.

Cinelli

Re: Dominoes

Posted: June 22nd, 2020, 3:37 pm
by Gengulphus
cinelli wrote:
.-- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx|
-- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx| | | |
-- -- -- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx|
-- -- -- -- -- -- -- --
|xx| |xx| |xx| |xx| |
-- -- -- -- -- -- -- --
| |xx| |xx| |xx| |xx|
-- -- -- -- -- -- -- --

If two squares of opposite colours are removed from anywhere on an 8x8 chessboard, can the remaining portion of the board be completely covered with 1x2 dominoes? If so can you show how it can be done? If not prove it.

Spoiler...

Yes, it can always be completely covered with 1x2 dominoes. The two removed squares are in different rows, different columns or both. So I can split into four cases:

  1. the row containing the black removed square is above the row containing the white removed square;
  2. the row containing the black removed square is below the row containing the white removed square;
  3. the column containing the black removed square is to the left of the column containing the white removed square;
  4. the column containing the black removed square is to the right of the column containing the white removed square.
In case 1, consider the path from the top left corner to the bottom left corner that goes from left to right along the top row, then right to left along the 2nd row, then left to right along the 3rd row, etc, ending up going right to left along the bottom row. If I head along it laying down dominoes as I go, I will reach the black removed square before I reach the white removed square, so each domino covers a black square and then a white square until I reach the black removed square, then each domino covers a white square and then a black square until I reach the white removed square, then each domino covers a black square and then a white square until I end up in the bottom left corner, and I have successfully covered the board minus the removed squares with dominos.

In case 2, do likewise with the symmetrically placed path from the bottom right corner to the top right corner that starts by going right to left along the bottom row; in case 3, do likewise with the symmetrically placed path from the top left corner to the top right corner that starts by going top to bottom down the leftmost column; in case 4, do likewise with the symmetrically placed path from the bottom right corner to the bottom left corner that starts by going bottom to top up the rightmost column. (Note that if the two removed squares are neither in the same row nor the same column, both one of cases 1 and 2 and one of cases 3 and 4 apply, giving two different solutions - but that's no problem!)

Gengulphus

Re: Dominoes

Posted: June 25th, 2020, 11:41 am
by cinelli
Well solved Gengulphus. On reflection I think I should have worded the question differently: “Are there any choices of the two squares which make it impossible to cover the remaining squares with dominoes?” But you have shown that it is possible in all cases.

My solution is not very different from yours. 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.

Cinelli

Re: Dominoes

Posted: June 26th, 2020, 4:59 am
by Gengulphus
cinelli wrote:Well solved Gengulphus. On reflection I think I should have worded the question differently: “Are there any choices of the two squares which make it impossible to cover the remaining squares with dominoes?” But you have shown that it is possible in all cases.

My solution is not very different from yours. 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.

Yes, that's a slightly better solution than mine, as it doesn't involve splitting into cases at all, whereas mine involves splitting into four cases - albeit four cases that are equivalent under the square's symmetries.

By the way, here's a closed loop that has even better symmetry:

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

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?

Gengulphus

Re: Dominoes

Posted: June 26th, 2020, 9:57 am
by jfgw
Gengulphus wrote: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?


You need to also eliminate the case where three squares in a corner are isolated by removing (say) A3, B2 and C1 otherwise the puzzle is too easy :)


Julian F. G. W.

Re: Dominoes

Posted: June 26th, 2020, 10:30 am
by UncleEbenezer
jfgw wrote:You need to also eliminate the case where three squares in a corner are isolated by removing (say) A3, B2 and C1 otherwise the puzzle is too easy :)
Julian F. G. W.

Two of each colour already excludes that. But I agree the principle of making special cases detracts from the problem.

Perhaps Gengulphus' problem should be generalised to removing N white and N black squares, with the condition that remaining space be connected? We've dealt with N<=1, and at the other extreme if N>=30 the connected space to be dominoed is so constrained as to be trivial.

With intermediate N we can easily construct counterexamples. Thus with N=27 we cannot domino this remaining space:
.
o +
o + o + o +
o +


So, what values of N work, and why?

Supplementary: the condition of the space to be dominoed being connected is just the most obvious generalisation of Gengulphus' corners. But our counterexample shows it's not a sufficient condition. Can we express any reasonably elegant alternative condition?

Re: Dominoes

Posted: June 26th, 2020, 10:49 am
by UncleEbenezer
Should've added: since all the example needs is a matching pair of corners, it generalises obviously to all 4 <= N <= 28

Re: Dominoes

Posted: June 26th, 2020, 11:54 am
by UncleEbenezer
Bah. My mind was playing with symmetry.
We know N=0,1,30,31 work. And in addition to what I said, the simplest counterexample of all deals with N=29:
.
o
+ o + o
+


That just leaves N=2,3 unsolved. My mind wants to find symmetry with 30 and 29 respectively, but doesn't see a proof.

Re: Dominoes

Posted: June 26th, 2020, 1:53 pm
by Gengulphus
UncleEbenezer wrote:Bah. My mind was playing with symmetry.
We know N=0,1,30,31 work. And in addition to what I said, the simplest counterexample of all deals with N=29:
.
o
+ o + o
+


That just leaves N=2,3 unsolved. My mind wants to find symmetry with 30 and 29 respectively, but doesn't see a proof.

For N=3, just remove three squares of one colour to leave this configuration in the top left corner of the board:

+----------
| o ...
| o o o ...
| o o ...
| : : :
| : : :

and remove three squares of the other colour from elsewhere on the board so as to leave it connected - this can be done for any board of size 4x4 or more.

Gengulphus

Re: Dominoes

Posted: June 26th, 2020, 3:43 pm
by UncleEbenezer
Gengulphus wrote:For N=3, just remove three squares of one colour to leave this configuration in the top left corner of the board:

Damn, that's just another variant of my example - should've been obvious. :oops:

Also feels like the kind of symmetry I was looking for. Now if we had a symmetry property with N=30, your N=2 solution would follow.

Re: Dominoes

Posted: July 8th, 2020, 9:35 am
by Gengulphus
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

Re: Dominoes

Posted: July 11th, 2020, 12:18 pm
by Gengulphus
Using some of the general ideas in my last post, I've made some progress towards a solution to my follow-up puzzle:

Gengulphus wrote: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?

For brevity, I'll describe that configuration of the two squares next to a corner square having been removed and the corner square itself not having been removed as the 'forbidden configuration'.

The idea is to split into cases according to the number, and in some cases the colour, of the removed squares that are among the 28 edge and corner squares of the 8x8 board:

Case A) All four removed squares are edge or corner squares (and are necessarily two of each colour);
Case B) Three of the removed squares are edge or corner squares (and are necessarily two of one colour and one of the other colour);
Case C) Two of the removed squares are edge or corner squares and their colours differ;
Case D) Two of the removed squares are edge or corner squares and they're both the same colour;
Case E) One of the removed squares is an edge or corner square;
Case F) None of the removed squares is an edge or corner square.

I've solved cases A), B) and C) so far, and this post gives my solutions to them. Cases D), E) and F) are still undetermined and could be anything from reasonably easy to totally impossible (through I think both extremes are unlikely). I'll put some more thought in about them, but I think I've made enough progress and come up with enough general ideas about how to tackle the problem that others besides me may wish to explore them!

Case A) All four removed squares are edge or corner squares

Start by setting up a closed loop around the edge of the board, passing through the 28 edge and corner squares. The four removed squares split it up into four segments (or fewer if some of the removed squares are adjacent to each other). As one goes around that loop, there are two subcases: the colours of the removed squares alternate between black and white, or if we start at the right point, we'll see the two black removed squares and then the two white removed squares. In the first case, cinelli's argument earlier in the thread applies to the boundary loop, allowing us to tile it minus the removed squares with dominoes, and we can then complete that to a tiling of the whole board minus the removed squares by filling the entire central 6x6 array of squares with any of the numerous easy packings - e.g. six rows of three dominoes each.

That leaves the second subcase: as we go around the boundary loop from the right point, we see first the two black removed squares and then the two white removed squares. This is the case I looked at in my last post, in which I showed that it's not possible to produce any closed loop passing through the four removed squares in alternating colour order, but it might be possible to produce an open path covering the whole board and passing through the four removed squares in alternating colour order and which, when divided up into up to five segments by the removed squares, has all segments of even length. My aim here is to show that provided the forbidden configuration doesn't appear, this is always possible.

To prove this, consider the segment of the boundary cycle between the two black removed squares. It contains at least one white square and one fewer black squares than white squares. If we pick any one of those white squares, it splits the segment into an even number (possibly zero) of squares before it, the white square itself, and an even number (also possibly zero) of squares after it, and so we can tile all of the segment except the chosen white square with dominoes. That allows the white square we pick to be either a corner square or a (non-corner) edge square, but add the restriction that we don't choose it to be a corner square - this is always possible as long as the forbidden configuration doesn't appear, since the only white square in the boundary loop between the two black removed squares being a corner square is an occurrence of the forbidden configuration. Call the chosen white square the entry square, and similarly choose a non-corner black square in the segment of the boundary loop between the two white removed squares and call it the exit square. As an illustration of this, here's how the entry and exit squares might be chosen for the four removed squares in the example in my last post:

+--+--+--+--+--+--+--+--+
| | | | |B1|nn| | | B1 and B2 are the black removed squares
+--+--+--+--+--+--+--+--+ W1 and W2 are the white removed squares
|W2| | | NN is my chosen entry square
+--+ +--+ nn are other entry squares I could have chosen
|xx| |NN| XX is my chosen exit square
+--+ +--+ xx are other exit squares I could have chosen
| | | |
+--+ +--+
|xx| |nn|
+--+ +--+
| | |B2|
+--+ +--+
|XX| | |
+--+--+--+--+--+--+--+--+
|W1| | | | | | | |
+--+--+--+--+--+--+--+--+

The idea is then to construct an open path that starts in the boundary loop square immediately adjacent clockwise from the exit square, goes clockwise around the boundary loop until it gets to the entry square, then goes into the central 6x6 square area and fills it, ending up adjacent to the exit square, and then moves out into the exit square and goes anticlockwise around the boundary loop until it ends at the square immediately adjacent clockwise to the entry square. For my chosen entry and exit squares, this produces a path of the following form:

+--+--+--+--+--+--+--+--+
| : :B1: : |
+..+--+--+--+--+--+--+ +
|W2| | |
+..+ +..+..+
| | :entry|
+ + +..+--+
| | some filling | |
+..+ path between + +
| | entry domino | |
+ + and exit +..+
| | domino |B2|
+--+..+ +..+
|exit : | |
+..+--+--+--+--+--+--+ +
|W1: : : : |
+--+--+--+--+--+--+--+--+

Each of the five (or fewer) segments that the removed squares divide this path into is then of even length and so can be tiled with dominoes - in the diagram, they are the segments from the path's start just clockwise of 'exit' to W2, from W2 to B1, from B1 through 'entry', the central area and 'exit' to W1, from W1 to B2, and from B2 to its end just clockwise of 'entry'. This shows that (in the absence of the forbidden configuration) we can always tile the whole board minus the four removed squares with dominoes, provided we can always find the filling path it requires, from the entry square through the central area to the exit square. So we need to show that we can always find that filling path to complete the proof for case A.

To construct that filling path, consider the central area as being divided up into nine 2x2 squares in the obvious way, and suppose first that the entry square and the exit square are next to the same one of those 2x2 squares. The entry square and the exit square cannot be next to each other in the boundary loop, since they are separated from each other by a black removed square, a white removed square and zero or more non-removed squares on each side of the boundary loop, so the 2x2 square they are adjacent to must be in a corner of the central 6x6 area. Also taking into account the fact that the entry square and exit squares are of different colours, we must have the following configuration or one that is symmetrically equivalent to it, and the right hand diagram shows that we can produce a filling path that connects them:

+--+--+--+--+--+--+--+--+     +--+--+--+--+--+--+--+--+
|XX| | |XX| | XX marks two of the removed squares
+--+ +--+--+--+--+--+ + +--+ +--+--+--+--+--+ + (the others are also in the boundary loop)
|XX| | | |XX| | |
+--+ + + +--+--+--+--+--+--+ + +
| | | | | | | | |
+ + + + + + + + + + + + +
| | | | | | | | | | | | |
+ + + + + + + + + + + + +
| | | | | | | | | | | | |
+ + + + + + + + + + + + +
| | | | | | | | | | | | |
+ + + + + + + + + + + + +
| | | | | | | | | |
+ +--+--+--+--+--+--+ + + +--+--+--+--+--+--+ +
| | | |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+

Otherwise, the entry and exit squares are adjacent to different 2x2 squares of the nine 2x2 squares that we have divided the 6x6 central region up into, and we can always find a split of that region into a 2x6 rectangular block that contains one of the 2x2 squares they are adjacent to and a 4x6 rectangular block that contains the other. Taking account of the fact that the entry and exit squares are of different colours, that split can always be changed into one of the following by applying the obvious symmetries of rotation, reflection, interchanging the colours and swapping the roles of the entry and exit squares as needed:

.   **    **    **       
+--+--+--+--+--+--+
** | |
+ + ** = possible position of entry square
| | **
+ +--+--+--+--+--+
...........cut...........
+ +--+--+--+--+--+
| | ##
+ +
## | |
+ + ## = possible position of exit square
| | ##
+ +
## | |
+--+--+--+--+--+--+
## ## ##

In this case, one fills the 2x6 block with one of the following paths from the entry square to the gap I've left at the left end of the wall separating the two blocks:

.   **                                  **             
+..+--+--+--+--+--+ +--+--+ +--+--+--+
** : | | | |
+--+--+--+--+--+ + + + +--+--+--+ + ** = possible position of entry square
| | | | |
+ +--+--+--+--+--+ + +--+--+--+--+--+

**
+--+--+--+--+ +--+ +--+--+--+--+--+--+
| | | | | | | |
+ + + + +--+ + + + + + + + +
| | | | | | | | **
+ +--+--+--+--+--+ + +--+--+--+--+--+

and one similarly fills the 4x6 block with one of the following paths from that gap to the exit square:

.  +  +--+--+--+--+--+           +  +--+--+--+--+--+   
| | | | ## | |
+ + + + + + + +--+--+--+--+--+ +
| | | | | | | ## | | | |
+ + + + + + + + + + + + + + ## = possible position of exit square
| | | | | | | | | | | | | |
+ + + + + + + + + + + + + +
| | | | | | | |
+--+--+--+--+--+--+ +--+--+--+--+--+--+


+ +--+--+--+--+--+ + +--+--+--+--+--+
| | | |
+--+--+--+--+--+ + +--+--+--+--+--+ +
| | | |
+ +--+--+--+--+--+ + +--+--+--+--+--+
| | | | ## | |
+ + + + + + + +--+--+--+--+--+ +
| | | | ## : |
+--+--+--+--+--+--+ +..+--+--+--+--+--+
##

+ +--+--+--+--+--+ + +--+--+--+--+--+
| | | |
+--+--+--+--+--+ + +--+--+--+--+--+ +
| | | |
+ +--+--+--+--+--+ + +--+--+--+--+--+
| | | | | | |
+ + +--+--+--+ + + + + + +--+ +
| | | | | | |
+--+--+ +--+--+--+ +--+--+--+--+ +--+
## ##

Combining those two paths, one gets the required path from the entry square to the exit square that fills the central 6x6 area, completing the proof that in the absence of the forbidden configuration, the whole board minus the removed squares can always be tiled with dominos in case A.

Case B) Three of the removed squares are edge or corner squares

Two of the removed edge squares are one colour and the third is the other colour. Assume the first colour is black and the second white - the other case can obviously be dealt with completely analogously.

Consider the segment of the boundary loop that starts at one of the black removed squares and ends at the other and does not include the white removed square, including both of the removed black squares themselves. It consists of an odd number of squares, which is at least three. Each of those squares which is not a corner square has an edge in common with the central 6x6 area, and those common edges form a connected section of the boundary of that central 6x6 area. Furthermore, there can only be less than three edges in that connected section if there are only three squares in the boundary loop segment we're considering and one of them is a corner square. In that case, either the boundary loop segment we're considering consists of a corner square and the two adjacent edge squares, implying that we've got the forbidden configuration, or it consists of a corner square, one of the edge squares adjacent to it, and the next edge square along the same edge. So in that case and in the absence of the forbidden configuration, the connected section of the central area boundary that we're considering consists precisely of the two edges marked "==" in the left-hand diagram below or some symmetrically equivalent pair of edges. Otherwise, the connected section of the central area that we're considering contains at least three edges and must include the two edges marked "==" in at least one of the two diagrams or some symmetrically equivalent pair of edges:

+--+--+--+--+--+--+--+--+     +--+--+--+--+--+--+--+--+
| | | |
+ +==+==+--+--+--+--+ + + +--+--+==+==+--+--+ +
| | | | | | | |
+ + + + + + + +
| | | | | | | |
+ + + + + + + +
| | | | | | | |
+ + + + + + + +
| | | | | | | |
+ + + + + + + +
| | | | | | | |
+ + + + + + + +
| | | | | | | |
+ +--+--+--+--+--+--+ + + +--+--+--+--+--+--+ +
| | | |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+

Now consider the following two closed paths respectively:

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

In each case, our construction ensures that if we go around the boundary part of that closed path and then the central area, we encounter the removed squares in the order black, white, black in the boundary part and then white in the central area. So cinelli's argument applies to that closed path, allowing us to tile the whole board minus the removed squares with dominos.

Case C) Two of the removed squares are edge or corner squares and their colours differ

This case is very easy: make two closed loops, one of the edge squares and one of the central 6x6 squares, e.g.:

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

Each of those two closed loops contains one removed square of each colour, so is divided by those squares into two segments (or just one if the removed squares are adjacent along the loop). Each of the four (or fewer) segments is a path containing an even number of squares, and so can be tiled with dominoes just by traversing it from end to end, laying down dominoes as one proceeds, and the four resulting sets of dominoes tile the whole 8x8 square minus the removed squares. (I.e. this is basically just gluing together two copies of cinelli's argument.)

Gengulphus

Re: Dominoes

Posted: July 26th, 2020, 5:28 pm
by Gengulphus
Gengulphus wrote:Case A) All four removed squares are edge or corner squares (and are necessarily two of each colour);
Case B) Three of the removed squares are edge or corner squares (and are necessarily two of one colour and one of the other colour);
Case C) Two of the removed squares are edge or corner squares and their colours differ;
Case D) Two of the removed squares are edge or corner squares and they're both the same colour;
Case E) One of the removed squares is an edge or corner square;
Case F) None of the removed squares is an edge or corner square.

I've solved cases A), B) and C) so far, and this post gives my solutions to them. Cases D), E) and F) are still undetermined and could be anything from reasonably easy to totally impossible (through I think both extremes are unlikely). I'll put some more thought in about them, but I think I've made enough progress and come up with enough general ideas about how to tackle the problem that others besides me may wish to explore them!

On and off, I've done some more thinking about cases D), E) and F), and I believe I've seen my way to solving all of them - but it does involve a proliferation of subcases, and before I finished working them all out in full detail, another approach occurred to me that looked to involve fewer cases and to generalise more obviously to other even board sizes (*). So as a reminder of my follow-up puzzle, it is that we remove two black squares and two white squares from the 8x8 chess board:

+--+--+--+--+--+--+--+--+
|xx| |xx| |xx| |xx| |
+--+--+--+--+--+--+--+--+
| |xx| |xx| |xx| |xx|
+--+--+--+--+--+--+--+--+
|xx| |xx| |xx| |xx| |
+--+--+--+--+--+--+--+--+
| |xx| |xx| |xx| |xx|
+--+--+--+--+--+--+--+--+
|xx| |xx| |xx| |xx| |
+--+--+--+--+--+--+--+--+
| |xx| |xx| |xx| |xx|
+--+--+--+--+--+--+--+--+
|xx| |xx| |xx| |xx| |
+--+--+--+--+--+--+--+--+
| |xx| |xx| |xx| |xx|
+--+--+--+--+--+--+--+--+

Supposing that the 'forbidden configuration' does not occur, of the two squares horizontally and vertically adjacent to a corner square being removed without the corner square itself also being removed, can one always cover the remaining part of the board with 1x2 dominos?

The new approach is to consider the board to consist of a 4x4 array of 2x2 blocks of squares:

+--+--+--+--+--+--+--+--+
| : : : |
+ : : : +
| : : : |
+.....+.....+.....+.....+
| : : : |
+ : : : + +--+--+
| : : : | where each 2x2 block is |xx| |
+.....+.....+.....+.....+ +--+--+
| : : : | | |xx|
+ : : : + +--+--+
| : : : |
+.....+.....+.....+.....+
| : : : |
+ : : : +
| : : : |
+--+--+--+--+--+--+--+--+

There are the following cases for how the four removed squares are distributed between the blocks:

* [BBWW] One block contains all four removed squares.

* [BBW,W] One block contains both removed black squares and a removed white square; another contains the other removed white square.

* [BWW,B] One block contains both removed white squares and a removed black square; another contains the other removed black square.

* [BB,WW] One block contains both removed black squares and another contains both removed white squares.

* [BW,BW] Two blocks each contain a removed black square and a removed white square.

* [BB,W,W] One block contains both removed black squares and two others each contain a removed white square.

* [WW,B,B] One block contains both removed white squares and two others each contain a removed black square.

* [BW,B,W] One block contains a removed black square and a removed white square, another contains a removed black square, and yet another contains a removed white square.

* [B,B,W,W] Four blocks each contain one of the removed squares, two of them black and the other two white.

Split into those cases:


[BBWW]

This case is trivial to cover with dominoes - just cover each of the fifteen other 2x2 blocks with two dominoes.


[BBW,W] (and [BWW,B] by colour symmetry)

Construct a block-to-block path (with orthogonal steps only, not diagonal ones) from the block which has had both black squares and a white square removed to the one which has had a white square removed, with the constraints that (a) it doesn't visit any block more than once; (b) it must leave its starting block through one of the two sides adjacent to its remaining white square. For example, if the removed squares are the ones marked "XX" on the following board, then one of the possible paths is indicated in red:

+--+--+--+--+--+--+--+--+
| : |XX| : |
+ : +--+---->+ +
| : |XX|XX| | |
+.....+.....+--+--+..|..+
| : : : v |
+ : : +<----+ +
| : : | : |
+..+--+.....+..|..+.....+
| |XX| : v : |
+ +<----+<----+ : +
| : : : |
+.....+.....+.....+.....+
| : : : |
+ : : : +
| : : : |
+--+--+--+--+--+--+--+--+

This is possible unless the remaining white square in its starting block is in a corner of the entire board, so that it's impossible to take the first step along the path. In that case, the two removed black squares of the starting block and the unremoved white square form an example of the forbidden configuration. So on our supposition that that configuration isn't present, it's always possible.

For each of the arrowed edges in that path, place a domino consisting of the white square next to its tail end and the black square next to its head end, or equivalently, place a domino on its left-hand side facing along it if it's horizontal and its right-hand side facing along it if it's vertical:

+--+--+--+--+--+--+--+--+
| : |XX| | |
+ : +--+--+->+ +
| : |XX|XX| | |
+.....+.....+--+--+ +..+
| : : | v |
+ : +--+<-+--+ +
| : | | | |
+..+--+.....+ +--+--+..+
| |XX| | v : |
+ +<-+--+<-+--+ : +
| | | | : |
+..+--+--+--+--+..+.....+
| : : : |
+ : : : +
| : : : |
+--+--+--+--+--+--+--+--+

Note that no conflicts can occur between dominoes placed this way, as they cover a maximum of one white square and one black square in each block.

Now consider what squares are left both unremoved and uncovered in each block:

* In the starting block of the path, three squares are removed and the remaining square is covered, so no squares are left unremoved and uncovered.

* In the ending block of the path, a white square is removed and a black square is covered, so one square of each colour is left unremoved and uncovered. Those two squares necessarily form a domino.

* In any other blocks that the path visits, a black square is covered by the domino we've placed next to the arrowed edge entering the block, and a white square is covered by the domino we've placed next to the arrowed edge leaving the block. So again one square of each colour is left unremoved and uncovered, and those two squares necessarily form a domino.

* In any blocks the path does not visit, no squares are removed and no squares are covered. So all four squares are left unremoved and uncovered, and those four squares form two dominoes (in either of two different ways).

So it is easy to cover the remainder of the board with dominoes on a simple block-by-block basis.


[BB,WW]

Call the block with two removed black squares the starting block, and the block with two removed white squares the ending block. The aim will be to construct two block-to-block paths (each as in the previous case) from the starting block to the ending block such that:

* The two paths don't have any blocks in common other than the starting block and the ending block.

* The two paths' first steps out of the starting block are not adjacent to the same remaining white square in the block - i.e they aren't the combination of steps to the N (up) and the E (right), nor are they the combination of steps to the S (down) and W (left). The other four combinations (N,W), (N,S), (E,W) and (E,S) are all allowed.

* The two paths' final steps into the ending block are not adjacent to the same remaining black square in the block - i.e they aren't the combination of steps to the N and the W, nor are they the combination of steps to the S and E. The other four combinations (N,E), (N,S), (W,E) and (W,S) are all allowed.

Assuming I can construct those two paths, I can apply the same construction as in the previous case to both of those paths to cover them with dominoes, with no conflicts between the dominoes constructed by the two as a result of the three conditions, and then a similar argument to that in the previous case says that the unremoved and uncovered squares remaining are none in the starting and ending blocks, two of different colours (which can therefore be covered by a domino) in the other blocks visited by the paths, and all four (which can be covered by two dominoes, in either of two ways) in the blocks not visited by the paths.

So we need to show that two paths satisfying the three conditions can be constructed, provided the forbidden configuration doesn't appear - i.e. that the starting block is neither the top right block nor the bottom left block, and the ending block is neither the top left block nor the bottom right block. To do this, split into three cases according to whether the starting and ending blocks are boundary (either corner or edge) blocks of the board or interior blocks:

Both are boundary blocks

Construct one path to go clockwise around the boundary from the starting block to the ending block and the other to go anticlockwise around the boundary from the starting block to the ending block. Clearly the first condition is met, and the second and third are as well because the 'forbidden configuration does not appear' restrictions noted above ensure that the two paths' first and final steps are not in the forbidden direction combinations. Example:

+--+--+--+--+--+--+--+--+
|XX| : : : |
+--+---->+---->+---->+ +
| |XX| : : | |
+..|--+.....+.....+..|..+
| v : : : v |
+ + : : : + +
| | : : : | |
+..|..+.....+.....+..|..+
| v : : : v |
+ + : : : + +
| | : : : | |
+..|..+.....+..+--+..|..+
| v : : |XX| v |
+ +---->+---->+<----+ +
| : |XX| : |
+--+--+--+--+--+--+--+--+

One is a boundary block and the other an interior block

Assume that the starting block is the interior block and the ending block is the boundary block. If the starting block is not on the same row of blocks as the ending block, produce initial steps from the starting block going E for one path and W for the other block, extending both to the boundary to cover the entire row. The ending block then lies either above or below that row: if below, extend the two paths clockwise around the boundary from the E end and anticlockwise around the boundary from the W end to take them each to the ending block; if above, swap the roles of clockwise and anticlockwise in that to do the same. Example:

+--+--+--+--+--+--+--+--+
| : : : |
+ : : : +
| : : : |
+.....+.....+--+..+.....+
| : |XX| : |
+ +<----+<----+---->+ +
| | : : |XX| | |
+..|..+.....+..+--+..|..+
| v : : : v |
+ + : : : + +
| | : : : | |
+..|..+.....+..+--+..|..+
| v : : |XX| v |
+ +---->+---->+<----+ +
| : |XX| : |
+--+--+--+--+--+--+--+--+

If the starting block and the ending block are on the same row, they cannot be in the same column, in which case apply a similar construction with initial steps N for one path and S for the other, extending both to fill the entire column, then continuing clockwise and anticlockwise around the boundary into the side that contains the ending square.

If the starting block is the boundary block and the ending block is the interior block, construct the two paths similarly working from their ends towards their starts rather than from their starts to their ends.

Both are interior blocks

If the starting and ending blocks are not in the same row of blocks, construct initial steps of the two paths E and W from the starting block to fill its row, and final steps of the two paths E and W from the ending block to fill its row, then connect the two E ends with steps in the last column and the two W ends with steps in the first column. Example:

+--+--+--+--+--+--+--+--+
| : : : |
+ : : : +
| : : : |
+.....+.....+--+..+.....+
| : |XX| : |
+ +<----+<----+---->+ +
| | : : |XX| | |
+..|..+..+--+..+--+..|..+
| v : |XX| : v |
+ +---->+<----+<----+ +
| |XX| : : |
+.....+--+..+.....+.....+
| : : : |
+ : : : +
| : : : |
+--+--+--+--+--+--+--+--+

Again, if the starting and ending blocks are in the same row of blocks, then they cannot be in the same column, so proceed similarly with the initial and final steps N and S to fill their columns, and complete the paths by connecting them up on the first and last rows.


[BW,BW]

Another trivial case: being of opposite colours, the two removed squares in each of the 2x2 blocks containing them must make up a domino half of the block, allowing the other half to be covered by a domino. Cover each of the other fourteen 2x2 blocks with two dominoes to complete the covering.


[BB,W,W] (and [WW,B,B] by colour symmetry)

Call the block with two removed black squares the starting block, and each of the blocks with a removed white square an ending block. The aim will be to construct two block-to-block paths (as above) from the starting block to an ending block such that:

* The two paths don't have any blocks in common other than the starting block.

* The two paths' first steps out of the starting block are not adjacent to the same remaining white square in the block - i.e they aren't the combination of steps to the N (up) and the E (right), nor are they the combination of steps to the S (down) and W (left). The other four combinations (N,W), (N,S), (E,W) and (E,S) are all allowed.

Unlike in the [BB,WW] case above, there is no restriction on the directions of the final steps of the two paths.

The strategy we'll use is to construct the first path from the starting block to an ending block such that removing the set of blocks it uses leaves the remaining set of blocks connected and including both a block to which the second path can take its first step and the other ending block. Then we can construct the second path as consisting of that first step followed by steps within the remaining set of blocks, followed by constructing a set of dominoes alongside the two paths and filling the half-used and unused blocks with dominoes, as described above.

Now split into cases according to whether the starting block is a boundary block or an interior block:

The starting block is a boundary block

The starting block cannot be either the top right corner block or the bottom left corner block, as those would be forbidden configurations. If it's the top left corner block or the bottom right corner block, the two available directions for the paths' first steps are (E,S) or (N,W), both allowed combinations. And if it's an edge block, then either the combination (N,S) or the combination (E,W) is allowed. In other words, in the absence of forbidden combinations, we can decide that the first steps of the two paths will go clockwise and anticlockwise along the boundary.

If at least one of the ending blocks is a boundary block, choose the first path to be the shortest path going around the boundary (in either direction) from the starting block to an ending block (choosing arbitrarily in the event of ties). This cannot disconnect the remaining set of blocks, can go at most halfway around the boundary (so cannot interfere with the the first step we intend the second path to take) and cannot inadvertently go through the other ending block, since both going more than halfway around the boundary and going through the other ending block would imply the existence of a shorter path. So we've achieved the goal set out above for the first path, and can complete the construction of the domino tiling as described there.

If both of the ending blocks are interior blocks, extend the clockwise (or anticlockwise - arbitrary choice) first step zero or more further steps around the boundary until we're on the same row or column as at least one of the ending blocks, then extend along that row or column until we reach an ending block (stopping at the first ending block reached if both ending blocks are on that row or column). This again is certain to leave the remaining set of blocks connected and neither to visit the second ending block nor the intended first step of the second path. So again, we can complete the construction of the second path and then the domino tiling as described above.

The starting block is an interior block

In this case, make the first path go zero or more steps E or W to reach the same column as an ending block (zero steps if the ending block is already in the same column as the starting block), then zero or more steps N or S to reach an ending block (zero steps if the ending block is in the same row, so that the E/W steps have already reached it). As usual, choose to go to the ending block for which this requires fewer steps, or arbitrarily for ties, to ensure that the first path doesn't inadvertently visit the other ending block on the way to the chosen ending block. Again, this construction of the first path cannot disconnect the remaining set of blocks, and it cannot visit any of the other three blocks adjacent to the starting block, two of which are available for the second path to take its first step to. So we can complete the construction of the second path and then the domino tiling as above.


[BW,B,W]

This case is quite easy: consider the board minus the entirety of the block containing both a black removed square and a white removed square. It consists of fifteen 2x2 blocks and is still entirely connected. So we can construct a block-to-block path from the block containing just a black removed square to the block containing just a white removed square that stays entirely within those fifteen blocks. Apply the construction used quite a few times above to cover those fifteen blocks minus the two removed squares they contain with dominoes, and cover the unremoved part of the block containing both a black removed square and a white removed square with a domino to complete the covering of the entire board minus the removed squares.


[B,B,W,W]

Call each of the blocks with a removed black square a starting block, and each of the blocks with a removed white square an ending block. The aim will be to construct a block-to-block path (as above) from a starting block to an ending block, and another from the other starting block to the other ending block, such that the two paths don't have any blocks in common.

The strategy we'll use is to construct the first path from one starting block to one ending block such that removing the set of blocks it uses leaves the remaining set of blocks connected and including both the other starting block and the other ending block. Then we can construct the second path to go from the other starting block to the other ending block by steps within the remaining set of blocks, followed by constructing a set of dominoes alongside the two paths and filling the half-used and unused blocks with dominoes, as described above.

To construct such a first path, consider each of the four combinations of a starting block with an ending block. For each of them, construct a path from the starting block to the ending block as follows:

* If both the starting block and the ending block are boundary blocks, choose the shorter of the anticlockwise and clockwise paths around the boundary blocks from the starting block to the ending block, or an arbitrary one of them if they're of equal length.

* Otherwise, choose the path that goes E or W zero or more steps from the starting block to reach the ending block's column, then N or S zero or more steps along that column to reach the ending block itself.

Choose the shortest of the four resulting paths, again choosing arbitrarily between ties. This ensures that the chosen path doesn't visit the other starting block or the other ending block, and the construction of each of the four paths ensures that it doesn't disconnect the remaining set of blocks, so the chosen path is a suitable first path to allow the construction to be completed.


So the answer is that in the absence of the forbidden configuration, yes, the remaining part of the board can always be covered by 1x2 dominoes. This is of course something we were pretty certain of from just trying to find anything other than the forbidden combination that made constructing a domino covering impossible, but it's nice to confirm that there isn't some configuration of the removed squares we'd failed to consider!


(*) Odd board sizes are of course not possible, due to starting with the number of black squares one larger (or smaller) than the number of white squares, and so still having that property after removing equal numbers of both colours of square. Though one want to investigate the puzzle of removing one more (or fewer) black squares than white squares to leave equal numbers of both...


Gengulphus