Gomory's Theorem
   HOME

TheInfoList



OR:

The mutilated chessboard problem is a
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 (and often without gaps). Some tiling puzzles ask players to dissect a give ...
posed by
Max Black Max Black (February 24, 1909 – August 27, 1988) was a Russian-born British-American philosopher who was a leading figure in analytic philosophy in the years after World War II. He made contributions to the philosophy of language, the philosoph ...
in 1946 that asks:
Suppose a standard 8×8
chessboard A chessboard is a game board used to play chess. It consists of 64 squares, 8 rows by 8 columns, on which the chess pieces are placed. It is square in shape and uses two colours of squares, one light and one dark, in a chequered pattern. During p ...
(or
checkerboard A checkerboard (American English) or chequerboard (British English) is a game board of check (pattern), checkered pattern on which checkers (also known as English draughts) is played. Most commonly, it consists of 64 squares (8×8) of alternating ...
) has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31
dominoes Dominoes is a family of tile-based games played with gaming pieces. Each domino is a rectangular tile, usually with a line dividing its face into two square ''ends''. Each end is marked with a number of spots (also called ''Pip (counting), pips ...
of size 2×1 so as to cover all of these squares?
It is an impossible puzzle: there is no
domino tiling In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by domino (mathematics), dominoes, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a matching (graph theory), ...
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 In computer science, in particular in knowledge representation and reasoning and metalogic, the area of automated reasoning is dedicated to understanding different aspects of reasoning. The study of automated reasoning helps produce computer progr ...
,
creativity Creativity is the ability to form novel and valuable Idea, ideas or works using one's imagination. Products of creativity may be intangible (e.g. an idea, scientific theory, Literature, literary work, musical composition, or joke), or a physica ...
, and the
philosophy of mathematics Philosophy of mathematics is the branch of philosophy that deals with the nature of mathematics and its relationship to other areas of philosophy, particularly epistemology and metaphysics. Central questions posed include whether or not mathem ...
.


History

The mutilated chessboard problem is an instance of
domino tiling In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by domino (mathematics), dominoes, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a matching (graph theory), ...
of grids and
polyomino A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling. Polyominoes have been used in popu ...
es, also known as "dimer models", a general class of problems whose study in
statistical mechanics In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. Sometimes called statistical physics or statistical thermodynamics, its applicati ...
dates to the work of
Ralph H. Fowler Sir Ralph Howard Fowler (17 January 1889 – 28 July 1944) was an English physicist, physical chemist, and astronomer. Education Ralph H. Fowler was born at Roydon, Essex, Roydon, Essex, on 17 January 1889 to Howard Fowler, from Burnham-on-Sea, ...
and George Stanley Rushbrooke in 1937. Domino tilings also have a long history of practical use in pavement design and the arrangement of
tatami are soft mats used as flooring material in traditional Japanese-style rooms. They are made in standard sizes, twice as long as wide, about , depending on the region. In martial arts, tatami are used for training in a dojo and for competition. ...
flooring. The mutilated chessboard problem itself was proposed by philosopher
Max Black Max Black (February 24, 1909 – August 27, 1988) was a Russian-born British-American philosopher who was a leading figure in analytic philosophy in the years after World War II. He made contributions to the philosophy of language, the philosoph ...
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 Solomon Wolf Golomb ( ; May 30, 1932 – May 1, 2016) was an American mathematician, engineer, and professor of electrical engineering at the University of Southern California, best known for his works on mathematical games. He most notably inven ...
(1954),
George Gamow George Gamow (sometimes Gammoff; born Georgiy Antonovich Gamov; ; 4 March 1904 – 19 August 1968) was a Soviet and American polymath, theoretical physicist and cosmologist. He was an early advocate and developer of Georges Lemaître's Big Ba ...
and Marvin Stern (1958),
Claude Berge Claude Jacques Berge (5 June 1926 – 30 June 2002) was a French mathematician, recognized as one of the modern founders of combinatorics and graph theory. Biography and professional history Claude Berge's parents were André Berge and Genevièv ...
(1958), and
Martin Gardner Martin Gardner (October 21, 1914May 22, 2010) was an American popular mathematics and popular science writer with interests also encompassing magic, scientific skepticism, micromagic, philosophy, religion, and literatureespecially the writin ...
in his ''
Scientific American ''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it, with more than 150 Nobel Pri ...
'' column "
Mathematical Games A mathematical game is a game whose rules, strategies, and outcomes are defined by clear mathematics, mathematical parameters. Often, such games have simple rules and match procedures, such as tic-tac-toe and dots and boxes. Generally, mathemati ...
" (1957). The use of the mutilated chessboard problem in
automated reasoning In computer science, in particular in knowledge representation and reasoning and metalogic, the area of automated reasoning is dedicated to understanding different aspects of reasoning. The study of automated reasoning helps produce computer progr ...
stems from a proposal for its use by
John McCarthy John McCarthy may refer to: Government * John George MacCarthy (1829–1892), Member of Parliament for Mallow constituency, 1874–1880 * John McCarthy (Irish politician) (1862–1893), Member of Parliament for the Mid Tipperary constituency, ...
in 1964. It has also been studied in
cognitive science Cognitive science is the interdisciplinary, scientific study of the mind and its processes. It examines the nature, the tasks, and the functions of cognition (in a broad sense). Mental faculties of concern to cognitive scientists include percep ...
as a test case for creative insight, Black's original motivation for the problem. In the
philosophy of mathematics Philosophy of mathematics is the branch of philosophy that deals with the nature of mathematics and its relationship to other areas of philosophy, particularly epistemology and metaphysics. Central questions posed include whether or not mathem ...
, it has been examined in studies of the nature of
mathematical proof A mathematical proof is a deductive reasoning, deductive Argument-deduction-proof distinctions, argument for a Proposition, mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use othe ...
.


Solution

The puzzle is impossible to complete. A domino placed on the chessboard will always cover one white square and one black square. Therefore, any collection of dominoes placed on the board will cover equal numbers of squares of each color. But any two opposite squares have the same color: both black or both white. If they are removed, there will be fewer squares of that color and more of the other color, making the numbers of squares of each color unequal and the board impossible to cover. The same idea shows that no
domino tiling In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by domino (mathematics), dominoes, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a matching (graph theory), ...
can exist whenever any two squares of the same color (not just the opposite corners) are removed from the chessboard. Several other proofs of impossibility have also been found. A proof by
Shmuel Winograd __NOTOC__ Shmuel Winograd (; January 4, 1936 – March 25, 2019) was an Israeli-American computer scientist, noted for his contributions to computational complexity. He has proved several major results regarding the computational aspects of arit ...
starts with induction. In a given tiling of the board, if a row has an odd number of squares not covered by vertical dominoes from the previous row, then an odd number of vertical dominoes must extend into the next row. The first row trivially has an odd number of squares (namely, 7) not covered by dominoes of the previous row. Thus, by induction, each of the seven pairs of consecutive rows houses an odd number of vertical dominoes, producing an odd total number. By the same reasoning, the total number of horizontal dominoes must also be odd. As the sum of two odd numbers, the total number of dominoes—vertical and horizontal—must be even. But to cover the mutilated chessboard, 31 dominoes are needed, an odd number. Another method counts the edges of each color around the boundary of the mutilated chessboard. Their numbers must be equal in any tileable region of the chessboard, because each domino has three edges of each color, and each internal edge between dominoes pairs off boundaries of opposite colors. However, the mutilated chessboard has more edges of one color than the other. If two squares of opposite colors are removed, then the remaining board can always be tiled with dominoes; this result is Gomory's theorem, after mathematician Ralph E. Gomory, whose proof was published in 1973. Gomory's theorem can be proven using a
Hamiltonian cycle In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or ...
of the
grid graph In graph theory, a lattice graph, mesh graph, or grid graph is a Graph (discrete mathematics), graph whose graph drawing, drawing, Embedding, embedded in some Euclidean space , forms a regular tiling. This implies that the group (mathematics), g ...
formed by the chessboard squares. The removal of any two oppositely colored squares splits this cycle into two paths with an even number of squares each. Both of these paths are easy to partition into dominoes by following them. Gomory's theorem is specific to the removal of only one square of each color. Removing larger numbers of squares, with equal numbers of each color, can result in a region that has no domino tiling, but for which coloring-based impossibility proofs do not work.


Application to automated reasoning

Domino tiling problems on
polyomino A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling. Polyominoes have been used in popu ...
es, such as the mutilated chessboard problem, can be solved in
polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
, either by converting them into problems in
group theory In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ( ...
, or as instances of bipartite matching. In the latter formulation, one obtains a
bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
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 In mathematics, Hall's marriage theorem, proved by , is a theorem with two equivalent formulations. In each case, the theorem gives a necessity and sufficiency, necessary and sufficient condition for an object to exist: * The Combinatorics, combina ...
, so no matching exists. The problem can also be solved by formulating it as a
constraint satisfaction problem Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite const ...
, and applying
semidefinite programming Semidefinite programming (SDP) is a subfield of mathematical programming concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize) over the intersection of the cone of po ...
to a relaxation. In 1964,
John McCarthy John McCarthy may refer to: Government * John George MacCarthy (1829–1892), Member of Parliament for Mallow constituency, 1874–1880 * John McCarthy (Irish politician) (1862–1893), Member of Parliament for the Mid Tipperary constituency, ...
proposed the mutilated chessboard as a hard problem for automated proof systems, formulating it in
first-order logic First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over ...
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 Artificial intelligence (AI) is the capability of computer, computational systems to perform tasks typically associated with human intelligence, such as learning, reasoning, problem-solving, perception, and decision-making. It is a field of re ...
that can automatically change to a more suitable problem representation and for
knowledge representation Knowledge representation (KR) aims to model information in a structured manner to formally represent it as knowledge in knowledge-based systems whereas knowledge representation and reasoning (KRR, KR&R, or KR²) also aims to understand, reason, and ...
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 assistant In computer science and mathematical logic, a proof assistant or interactive theorem prover is a software tool to assist with the development of formal proofs by human–machine collaboration. This involves some sort of interactive proof edi ...
s are capable of handling the coloring-based impossibility proof directly; these include
Isabelle Isabel is a female name of Iberian origin. Isabelle is a name that is similar, but it is of French origin. It originates as the medieval Spanish form of '' Elisabeth'' (ultimately Hebrew ''Elisheba''). Arising in the 12th century, it became popul ...
, the
Mizar system The Mizar system consists of a formal language for writing mathematical definitions and proofs, a proof assistant, which is able to mechanically check proofs written in this language, and a library of formalized mathematics, which can be used ...
, and Nqthm.


Related problems

A similar problem asks if a wazir starting at a corner square of an ordinary chessboard can visit every square exactly once, and finish at the opposite corner square. The wazir is a
fairy chess piece A fairy chess piece, variant chess piece, unorthodox chess piece, or heterodox chess piece is a chess piece not used in conventional chess but incorporated into certain chess variants and some unorthodox chess problems, known as fairy chess. Compar ...
that can move only one square vertically or horizontally (not diagonally). Using similar reasoning to the mutilated chessboard problem's classic solution, this wazir's tour does not exist. For example, if the initial square is white, as each move alternates between black and white squares, the final square of any complete tour is black. However, the opposite corner square is white. This sort of tour of a chessboard also forms the basis of a type of puzzle called
Numbrix Hidato (, originating from the Hebrew word ''Hida'' = Riddle), also known as "Hidoku", is a logic puzzle game invented by Dr. Gyora M. Benedek, an Israeli mathematician. The goal of Hidato is to fill the grid with consecutive numbers that connec ...
, which asks for a tour in which the positions of certain squares match given clues. The impossibility of a corner-to-corner tour shows the impossibility of a Numbrix puzzle with the clues 1 in one corner and 64 in the opposite corner.
De Bruijn's theorem In a 1969 paper, Dutch mathematician Nicolaas Govert de Bruijn proved several results about packing congruent rectangular bricks (of any dimension) into larger rectangular boxes, in such a way that no space is left over. One of these results is no ...
concerns the impossibility of packing certain
cuboid In geometry, a cuboid is a hexahedron with quadrilateral faces, meaning it is a polyhedron with six Face (geometry), faces; it has eight Vertex (geometry), vertices and twelve Edge (geometry), edges. A ''rectangular cuboid'' (sometimes also calle ...
s into a larger cuboid. For instance, it is impossible, according to this theorem, to fill a box with cuboids. The proof uses a similar chessboard-coloring argument to the mutilated chessboard problem.


References


External links

{{Commons category, Mutilated chessboard problem
Gomory's Theorem
by Jay Warendorff,
The Wolfram Demonstrations Project The Wolfram Demonstrations Project is an open-source collection of interactive programmes called Demonstrations. It is hosted by Wolfram Research. At its launch, it contained 1300 demonstrations but has grown to over 10,000. The site won a Pa ...
. Tiling puzzles Logic puzzles Mathematical chess problems Unsolvable puzzles