🔗 Mutilated chessboard problem

🔗 Chess

The mutilated chessboard problem is a tiling puzzle proposed by philosopher Max Black in his book Critical Thinking (1946). It was later discussed by Solomon W. Golomb (1954), Gamow & Stern (1958) and by Martin Gardner in his Scientific American column "Mathematical Games". The problem is as follows:

Suppose a standard 8×8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2×1 so as to cover all of these squares?

Most considerations of this problem in literature provide solutions "in the conceptual sense" without proofs. John McCarthy proposed it as a hard problem for automated proof systems. In fact, its solution using the resolution system of inference is exponentially hard.