139
各大計算機公司 筆試及麵試 題目 - 深信服（八皇後問題）
八皇後問題是一個以國際象棋為背景的問題：如何能夠在 8×8 的國際象棋棋盤上放置八個皇後，使得任何一個皇後都無法直接吃掉其他的皇後？為了達到此目的，任兩個皇後都不能處於同一條橫行、縱行或斜線上。八皇後問題可以推廣為更一般的n皇後擺放問題：這時棋盤的大小變為n×n，而皇後個數也變成n。當且僅當 n =
1 或 n ≥ 4 時問題有解。
在n×n格的棋盤上擺放n個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，求解滿足條件的棋盤布局。
n-皇後問題是典型的可以使用回溯算法求解的問題。如果你明白了問題的具體執行過程，也就對該問題的特點有了把握，從而選擇合適的算法去求解。
以8-皇後問題為例，假設皇後所在的行用變量row表示，對應的列使用數組column[row]表示。
使用回溯算法執行的過程如下：
（1）第一次放置第1個皇後
將第1個皇後放在第0行第0列，即row=0，column[row]=column[0]，如圖所示：
第1個皇後放置在坐標(0,0)處。
（2）第一次放置第2個皇後
因為第1個皇後已經放好，第1個皇後放置到第0行第0列，從第1個皇後下方的格子開始判斷。第2個皇後位於第1行，則row=1：
當column[row]=column[1]=0時，與第1個皇後在同一列上，衝突，繼續後移到下一列（即column[row]++）；
當column[row]=column[1]=1時，與第1個皇後在同一對角線上，衝突，繼續後移到下一列（即column[row]++）；
當column[row]=column[1]=2時，與第1個皇後不在同一行、同一列、同一對角線上，故放置第2個皇後。
如圖所示：
第2個皇後放置在坐標(1,2)處。
（3）第一次放置第3個皇後
因為第2個皇後已經放好，第2個皇後放置到第1行第2列，從第2個皇後下方的格子開始判斷。第3個皇後位於第2行，則row=2：
當column[row]=column[2]=0時，與第1個皇後在同一對角線上，衝突，繼續後移到下一列（即column[row]++）；
當column[row]=column[2]=1時，與第2個皇後在同一對角線上，衝突，繼續後移到下一列（即column[row]++）；
當column[row]=column[2]=2時，與第2個皇後在同一列上，衝突，繼續後移到下一列（即column[row]++）；
當column[row]=column[2]=3時，與第2個皇後在同一對角線上，衝突，繼續後移到下一列（即column[row]++）；
當column[row]=column[1]=4時，與第1、2個皇後不在同一行、同一列、同一對角線上，故放置第3個皇後。
如圖所示：
第3個皇後放置在坐標(2,4)處。
（4）第一次放置第4個皇後
如圖所示：
第4個皇後放置在坐標(3,1)處。
（5）第一次放置第5個皇後
如圖所示：
第4個皇後放置在坐標(4,3)處。其餘依次類推。
代碼如下：
備注：轉載於 https://hi.baidu.com/shirdrn/blog/item/2720311b5cc970108618bfb1.html
最後更新：2017-04-04 07:03:49