Mutilated chessboard problem

The mutilated chessboard problem is a tiling puzzle posed by Max Black in 1946 that asks: Suppose a standard 8×8 chessboard (or checkerboard) has two diagonally opposite corners removed, leaving 62 squares.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

The mutilated chessboard problem is a tiling puzzle posed by Max Black in 1946 that asks: Suppose a standard 8×8 chessboard (or checkerboard) 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? It is an impossible puzzle: there is no domino tiling 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 automated reasoning, creativity, and the philosophy of mathematics.

History

The mutilated chessboard problem is an instance of domino tiling of grids and polyominoes, also known as "dimer models", a general class of problems whose study in statistical mechanics dates to the work of Ralph H. Fowler and George Stanley Rushbrooke in 1937. Domino tilings also have a long history of practical use in pavement design and the arrangement of tatami flooring.

The mutilated chessboard problem itself was proposed by philosopher Max Black in his book Critical Thinking (1946), with a hint at the coloring-based solution to its impossibility. It was popularized in the 1950s through later discussions by Solomon W. Golomb (1954), George Gamow and Marvin Stern (1958), Claude Berge (1958), and Martin Gardner in his Scientific American column "Mathematical Games" (1957).

The use of the mutilated chessboard problem in automated reasoning stems from a proposal for its use by John McCarthy in 1964. It has also been studied in cognitive science as a test case for creative insight, Black's original motivation for the problem. In the philosophy of mathematics, it has been examined in studies of the nature of mathematical proof.

Application to automated reasoning

Domino tiling problems on polyominoes, such as the mutilated chessboard problem, can be solved in polynomial time, either by converting them into problems in group theory, or as instances of bipartite matching. In the latter formulation, one obtains a bipartite graph with a vertex for each available chessboard square and an edge for every pair of adjacent squares; the problem is to find a system of edges that touches each vertex exactly once.

As in the coloring-based proof of the impossibility of the mutilated chessboard problem, the fact that this graph has more vertices of one color than the other implies that it fails the necessary conditions of Hall's marriage theorem, so no matching exists. The problem can also be solved by formulating it as a constraint satisfaction problem, and applying semidefinite programming to a relaxation.

In 1964, John McCarthy proposed the mutilated chessboard as a hard problem for automated proof systems, formulating it in first-order logic and asking for a system that can automatically determine the unsolvability of this formulation. Most considerations of this problem provide solutions "in the conceptual sense" that do not apply to McCarthy's logic formulation of the problem.

Despite the existence of general methods such as those based on graph matching, it is exponentially hard for resolution to solve McCarthy's logical formulation of the problem, highlighting the need for methods in artificial intelligence that can automatically change to a more suitable problem representation and for knowledge representation systems that can manage the equivalences between different representations. Short proofs are possible using resolution with additional variables, or in stronger proof systems allowing the expression of avoidable tiling patterns that can prune the search space.

Higher-level proof assistants are capable of handling the coloring-based impossibility proof directly; these include Isabelle, the Mizar system, and Nqthm.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1356319291 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

15 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.