The Mutilated Chessboard

Take a standard 8×8 chessboard and remove two opposite corner squares (say, the bottom-left and top-right), leaving 62 squares. Can you tile the remaining board exactly with 31 dominoes, where each domino covers two adjacent squares? There's no obvious way to brute-force this by trying layouts — but the answer, "no, it's impossible," can be proven in three sentences using the board's coloring.

The coloring argument

A chessboard's usual black-and-white coloring is the key. Every domino, wherever it's placed, covers one black square and one white square, because any two adjacent squares always have opposite colors. So any full domino tiling of any region must cover an equal number of black and white squares — that's not a guess, it's forced by how a domino sits on the grid.

Now count the colors on the mutilated board. A full 8×8 board has 32 black and 32 white squares. The two opposite corners removed (bottom-left and top-right) are always the same color as each other, because opposite corners of a chessboard always share a color. Removing two squares of the same color leaves 30 of one color and 32 of the other — an imbalance of 2. Since every domino must cover one of each color, 31 dominoes could cover at most 30 black and 30 white squares if matched to the smaller count, or would need 31 of each color to tile 62 squares evenly — but the board simply doesn't have 31 of each color available. The tiling is impossible, proven without placing a single domino.

Worked example: checking the corner colors directly

Label squares $(row, col)$ from $(1,1)$ to $(8,8)$, colored black if $row+col$ is even, white if odd. The bottom-left corner is $(1,1)$: $1+1=2$, even, black. The top-right corner is $(8,8)$: $8+8=16$, even, also black. Both removed squares are black, confirming the imbalance: $32 - 2 = 30$ black squares remain against $32$ white squares. Since $30 \ne 32$, no domino tiling can exist — 31 dominoes always split into 31 black-covering and 31 white-covering halves, requiring exactly 31 of each color, and this board has 30 and 32.

Worked example: when it is possible

Remove one black and one white square instead (any pair, not necessarily corners) — say $(1,1)$ (black) and $(1,2)$ (white). Now the board has 31 black and 31 white squares, matching what 31 dominoes need. It turns out this is always tileable in that case (a theorem, not just a lucky example): removing one square of each color from a chessboard always leaves a domino-tileable board, no matter which two squares you pick. The coloring argument only rules out tilings when the counts mismatch; when they match, a separate (also elegant) argument guarantees a tiling exists.

What this means in practice

Coloring and parity arguments like this are a standard interview move: when a combinatorial question asks "is X possible," look first for an invariant — some quantity every valid move or placement preserves — before trying to construct a solution. It's the same style of reasoning used to quickly rule out infeasible matching or allocation problems in scheduling and inventory puzzles: find what's conserved, then check whether the target state respects it.