肢解国际象棋盘问题

肢解国际象棋盘问题（英语：mutilated chessboard problem）属于平铺拼图问题（英语：Tiling puzzle），最早是由Max Black（英语：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]，得名自数学家拉尔夫·爱德华·高莫利（英语：Ralph E. Gomory），他在1973年提出的证明^[6]。高莫利定理可以用棋盘组成格子图（英语：grid graph）的哈密顿图来证明，移去二个不同色的方格会将哈密顿图切成二部分，每个部分的黑色方格及白色方格都一样多，两部分都可以用2x1格骨牌填满。

参见

邓克辐射难题
二格骨牌平铺（英语：Domino tiling）

引用来源

[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.

参考资料

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.

[1] [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] [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] [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.

[McCarthy-4] [4]
McCarthy, John, Creative Solutions to Problems, AISB Workshop on Artificial Intelligence and Creativity, 1999 [2007-04-27], （原始内容存档于2019-04-05）

[5] [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] [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.

[1]

[2]

[3]

[4]

[5]

[6]