Mutilated chessboard problem

The mutilated chessboard problem is a <a href="/facts/Tiling_puzzle/c9JPlarv">tiling puzzle</a> posed by <a href="/facts/Max_Black/CpkI2S2d">Max Black</a> in 1946 that asks:

<blockquote>Suppose a standard 8×8 <a href="/facts/Chessboard/BmECnjVp">chessboard</a> (or <a href="/facts/Checkerboard/yIQaQoaM">checkerboard</a>) has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 <a href="/facts/Dominoes/31R2CTdB">dominoes</a> of size 2×1 so as to cover all of these squares?</blockquote>
It is an <a href="/facts/Impossible_puzzle/pflz6bPp">impossible puzzle</a>: there is no <a href="/facts/Domino_tiling/blw6bzyy">domino tiling</a> meeting these conditions. One proof of its impossibility uses the fact that, with the corners removed, the chessboard has 32 squares of one color and 30 of the other, but each domino must cover equally many squares of each color. More generally, if any two squares are removed from the chessboard, the rest can be tiled by dominoes if and only if the removed squares are of different colors. This problem has been used as a test case for <a href="/facts/Automated_reasoning/x5EdkKoU">automated reasoning</a>, <a href="/facts/Creativity/8sNGv9no">creativity</a>, and the <a href="/facts/Philosophy_of_mathematics/z7xBcdWA">philosophy of mathematics</a>.

Mutilated chessboard problem open-in-new

Mutilated chessboard problem