肢解国际象棋盘问题

肢解国际象棋盘问题（英语：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格骨牌填满。

参见

• 邓克辐射难题
• 二格骨牌平铺