肢解國際象棋盤問題

来自维基百科,自由的百科全书

肢解國際象棋盤問題

肢解國際象棋盤問題(英語: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]

解法

Thumb
肢解國際象棋盤問題的例子,移除了左上和右下的白格,棋盤中間二個黑色的方格無法用骨牌填滿,但不容易注意到

肢解國際象棋盤問題是無解的。國際象棋盤上的2x1格骨牌一定會佔據一個白色方格及一個黑色方格,因此被骨牌填滿的位置,白色方格及黑色方格的個數相同。在肢解國際象棋盤問題中,若移除的二個是白色方格,有32個黑色方格及30個白色方格要填滿,兩者數量不同,無法用2x1格骨牌填满。若移除的二個是黑色方格,有30個黑色方格及32個白色方格要填滿,還是無法用2x1格骨牌填满[4]

高莫利定理

只要國際象棋盤上移除二個同色的方格,相同的方式可以證明,移除方格後的棋盤無法用2x1格骨牌填滿。不過若填除的是二個不同顏色的方格,一定可以用2x1格骨牌填滿,這個結果稱為高莫利定理(Gomory's theorem)[5],得名自數學家拉爾夫·愛德華·高莫利英语Ralph E. Gomory,他在1973年提出的證明[6]。高莫利定理可以用棋盤組成格子圖英语grid graph哈密顿图來證明,移去二個不同色的方格會將哈密顿图切成二部份,每個部份的黑色方格及白色方格都一樣多,兩部份都可以用2x1格骨牌填滿。

參見

引用來源

參考資料

外部連結

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.