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 blocksConstruct 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 blockAssume 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 blocksIf 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 blockThe 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 blockIn 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