肢解国际象棋盘问题
外观
![]() |
a | b | c | d | e | f | g | h | ||
8 | ![]() ![]() ![]() | 8 | |||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
a | b | c | d | e | f | g | h |
肢解国际象棋盘问题
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Domino_green.svg/75px-Domino_green.svg.png)
肢解国际象棋盘问题(英语:mutilated chessboard problem)属于平铺拼图问题,最早是由Max Black在1946年的《Critical Thinking》中提出。后来数学家所罗门·格伦布(1954年)及马丁·加德纳(在杂志《科学人》中的专栏《Mathematical Games》中)都有讨论到此问题。问题:“假设一个标准的8x8格国际象棋棋盘,移除对角的2个方块,余下62个方块。可不可以用31个2x1格骨牌来盖上余下方块呢?”
大部分讨论此问题的文献是在概念上说明此问题[1],计算机科学家约翰·麦卡锡认为这问题对于自动证明系统而言是很难的问题[2]。若使用归结系统,其解的困难度是指数等级[3]。
解法
[编辑]![肢解国际象棋盘问题的例子](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0f/Mutilated_chessboard_problem_example.jpg/220px-Mutilated_chessboard_problem_example.jpg)
肢解国际象棋盘问题是无解的。国际象棋盘上的2x1格骨牌一定会占据一个白色方格及一个黑色方格,因此被骨牌填满的位置,白色方格及黑色方格的个数相同。在肢解国际象棋盘问题中,若移除的二个是白色方格,有32个黑色方格及30个白色方格要填满,两者数量不同,无法用2x1格骨牌填满。若移除的二个是黑色方格,有30个黑色方格及32个白色方格要填满,还是无法用2x1格骨牌填满[4]。
高莫利定理
[编辑]只要国际象棋盘上移除二个同色的方格,相同的方式可以证明,移除方格后的棋盘无法用2x1格骨牌填满。不过若填除的是二个不同颜色的方格,一定可以用2x1格骨牌填满,这个结果称为高莫利定理(Gomory's theorem)[5],得名自数学家拉尔夫·爱德华·高莫利,他在1973年提出的证明[6]。高莫利定理可以用棋盘组成格子图的哈密顿图来证明,移去二个不同色的方格会将哈密顿图切成二部分,每个部分的黑色方格及白色方格都一样多,两部分都可以用2x1格骨牌填满。
参见
[编辑]引用来源
[编辑]- ^ Andrews, Peter B.; Bishop, Matthew, 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-Verlag, 1996,
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.
- ^ Arthan, R. D., The Mutilated Chessboard Theorem in Z (PDF), 2005 [2007-05-06], (原始内容 (PDF)存档于2017-12-14),
The mutilated chessboard theorem was proposed over 40 years ago by John McCarthy as a "tough nut to crack" for automated reasoning.
- ^ Alekhnovich, Michael, Mutilated chessboard problem is exponentially hard for resolution, Theoretical Computer Science, 2004, 310 (1-3): 513–525, doi:10.1016/S0304-3975(03)00395-5.
- ^ McCarthy, John, Creative Solutions to Problems, AISB Workshop on Artificial Intelligence and Creativity, 1999 [2007-04-27], (原始内容存档于2019-04-05)
- ^ Watkins, John J., Across the board: the mathematics of chessboard problems, Princeton University Press: 12–14, 2004, ISBN 978-0-691-11503-0.
- ^ According to Mendelsohn, the original publication is in Honsberger's book. Mendelsohn, N. S., Tiling with dominoes, The College Mathematics Journal (Mathematical Association of America), 2004, 35 (2): 115–120, JSTOR 4146865, doi:10.2307/4146865; Honsberger, R., Mathematical Gems I, Mathematical Association of America, 1973.
参考资料
[编辑]- Gamow, George; Stern, Marvin, Puzzle-Math, Viking Press, 1958, ISBN 978-0-333-08637-7
- Gardner, Martin, My Best Mathematical and Logic Puzzles, Dover, 1994, ISBN 0-486-28152-3
外部链接
[编辑]- Dominoes on a Checker Board by Jim Loy
- Dominoes on a Checker Board (页面存档备份,存于互联网档案馆)
- Gomory's Theorem (页面存档备份,存于互联网档案馆) by Jay Warendorff, The Wolfram Demonstrations Project.