四個皇后

   「在西洋棋的棋盤上放八個王后,使得沒有一個王后能吃掉其它王后」這個問題是Franz Nauck於1850年最先提出的。我們知道西洋棋中王后是可以縱、橫、斜向的任意移動,但如今我們要在一個8乘8個正方形格子的棋盤上放置8個王后,使任一個王后不被其他的王后吃掉。大數學家高斯(Gauss)曾猜測此問題共有96個解,但後來經過嚴格證明,實際上只有92個解(此為形式解;而本質解(即沒辦法由某一個解經旋轉或反射後得到另一個解)只有12個。)。
以八皇后問題的規則來討論4乘4棋盤上所謂之四皇后問題會有幾個解。我們採用4維向量(a,b,c,d)表示四個皇后在4乘4棋盤上的一種放法。例如,(2,4,1,3)對應著圖一所示的方法。圖中Q代表皇后。

圖一       

圖二

假設在棋盤上已經放好三個皇后,第四個皇后還沒有放(如圖二),對應的向量應為(1,4,2,×),第四個分量 ”×”,表示第四個皇后還未確定位置。
為今後的方便,我們用
「條件A」代表 「沒有兩個皇后在同一行、同一列或同一對角線上」。我們可以發現,圖二對應的(1,4,2,×),第四個皇后不管怎麼放,都不能符合條件A。
讓我們先看一下圖三所示的樹狀圖,樹根用(×,×,×,×)標記,表示棋盤上沒有皇后(空棋盤),樹中每個頂點都對應著棋盤上放皇后的一個狀態,如(1,4,2,×)就表示圖二所呈現之狀態。

圖三

由圖三看來,要找出”四皇后”問題的解,最可靠的方法就是把種情況全部檢核一遍,將符合條件A的解找出來。但這樣做,你要有相當耐心才行,這是很費時的。現在我們改用一個比較可行的方法來處理,首先,依次序先檢查(1,×,×,×),再往下層檢查(1,1,×,×)。因為(1,1,×,×)表示前兩個皇后都位於第一行上,違反條件A。所以(1,1,×,×)以下的子樹的樹枝就都不必再逐一的搜索了。這時,應退回到上一級的頂點(1,×,×,×)處,以下一個頂點(1,2,×,×)來考察。而我們可以發現(1,2,×,×)這個頂點也違反了條件A(在同一對角線上),於是再返回(1,×,×,×)。現在我們利用圖四,以此方法繼續做下去:(a)表示第一個皇后放在第一行,第二個皇后就不能放在第一列也不能放在第二列,只能以第三列開始搜尋;(b)表示以(1,3,×,×)為樹根的子樹都不是問題的解,因為第三個皇后無論怎麼放,都違反條件A;(c)表示(1,4,1,×)違反A,而(1,4,2,×)仍能符合A;(d)表示(1,4,2,×)在考慮第四個皇后位置,就被否決了。

圖四

(a)

(b)

(c)

(d)

如此按上述方式繼續做下去,不難得到一個結論:”四皇后問題”共有兩個解,如圖五中的(A)(2,4,1,3)和(B)(3,1,4,2)。

(A)(2,4,1,3)

(B)(3,1,4,2)

圖五

讓我們來看一下(A)(B)這兩個解,可以發現其乃相互對稱的,所以(A)(B)這兩個解在本質上只是同一個解,也就是說,雖然(2413)(3142)形式上是兩個解,本質上只是一個解。於是,我們有了形式解本質解的初步概念。
現在讓我們回到”八皇后問題”上來。我們可以利用解決四皇后問題的方法來求得八皇后的解。想看看:高斯在猜測八皇后問題時,為何會想成有96個解呢?

資料來源: 彰師大數學系數學史-數學課堂中的參考資料


回上一頁