Mutilated chessboard problem
From Wikipedia, the free encyclopedia
 |
|||||||||
 |
 |
 |
|
|
|
|
|
 |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
||
|
|||||||||
The mutilated chessboard problem is a tiling puzzle introduced by Martin Gardner in his Scientific American column "Mathematical Games." The problem is as follows:
Suppose a standard 8x8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes 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.[1] John McCarthy proposed it[2] as a hard problem for automated proof systems.[3] In fact, its resolution is exponentially hard.[4]
Contents |
[edit] Solution
The puzzle is impossible. Any way you would place a domino would cover one white square and one black square. A group of 31 dominoes would cover 31 white and 31 black squares of an unmutilated chessboard, leaving one white and one black square uncovered. The directions had you remove diagonally opposite corner squares, and such squares are always either both black or both white.[5]
[edit] Notes
- ^ Peter B. Andrews and Matthew Bishop (June 1996). On Sets, Types, Fixed Points, and Checkerboards. Theorem Proving With Analytic Tableaux and Related Methods: 5th International Workshop, Tableaux '96, Terrasini, Palermo, Italy, 15-17th, 1996 : Proceedings (Lecture Notes in Computer Science). Springer Science+Business Media. Retrieved on 2007-05-06. “It should be noted that 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.”
- ^ Grzegorz Bancerek. The Mutilated Chessboard Problem checked by Mizar. Retrieved on 2007-05-06. “The problem presented by John McCarthy during his lecture "Heavy duty set theory"1 has been resolved here.”
- ^ R.D. Arthan (2005-08-09). The Mutilated Chessboard Theorem in Z (PDF). Retrieved on 2007-05-06. “The mutilated chessboard theorem was proposed over 40 years ago by John McCarthy as a “tough nut to crack” for automated reasoning.”
- ^ Michael Alekhnovich (January 2004). "Mutilated chessboard problem is exponentially hard for resolution". Theoretical Computer Science 310 (1-3): 513–525. doi:. ISSN 0304-3975.
- ^ McCarthy, John (1999). "Creative Solutions to Problems". AISB Workshop on Artificial Intelligence and Creativity. Retrieved on 2007-04-27.
[edit] See also
[edit] Additional reading
- Gardner, Martin (1994), My Best Mathematical and Logic Puzzles, Dover, ISBN 0486281523
