肢解國際象棋盤問題

肢解國際象棋盤問題（英語：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, , , 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., (PDF), 2005 [2007-05-06], The mutilated chessboard theorem was proposed over 40 years ago by John McCarthy as a "tough nut to crack" for automated reasoning.
Alekhnovich, Michael, , Theoretical Computer Science, 2004, 310 (1-3): 513–525, doi:10.1016/S0304-3975(03)00395-5.
McCarthy, John, , , 1999 [2007-04-27], （原始内容存档于2019-04-05）
Watkins, John J., , 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., , The College Mathematics Journal (Mathematical Association of America), 2004, 35 (2): 115–120, JSTOR 4146865, doi:10.2307/4146865; Honsberger, R., , Mathematical Association of America, 1973.

參考資料

Gamow, George; Stern, Marvin, , Viking Press, 1958, ISBN 978-0-333-08637-7
Gardner, Martin, , 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Andrews, Peter B.; Bishop, Matthew, , , 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., (PDF), 2005 [2007-05-06], 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, , Theoretical Computer Science, 2004, 310 (1-3): 513–525, doi:10.1016/S0304-3975(03)00395-5.

[McCarthy-4] McCarthy, John, , , 1999 [2007-04-27], （原始内容存档于2019-04-05）

[5] Watkins, John J., , 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., , The College Mathematics Journal (Mathematical Association of America), 2004, 35 (2): 115–120, JSTOR 4146865, doi:10.2307/4146865; Honsberger, R., , Mathematical Association of America, 1973.