肢解国际象棋盘问题

肢解国际象棋盘问题(英语:mutilated chessboard problem)属于平铺拼图问题英语Tiling puzzle,最早是由Max Black英语Max Black在1946年的《Critical Thinking》中提出。后来数学家所罗门·格伦布(1954年)及马丁·加德纳(在杂志《科学人》中的专栏《Mathematical Games》中)都有讨论到此问题。问题:“假设一个标准的8x8格国际象棋棋盘,移除对角的2个方块,馀下62个方块。可不可以用31个2x1格骨牌来盖上馀下方块呢?”

abcdefgh
8
h8 black cross
a1 black cross
8
77
66
55
44
33
22
11
abcdefgh
肢解国际象棋盘问题
一个二格骨牌

大部份讨论此问题的文献是在概念上说明此问题[1],电脑科学家约翰·麦卡锡认为这问题对于自动证明系统而言是很难的问题[2]。若使用归结系统,其解的困难度是指数等级[3]

解法

 
肢解国际象棋盘问题的例子,移除了左上和右下的白格,棋盘中间二个黑色的方格无法用骨牌填满,但不容易注意到

肢解国际象棋盘问题是无解的。国际象棋盘上的2x1格骨牌一定会占据一个白色方格及一个黑色方格,因此被骨牌填满的位置,白色方格及黑色方格的个数相同。在肢解国际象棋盘问题中,若移除的二个是白色方格,有32个黑色方格及30个白色方格要填满,两者数量不同,无法用2x1格骨牌填满。若移除的二个是黑色方格,有30个黑色方格及32个白色方格要填满,还是无法用2x1格骨牌填满[4]

高莫利定理

只要国际象棋盘上移除二个同色的方格,相同的方式可以证明,移除方格后的棋盘无法用2x1格骨牌填满。不过若填除的是二个不同颜色的方格,一定可以用2x1格骨牌填满,这个结果称为高莫利定理(Gomory's theorem)[5],得名自数学家拉尔夫·爱德华·高莫利英语Ralph E. Gomory,他在1973年提出的证明[6]。高莫利定理可以用棋盘组成格子图英语grid graph哈密顿图来证明,移去二个不同色的方格会将哈密顿图切成二部份,每个部份的黑色方格及白色方格都一样多,两部份都可以用2x1格骨牌填满。

参见

引用来源

  1. ^ 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. 
  2. ^ 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. 
  3. ^ 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 .
  4. ^ McCarthy, John, Creative Solutions to Problems, AISB Workshop on Artificial Intelligence and Creativity, 1999 [2007-04-27], (原始内容存档于2019-04-05) 
  5. ^ Watkins, John J., Across the board: the mathematics of chessboard problems, Princeton University Press: 12–14, 2004, ISBN 978-0-691-11503-0 .
  6. ^ 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 .

参考资料

外部链接