肢解國際象棋盤問題

肢解國際象棋盤問題（英語：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.