握住科學鑰匙 打開科學之門

首頁 > 正文

你知道“八皇後問題”嗎?

2019-09-20 15:19  來源: 新華網

棋類遊戲因變化無窮、富有趣味和益智功能,受到很多人的喜愛,國際象棋是其中一種。除了休閒娛樂,國際象棋中還有一些趣味知識,如八皇後問題。

提起八皇後問題,我們就要講到一個人——高斯。高斯是德國著名的數學家、物理學家和天文學家。他的興趣愛好十分廣泛,常常在工作之余獨自一人下棋。不過,他的下法與眾不同,其規則多數與他自己設計的一些數學問題有關。1850年,高斯又給自己提出了一個象棋問題:在國際象棋棋盤,即8*8的棋盤上放8個“皇後”,保證它們之間不能互相攻擊,換言之,任意兩後不能位于棋盤的同一行、同一列或同一對角線上,滿足條件的放法有多少種?

其實,八皇後問題是一個經典的回溯算法問題。回溯法也稱為試探法,這種方法是指暫時放棄關于問題規模大小的限制,並將問題的候選解按某種順序逐一枚舉和檢驗。當發現當前候選解不可能是解時,就選擇下一個候選解。倘若當前候選解除了還不滿足問題規模要求外,滿足所有其他要求時,繼續擴大當前候選解的規模,並繼續試探。如果當前候選解滿足包括問題規模在內的所有要求時,該候選解就是問題的一個解。在回溯法中,放棄當前候選解,尋找下一個候選解的過程稱為回溯。擴大當前候選解的規模,以繼續試探的過程稱為向前試探。換言之,回溯法就是允許在選擇失敗的情況下,係統地去嘗試完所有可能的選擇。

因而,在分析八皇後問題時,用回溯法來解決問題是很合適的:從一個給定的位置出發有多種選擇,但不知道究竟哪種選擇才能解決問題。由于每一個皇後擺放的位置都受到前一個皇後落子位置的限制,所以越是最先落子的皇後,可選擇的位置就越多,越後放的皇後,可選擇的范圍就越小。當我們選擇採用回溯的方法解決八皇後問題時,先在棋盤上放上第1個皇後,然後再放上第2個,並保證第二個皇後和第一個不互相攻擊。再接著放上第3個皇後,並滿足她與前兩個皇後都不會相互攻擊的條件,依此類推,直到所有的皇後都擺放上去。假如第7個皇後放上後,第8個皇後已經沒有安全的位置了,則要試著調整第7個皇後的位置,並再次調整第8個皇後的位置,看是否有安全的位置;如果第7個皇後的位置都已經嘗試過而第8個皇後還沒有安全的位置,則應試著調整第6個皇後的位置,重新調整第7、第8個皇後的位置。依此類推,並且有可能倒退到調整第1個皇後的位置。

所以,採用回溯的方法來解決八皇後問題,看似實現形式非常簡單,實際上這一過程的工作量十分巨大,尤其是當八皇後問題擴展到更多的時候。

本作品為“科普中國-科學原理一點通”原創,轉載時務請注明出處。

作者: 朱寅瑩   [責任編輯: 李浩]

相關稿件

象棋,數學