Mutilated chessboard problem
Encyclopedia
The mutilated chessboard problem is a tiling puzzle
introduced by and discussed by Martin Gardner
in his Scientific American
column "Mathematical Games." The problem is as follows:
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.
exists whenever any two white squares are removed from the chessboard. However, if two squares of opposite colors are removed, then it is always possible to tile the remaining board with dominos; this result is called Gomory's theorem, and is named after mathematician Ralph E. Gomory
, whose proof was published in 1973. Gomory's theorem can be proven using a Hamiltonian cycle of the grid graph formed by the chessboard squares; the removal of two oppositely-colored squares splits this cycle into two paths with an even number of squares each, both of which are easy to partition into dominos.
Tiling puzzle
Tiling puzzles are puzzles involving two-dimensional packing problems in which a number of flat shapes have to be assembled into a larger given shape without overlaps . Some tiling puzzles ask you to dissect a given shape first and then rearrange the pieces into another shape...
introduced by and discussed by Martin Gardner
Martin Gardner
Martin Gardner was an American mathematics and science writer specializing in recreational mathematics, but with interests encompassing micromagic, stage magic, literature , philosophy, scientific skepticism, and religion...
in his Scientific American
Scientific American
Scientific American is a popular science magazine. It is notable for its long history of presenting science monthly to an educated but not necessarily scientific public, through its careful attention to the clarity of its text as well as the quality of its specially commissioned color graphics...
column "Mathematical Games." The problem is as follows:
Suppose a standard 8x8 chessboardChessboardA chessboard is the type of checkerboard used in the board game chess, and consists of 64 squares arranged in two alternating colors...
has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoesDominoesDominoes generally refers to the collective gaming pieces making up a domino set or to the subcategory of tile games played with domino pieces. In the area of mathematical tilings and polyominoes, the word domino often refers to any rectangle formed from joining two congruent squares edge to edge...
of size 2x1 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
John McCarthy (computer scientist)
John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...
proposed it as a hard problem for automated proof systems. In fact, its solution using the resolution
Resolution (logic)
In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation theorem-proving technique for sentences in propositional logic and first-order logic...
system of inference is exponentially hard.
Solution
The puzzle is impossible to complete. A domino placed on the chessboard will always cover one white square and one black square. Therefore a collection of dominoes placed on the board will cover equal numbers squares of each colour. If the two white corners are removed from the board then 30 white squares and 32 black squares remain to be covered by dominoes, so this is impossible. If the two black corners are removed instead, then 32 black squares and 30 white square remain, so it is again impossible.Gomory's theorem
The same impossibility proof shows that no domino tilingDomino tiling
A domino tiling of a region in the Euclidean plane is a tessellation of the region by dominos, shapes formed by the union of two unit squares meeting edge-to-edge...
exists whenever any two white squares are removed from the chessboard. However, if two squares of opposite colors are removed, then it is always possible to tile the remaining board with dominos; this result is called Gomory's theorem, and is named after mathematician Ralph E. Gomory
Ralph E. Gomory
Ralph Edward Gomory is an American applied mathematician and executive. Gomory worked at IBM as a researcher and later as an executive. During that time, his research led to the creation of new areas of applied mathematics....
, whose proof was published in 1973. Gomory's theorem can be proven using a Hamiltonian cycle of the grid graph formed by the chessboard squares; the removal of two oppositely-colored squares splits this cycle into two paths with an even number of squares each, both of which are easy to partition into dominos.
External links
- Dominoes on a Checker Board by Jim Loy
- Dominoes on a Checker Board
- Gomory's Theorem by Jay Warendorff, The Wolfram Demonstrations Project.