肢解国际象棋盘问题
肢解国际象棋盘问题（英语：mutilated chessboard problem）属于平铺拼图问题，最早是由Max Black在1946年的《Critical Thinking》中提出。后来数学家所罗门·格伦布（1954年）及马丁·加德纳（在杂志《科学人》中的专栏《Mathematical Games》中）都有讨论到此问题。问题：“假设一个标准的8x8格国际象棋棋盘，移除对角的2个方块，馀下62个方块。可不可以用31个2x1格骨牌来盖上馀下方块呢？”
| 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 | ||
肢解国际象棋盘问题
大部份讨论此问题的文献是在概念上说明此问题[1]，电脑科学家约翰·麦卡锡认为这问题对于自动证明系统而言是很难的问题[2]。若使用归结系统，其解的困难度是指数等级[3]。
解法
肢解国际象棋盘问题是无解的。国际象棋盘上的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.