Assume without loss of generality that the two squares to be removed are in different rows. (Otherwise turn the board 90°).
First cover the board in horizontal dominoes, and connect the two squares by a zig-zag line like this:
which follows the rule that if the line goes through one end of a domino, it immediately connects to another end. (The requirement that the two squares have different colors ensure that this will be true of the end of the path if only we start out in the right direction for this to hold at the beginning). Now you can flip dominoes along the zig-zag line to produce a covering that avoids the two squares.
With a bit of (easy) special-casing for the same-row case, this strategy can be extended to any size board as long as one of the side lengths is even and the other is $\ge 2$.
It is true! An even polyomino with one hole is tileable by dominoes.
The proof below has a few sketchy elements; a proof without those will be nice.
Proof. For this proof to work, we will manipulate the border (either the outside or inside border) to give a new polyomino with a hole, and we will consider regions where borders overlap also valid polyominoes, and they are even if the corners are black as with the regular definition. Here are some examples of such polyominoes (the outside border has been slightly displaced where it coincides with the inside border).
Here, tileable means tileable by dominoes.
A ring is a polyomino where each cell has exactly two borders. All rings are tileable.
A peak is a cell with exactly one neighbor. In an even polyomino, all peaks must be black (otherwise there are white corners). Also, all black peaks must be attached to a white cell with exactly two neighbors. Therefor, in an even polyomino, if we move the border to exclude the peak and it's neighboring cell, we are still left with an even polyomino.
An example of this manipulation:
- A $2 \times 2$ square can be of two types. Type I has a black square in the top right, a Type II square has a black square in the top left. If a Type I square occurs in a corner of the polyomino, we can move the border to exclude it, and keep the polyomino even.
An example of this manipulation:
- All convex corners of a even polyomino are one of these four types:
(This part is a bit sketchy; it requires considering many cases.)
- If we perform the manipulations in 2 and 3 until we cannot, we are only left with the following types of convex corners:
- A figure with only type 3 and 4 convex corners and one hole cannot contain a $2\times2$ subfigure.
Suppose there is such a square. Find the largest connected set of cells that contains this square such that each cell is part of a $2\times 2$ subfigure. This set of cells must have at least four convex corners (as do all rectilinear figures). For these corners to not be corners of the entire figure, each needs to be "covered" by a "strand" (the picture below shows a possibility.) These strands must either result in peaks, or they must connect in pairs. If they connect in pairs, there are two holes, and this is impossible. Therefor, there cannot be any $2\times 2$ subfigure.
In this^ image, there is a $2 \times 2$ square, contained in a $3\times 3$ square where each corner is covered by a white cell that stars the strand. In this example, the strands connect in pairs, leading to two holes.
- We cannot have any X or T junctions in a figure with no $2\times2$ subfigures, no peaks, and one hole.
Suppose we have an X junction. Each of the four connectors must eventually lead to a peak, or pairs of them must join. In the latter case, we have two holes, which is impossible. Therefor there are no X junctions.
Suppose we have a T-junction. Each of the three connectors must either lead to a peak, or they must join other connectors. We can only join up if we have at least another T junction, in which case we will have at least have two holes, which is impossible. Therefor there are no T junctions.
- This means we either have a ring, or a polyomino with no area (thus the inner and outer border coincide completely).
(This is also sketchy, and require cases to make sure we cannot have other possibilities.)
- This procedure shows we can partition any even polyomino with one hole into a set with $dominoes$, $2\times2$ squares, and either a ring or empty polyomino. All the elements of this partition are tileable, and therefor, so is the whole figure.
Some remarks:
- The double border definition is necessary to deal with polyominoes such as this below. If we did not have that, removing a $2\times 2$ corner would not leave an even polyomino. (It would be nice to find a proof that does not require this trick.)
- An algorithm follows immediately from the border manipulations.
Best Answer
Draw a hamiltonian cycle on the chessboard. Any cycle will do, and the following one suffices:
Pick (any) one square and call it $s_0$. Number the following squares in the hamiltonian cycle $s_1, s_2,\ldots s_{63}$:
Note that the even $s_i$ are all one color (say pink) and the odd $s_i$ are the other color (say brown). So far this is all very easy.
Now suppose two squares of the opposite colors have been deleted; for example:
The cycle has been cut into two paths, both of which have even length. Such a path is easily covered with dominoes: say one path is $s_k, s_{k+1}, \ldots, s_{k+2j+1}$, where the subscripts are understood mod 64. Then the dominoes easily go onto $(s_k, s_{k+1}), (s_{k+2}, s_{k+3}), \ldots (s_{k+2j}, s_{k+2j+1})$. Similarly the other path is tiled by $(s_{k+2j+3}, s_{k+2j+4}), \ldots, (s_{k-3}, s_{k-2})$.
This theorem and the proof I have given appear on pages 111–112 of Solomon W. Golomb Polyominoes (revised ed.), Princeton University Press, 1994. The proof is attributed to Ralph Gomory.