Sixty-Two Squares, Thirty-One Dominoes, and No Arrangement At All

Cut two diagonally opposite corners off a chessboard. Sixty-two squares are left. A domino covers two squares, and sixty-two is exactly thirty-one twos, so the question looks like a question about arrangement: which of the many ways of laying thirty-one dominoes on the wreckage actually works?

None of them. Not one arrangement out of the enormous number available, and the reason has nothing to do with being clever about placement. The board has a property that no collection of dominoes can ever have, and once you see which property it is, the search stops being difficult and starts being pointless.

The arithmetic is not the mistake

Sixty-four squares, minus two, is sixty-two. And $62 = 2 \times 31$is true. It is worth being careful here, because the temptation when writing this problem up is to strike that equation through as though it were the error. It is not. Every step of the counting is correct, and the false move comes one line later, in the silent inference from "the count divides evenly" to "so it must fit".

Divisibility of the area by two is necessary for a domino tiling. It is nowhere near sufficient, and the mutilated board is the standard demonstration of how far apart those two conditions can be. A region can have the right size, be connected, have no awkward narrow corridors, and still admit nothing.

Colour, written as arithmetic

Address a square by its column $i$ and row $j$, both running from $1$ to $8$, and give it the value

This is the checkerboard colouring, with the colours turned into numbers so that they can be added. Two squares are adjacent when exactly one of their coordinates differs by one, so adjacency flips the parity of $i + j$ and therefore flips the sign:

A domino always sits on two adjacent squares, whichever way round it lies, so it always contributes zero to the total. That single fact does all the work.

The census after the cuts

An intact board splits thirty-two against thirty-two, so its signed total is zero, which is consistent with it being tileable. Now look at the two corners that were removed. The corner at $(1,1)$ has $\sigma = (-1)^{2} = +1$, and the corner at $(n,n)$ has $\sigma = (-1)^{2n} = +1$ for every even $n$. Diagonally opposite corners of an even-sided board are always the same colour. That is the crux, and it is a statement about parity rather than about chessboards.

Thirty-one dominoes would cover thirty-one squares of each colour. The board offers thirty of one and thirty-two of the other. Since thirty is not thirty-one, no arrangement exists, and the impossibility is settled without ever placing a single piece.

The converse, which is genuinely harder

Equal colour counts are necessary. Are they enough? For an arbitrary region carved out of a board, no, and it is easy to build a counterexample by leaving an isolated square in a corner. But for the specific case of a full chessboard with one square of each colour removed, the answer is yes, and this is Gomory's theorem.

The proof is a pleasure. Take a closed tour that visits all sixty-four squares exactly once and returns to its start, stepping only between adjacent squares. Such a tour exists on any board with an even number of squares, and its squares alternate in colour as you walk it. Now delete one square of each colour. Those two deletions cut the cycle into two arcs, each of which has even length precisely because the deleted squares had opposite colours, and an arc of even length is tiled by walking along it two squares at a time. Either arc may be empty, which is fine.

Both directions of equation (4) were checked exhaustively rather than trusted. Of the pairs of squares one could remove, the 1024 pairs with opposite colours all leave a tileable board, and all 992 pairs with matching colours leave an untileable one. No exceptions on either side.

Counting instead of arguing

There is a real gap between "nobody has found an arrangement" and "no arrangement exists", and the colouring argument closes it. Still, an argument that proves impossibility deserves a second witness that shares none of its reasoning, so the tilings were also counted directly.

A bitmask dynamic programme sweeps the board column by column, tracking which cells of the frontier are already covered, and counts complete tilings without any notion of colour or parity anywhere in it. On the intact board it returns 12988816, the classical figure for the number of domino tilings of an eight by eight board. On the board minus two diagonally opposite corners it returns zero, and it returns zero on the other diagonal too. A count of zero from a procedure that has never heard of the checkerboard is independent evidence, not a restatement.

How far the argument reaches

Nothing above used the number eight except at the very end. The colouring, the domino cancellation and the corner parity all hold on any square board with an even side, so a $2m \times 2m$ board minus two diagonally opposite corners is untileable for every $m \ge 1$. It also does not matter which diagonal is cut, since both pairs of opposite corners share a colour.

The word "opposite" is doing real work, though. Two corners at the two ends of the same edge, say $(1,1)$ and $(1,8)$, have coordinate sums of different parity and therefore different colours. Remove those and the census stays balanced, the signed total stays zero, and by Gomory's theorem the remaining sixty-two squares tile perfectly well. The puzzle is entirely about which two squares leave, and not about how many.

The same technique, an invariant that every legal move preserves, settles a lot of tiling and colouring questions. When a placement problem resists, the move that usually works is to find a quantity the pieces cannot change, then check whether the board has the right value of it.

Sources and further reading

• The problem and its place in the literature — Mutilated chessboard problem
• The tilings counted in the enumeration channel — Domino tiling
• The parity of $i + j$ behind equations (1) and (2) — Parity
• The closed tour used to prove the converse — Hamiltonian path and cycle
• The general idea of an argument by invariant — Invariant

The impossibility was established twice over before publication, once by the colouring invariant in exact algebra and once by an exhaustive count of tilings that never mentions colour. The counting channel was itself controlled by reproducing 12988816 tilings on the intact board, and it was pushed further to confirm every one of the 1024 opposite-colour removals tileable and every one of the 992 same-colour removals untileable.