回溯法解決四皇后問題

2022-11-24 16:36:33 字數 1876 閱讀 8013

以4皇后為例,其他的n皇后問題以此類推。所謂4皇后問題就是求解如何在4×4的棋盤上無衝突的擺放4個皇后棋子。在國際象棋中,皇后的移動方式為橫豎交叉的,因此在任意一個皇后所在位置的水平、豎直、以及45度斜線上都不能出現皇后的棋子,例子

要求程式設計求出符合要求的情況的個數。四皇后問題有很多種解法,這裡主要介紹一種經典的解決方法:回溯法

回溯法的基本思想是:可以構建出一棵解空間樹,通過探索這棵解空間樹,可以得到四皇后問題的一種或幾種解。這樣的解空間樹有四棵

在如上圖所示的4×4的棋盤上,按列來擺放棋子,首先因為皇后棋子不能在同一列,所以先排除有2個或2個以上的棋子在同一列的情況,所以第一個棋子在第一列有4種擺放方法(第1列第1行,第1列第2行,第1列第3行,第1列第4行),同樣第二個棋子在第二列有4種,同樣第三個棋子在第三列有4種,同樣第四個棋子在第四列有4種,所以進行簡單的排除不在同一列的情況後,還有4×4×4×4=256種可能,但是在這256種可能裡,依然存在比如棋子在同一行,或在45度斜線上的情況出現。另一個角度思考,所有的滿足四皇后問題的擺放方式一定都存在於這256種情況之中。簡單的理解就是:這256種棋盤局面包含了所有滿足4皇后問題的解,但是不包含全部的棋盤局面。

下面是解空間樹的示例(以上一段的按列擺放的方式來進行示例講解),其中第i層的棋盤局面是在第i-1層的棋盤局面演化而來的(1

上面的是以第一個棋子在第一列的第一行而派生出的一個解空間樹,最後一層會有64中結局面,同理在以第一個棋子在第

一、列的第二/三/四行都分別可以派生出一個解空間樹,最後一層都會有64中局面,所以有4棵解空間樹,每一棵最終有64個局面,所以一共有4×64=256種局面

可以用上面的方法窮舉出所有的解,再遍歷窮舉的所有結果找出所有符合四皇后問題的解,但是這樣會很浪費。所以這裡可以用到回溯法,在構建解空間樹的途中進行深度優先探索,當探索到某一種棋盤局面一定不是四皇后問題的解的時候(比如出現任意兩個或兩個以上的棋子在同一行/同一列/45度斜線上),就可以判斷這個節點向下派生出的解空間樹的節點也一定不是四皇后問題的解,這樣就可以避免大量的無用功。

比如上圖中第二行的第一個節點出現了兩個棋子在同一行的情況,所以可以判斷出這個節點以及這個節點向下派生出的所有節點就不再有必要進行遍歷了,這樣就會避免4+4×4次的完全無用功的遍歷,就會大大的節省時間,再去探索第二行的第二個節點……其他的同理。

這樣,如果能夠成功遍歷到葉子節點,並且判斷該葉子節點的局面就是符合4皇后問題的,那麼這個節點局面就代表一個合法的四皇后問題的解。下面的就代表找到的一個合法的解的過程(注意中,虛線代表排除,黑實線代表繼續向下探索)     以上圖為例,當在第i層出現非法的棋盤局面時,就跳回第i-1層,繼續探索第i-1層的那個節點的下一個分支;或者在第4層探索到合法的局面就進行記錄並跳回上一層,繼續探索下一個分支。其他三個解空間樹同理。

以上圖為例,就單看探索的第四層節點的個數。使用回溯法,就只需探索第4層中的4個節點,而如果使用窮舉法,就要探索玩第4層的所有64個節點,顯而易見,哪一個方法更有效。

其實在解決四皇后問題的時候,並不一定要真的構建出這樣的一棵解空間樹,它完全可以通過一個遞迴回溯來模擬。所謂的解空間樹只是一個邏輯上的抽象。當然也可以用樹結構來真實的建立出一棵解空間樹,不過那樣會比較浪費空間資源,也沒有那個必要

解決四皇后問題的演算法描述如下

1 #include2

3int count = 0;4

int iscorrect(int i, int j, int (*q)[4])5

2829

void queue(int j, int (*q)[4

])30

39 printf("\n"

);40 count++;

41return;42

}43for(i=0; i<4; i++)49}

50}5152

intmain()

53

回溯法解決N皇后問題(以四皇后為例)

以4皇后為例,其他的n皇后問題以此類推。所謂4皇后問題就是求解如何在4 4的棋盤上無衝突的擺放4個皇后棋子。在國際象棋中,皇后的移動方式為橫豎交叉的,因此在任意一個皇后所在位置的水平 豎直 以及45度斜線上都不能出現皇后的棋子,例子 要求程式設計求出符合要求的情況的個數。四皇后問題有很多種解法,這裡...

八皇后問題 回溯法

目錄 實現 參考資料 眾所周知國際象棋是一種經典而著名的二人對弈的棋類遊戲,相信這個不必我多介紹。棋子共有國王 皇后 戰車 主教 騎士 禁衛軍這七種,不僅出現於國際象棋的棋盤上,在其他領域的作品中也會用這些棋子做點文章,例如 逆轉檢事2 的邏輯象棋系統 御劍檢察官的腦洞 不過我仍然不是來向你推薦遊戲...

回溯法(8皇后問題)

遞迴函式不再呼叫它本身,而是返回上一層呼叫,這種現象稱為回溯。表現在解答樹中就是一個結點本來應該有的分支因為不滿足條件而沒有接續產生分支。八皇后問題 在8 8的棋盤上,放置8個皇后,使其不互相攻擊,皇后的攻擊範圍為同行同列和同對角線,找出所有解。思考可知 每一行只能放一個,每一列也只能放一個。用c ...