2 / 3 Finding The Observation

Two Corners One Colour

An 8×88 \times 8 board has the top-left and bottom-right squares removed. You must decide whether the remaining 62 squares can be covered exactly by 31 dominoes, each covering two edge-adjacent squares.

Both removed corners sit on dark squares

You have written a backtracking search and it has been running for a while. What should you do?

A

Stop the search, since the equal-colour argument shows that a board is tileable exactly when its two colour classes are equal in size, and here they are not.

B

Stop the search. Colour the board like a chessboard: every domino covers one dark and one light square, so 31 dominoes cover 31 of each. The two removed corners are the same colour, leaving 32 and 30, so no tiling exists.

C

Let it run. 62 is even, so the count works out, and a covering exists; the search just has to find it.

D

Stop the search. Removing the two corners disconnects the board, and a disconnected region cannot be tiled by dominoes.