Colouring and Tiling Arguments

Some puzzles ask whether a region can be fully covered by a given set of tiles, or whether a path can visit every square exactly once. These are hard to attack by trying layouts — there are too many. Colouring converts the geometric question into a counting question: paint the squares so that every tile, wherever placed, must cover a fixed number of each colour, then compare colour counts between what you have and what a covering would need.

Worked example: the mutilated chessboard

A standard 8x8 chessboard has two opposite corner squares removed, leaving 62 squares. Can this board be tiled exactly by 31 dominoes, each covering two adjacent squares?

Colour it. Use the board's own black-and-white chessboard colouring. There are 32 black squares and 32 white squares. Every domino, placed horizontally or vertically, covers exactly one black square and one white square — adjacent squares always differ in colour.

Count the removed corners. The two opposite corners of a chessboard are always the same colour (both light-squared corners, say). Removing them leaves 32 white squares and 30 black squares, or vice versa — an imbalance of 2.

Compare. Any tiling by 31 dominoes would cover exactly 31 black and 31 white squares — equal numbers. The mutilated board has unequal numbers. So no tiling exists, and the geometry never had to be examined at all.

The same trick handles a knight's-tour question (colour the board normally; a knight always moves from one colour to the other, so a tour visiting all 64 squares must alternate colours perfectly — useful for checking closed tours), and "can an L-tromino tiling cover a chessboard missing one square?" (a three-colouring in diagonal stripes, rather than the usual checkerboard, is the one that makes the counting argument go through).

Choosing the right colouring is the actual skill: the two-colour chessboard pattern isn't the only option, and a differently striped or diagonal colouring sometimes reveals an imbalance the standard one hides.