棋類游戲因變化無(wú)窮、富有趣味和益智功能，受到很多人的喜愛(ài)，國(guó)際象棋是其中一種。除了休閑娛樂(lè)，國(guó)際象棋中還有一些趣味知識(shí)，如八皇后問(wèn)題。

提起八皇后問(wèn)題，我們就要講到一個(gè)人——高斯。高斯是德國(guó)著名的數(shù)學(xué)家、物理學(xué)家和天文學(xué)家。他的興趣愛(ài)好十分廣泛，常常在工作之余獨(dú)自一人下棋。不過(guò)，他的下法與眾不同，其規(guī)則多數(shù)與他自己設(shè)計(jì)的一些數(shù)學(xué)問(wèn)題有關(guān)。1850年，高斯又給自己提出了一個(gè)象棋問(wèn)題：在國(guó)際象棋棋盤，即8*8的棋盤上放8個(gè)“皇后”，保證它們之間不能互相攻擊，換言之，任意兩后不能位于棋盤的同一行、同一列或同一對(duì)角線上，滿足條件的放法有多少種？

其實(shí)，八皇后問(wèn)題是一個(gè)經(jīng)典的回溯算法問(wèn)題。回溯法也稱為試探法，這種方法是指暫時(shí)放棄關(guān)于問(wèn)題規(guī)模大小的限制，并將問(wèn)題的候選解按某種順序逐一枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時(shí)，就選擇下一個(gè)候選解。倘若當(dāng)前候選解除了還不滿足問(wèn)題規(guī)模要求外，滿足所有其他要求時(shí)，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿足包括問(wèn)題規(guī)模在內(nèi)的所有要求時(shí)，該候選解就是問(wèn)題的一個(gè)解。在回溯法中，放棄當(dāng)前候選解，尋找下一個(gè)候選解的過(guò)程稱為回溯。擴(kuò)大當(dāng)前候選解的規(guī)模，以繼續(xù)試探的過(guò)程稱為向前試探。換言之，回溯法就是允許在選擇失敗的情況下，系統(tǒng)地去嘗試完所有可能的選擇。

因而，在分析八皇后問(wèn)題時(shí)，用回溯法來(lái)解決問(wèn)題是很合適的：從一個(gè)給定的位置出發(fā)有多種選擇，但不知道究竟哪種選擇才能解決問(wèn)題。由于每一個(gè)皇后擺放的位置都受到前一個(gè)皇后落子位置的限制，所以越是最先落子的皇后，可選擇的位置就越多，越后放的皇后，可選擇的范圍就越小。當(dāng)我們選擇采用回溯的方法解決八皇后問(wèn)題時(shí)，先在棋盤上放上第1個(gè)皇后，然后再放上第2個(gè)，并保證第二個(gè)皇后和第一個(gè)不互相攻擊。再接著放上第3個(gè)皇后，并滿足她與前兩個(gè)皇后都不會(huì)相互攻擊的條件，依此類推，直到所有的皇后都擺放上去。假如第7個(gè)皇后放上后，第8個(gè)皇后已經(jīng)沒(méi)有安全的位置了，則要試著調(diào)整第7個(gè)皇后的位置，并再次調(diào)整第8個(gè)皇后的位置，看是否有安全的位置；如果第7個(gè)皇后的位置都已經(jīng)嘗試過(guò)而第8個(gè)皇后還沒(méi)有安全的位置，則應(yīng)試著調(diào)整第6個(gè)皇后的位置，重新調(diào)整第7、第8個(gè)皇后的位置。依此類推，并且有可能倒退到調(diào)整第1個(gè)皇后的位置。

所以，采用回溯的方法來(lái)解決八皇后問(wèn)題，看似實(shí)現(xiàn)形式非常簡(jiǎn)單，實(shí)際上這一過(guò)程的工作量十分巨大，尤其是當(dāng)八皇后問(wèn)題擴(kuò)展到更多的時(shí)候。

本作品為“科普中國(guó)-科學(xué)原理一點(diǎn)通”原創(chuàng)，轉(zhuǎn)載時(shí)務(wù)請(qǐng)注明出處。

你知道“八皇后問(wèn)題”嗎？

圖文簡(jiǎn)介

棋類游戲因變化無(wú)窮、富有趣味和益智功能，受到很多人的喜愛(ài)，國(guó)際象棋是其中一種。除了休閑娛樂(lè)，國(guó)際象棋中還有一些趣味知識(shí)，如八皇后問(wèn)題。