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. Is it possible to place 31 dominoes of size 2×1 so as to cover all of these squares?
It is an
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.[1] Domino tilings also have a long history of practical use in pavement design and the arrangement of tatami flooring.[2]
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.[3][4] It was popularized in the 1950s through later discussions by Solomon W. Golomb (1954),[5] George Gamow and Marvin Stern (1958),[6] Claude Berge (1958),[4][7] and Martin Gardner in his Scientific American column "Mathematical Games" (1957).[8]
The use of the mutilated chessboard problem in automated reasoning stems from a proposal for its use by John McCarthy in 1964.[9][10] It has also been studied in cognitive science as a test case for creative insight,[11][12][13] Black's original motivation for the problem.[3] In the philosophy of mathematics, it has been examined in studies of the nature of mathematical proof.[14][15][16][17]
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.[8] The same idea shows that no domino tiling can exist whenever any two squares of the same color (not just the opposite corners) are removed from the chessboard.[18]
Several other proofs of impossibility have also been found. A proof by Shmuel Winograd 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.[19][20] 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.[21]
If two squares of opposite colors are removed, then the remaining board can always be tiled with dominoes; this result is Gomory's theorem,
Application to automated reasoning
Domino tiling problems on
In 1964,
Related problems
A similar problem asks if a
De Bruijn's theorem concerns the impossibility of packing certain cuboids into a larger cuboid. For instance, it is impossible, according to this theorem, to fill a 6 × 6 × 6 box with 1 × 2 × 4 cuboids. The proof uses a similar chessboard-coloring argument to the mutilated chessboard problem.[40]
References
- S2CID 6603662
- ^ a b Black, Max (1946), Critical Thinking: An Introduction To Logic And Scientific Method, Prentice Hall, pp. 157, 433
- ^ doi:10.1007/978-94-011-3488-0_13; see especially Section 13.1, "The mutilated chess board problem", pp. 271–274 Archived 2022-07-18 at the Wayback Machine.
- MR 0067055
- ISBN 978-0-333-08637-7
- ^ Berge, Claude (1958), Théorie des graphes et ses applications (in French), Dunod, p. 176
- ^ JSTOR 24941903; for solution, seeJSTOR 24940785. Reprinted in My Best Mathematical and Logic Puzzles (Dover Publications, 1994), pages 2 and 39.
- ^ a b McCarthy, John (July 17, 1964), A tough nut for proof procedures, Stanford AI Memo, vol. 16, archived from the original on 2021-05-16, retrieved 2022-07-18
- ^
- S2CID 54334455
- PMID 31446653
- S2CID 18225791
- MR 3404036
- from the original on 2022-07-19, retrieved 2022-07-19
- ^ a b Honsberger, R. (1973), "Gomory's theorem", Mathematical Gems I, Mathematical Association of America, pp. 65–67
- ^ McCarthy, John (1999), "Creative Solutions to Problems", AISB Workshop on Artificial Intelligence and Creativity, archived from the original on 2018-10-23, retrieved 2007-04-27
- ^ JSTOR 4146865. Mendelsohn credits the original publication of Gomory's theorem to Honsberger (1973).
- ^ S2CID 236397105
- ^ ISBN 978-0-691-11503-0
- ^ (PDF) from the original on 2022-08-08, retrieved 2022-07-18
- MR 1072815
- S2CID 6753523
- hdl:10138/333647, archived(PDF) from the original on 2022-07-18, retrieved 2022-07-18
- from the original on 2021-06-20, retrieved 2022-07-19
- from the original on 2022-07-18, retrieved 2022-07-18,
most treatments of the problem in the literature solve it in the conceptual sense, but do not actually provide proofs of the theorem in either of McCarthy's original formulations
- from the original on 2022-09-14, retrieved 2022-07-18
- MR 2020358
- (PDF) from the original on 2022-08-08, retrieved 2022-07-19
- MR 0587851
- S2CID 2459540
- S2CID 92989148
- (PDF) from the original on 2022-08-08, retrieved 2022-07-18
- from the original on 2022-07-18, retrieved 2022-07-18
- ^ Subramanian, Sakthi (1996), "An interactive solution to the mutilated checkerboard problem", MR 1406233
- S2CID 125950546
- arXiv:1706.09389
- MR 0234841
External links
- Gomory's Theorem by Jay Warendorff, The Wolfram Demonstrations Project.