Doubly mutilated chessboard problem: not the solution

On Friday I wrote about the mutilated chessboard problem.

I'll give the solution now. The reason this problem is usually phrased in terms of a "chessboard" is that a chessboard has its squares alternately colored white and black. (I'm going to call the colors white and black even if that's not actually what they are.) A chessboard has the same number of squares of each color, and any domino covers one white square and one black square. So if we remove two squares of the same color, such as the opposite corners, then tiling is impossible.

It turns out that if you remove any two squares of different color, leaving 31 squares of each color, the board can be tiled with dominoes. Drini gave the solution; draw any tour that goes through all the squares exactly once and finishes where it began. Removing two squares of opposite colors breaks this into two subpaths of even length, which are easily tiled.

As for the other problem I asked, when can you remove four squared and have there be a tiling: clearly we need to begin by removing two squares of each color. There is another necessary condition for there to be a tiling -- the squares removed can't block off a single corner square from the rest of the board. (You might worry that they could disconnect the board in some other way, but the only other way possible under the tiling constraints is that they disconnect a domino-shaped region.) But then the tour argument above doesn't work; in particular, a tour is broken up into four subpaths of even lengths if and only if the removed squares occur on it in the order black-white-black-white. Furthermore, it appears that there are ways to remove four squares from the four-by-four board such that the remaining twelve are tileable, but there is no tour that they break up into even-length subpaths. There aren't that many tours of the four-by-four board, so it's easy to check this by brute force with a simple program; in fact there are six according to Sloane's encyclopedia. (It says twelve there, but Sloane refers to directed tours.)

However, that cuts down the number of cases one has to deal with, and in the end it looks like a four-by-four chessboard, with four squares removed, is tileable if and only if the removed squares are of opposite color and do not include both of the squares adjacent to any corner.

My method (which I realize I haven't fully explained here; if anybody wants to seriously tackle this problem for some reason I'll be happy to explain in more detail) requires a bunch of nasty case analysis, though. And in the case of the 8-by-8 board there are millions of tours, so it doesn't generalize well.