搜尋 八皇后

2022-11-24 17:41:13 字數 1735 閱讀 2586

這道題應該不陌生吧,這是一道很經典的搜尋題。

總的意思就是說在一個n*n的棋盤上放n個皇后,要求它們互不攻擊,求解有多少種情況,並輸出前三種。

那麼開始分析:這畢竟是一道搜尋題,搜尋最大的弊端是什麼,當然是時間複雜度極高,雖然這道題可能不會那麼卡,我們完全可以開一個二維陣列,然後不停標記不能放的位置。但是你是否想過,一維陣列+極少的時間複雜度就可以解決問題。

那麼具體說一下該怎麼放棋子,我們不需要全域性的考慮,因為深搜最大的好處是可以簡化繁瑣的過程,因此我們先考慮只擺一枚棋子,首先假設已經擺好了,那麼要進行怎樣的操作。

如圖,比方說現在在第二行第二列的位置上放了一個皇后,那麼有哪些點永遠不能放棋子呢?

如圖,所有紅色的格子(包括這個皇后所在的格子)都不能放置皇后了,乍一看,也看不出來什麼規律,彆著急,把整個圖都以二維陣列下標的形式標上序號就一目瞭然了。

按照國際象棋的規則,皇后所能控制的是它所在的行,列,左上到右下的對角線,右上到左下的對角線。那麼我們分開看:

1)行:如果你夠細心,就會發現一行的左邊的下標的值都相等,那麼我們是不是就可以定義一個一維陣列hang(用拼音更好區分),用來儲存每行是否被哪一個皇后所霸佔,初始賦成0,如果被霸佔後,就賦為1,比如說我們要判斷(2,4)是否可以放棋子,呼叫這個陣列hang[2]即可知道這一行已經被霸佔,所以不能放置。

2)列:同上,我們仍然可以定義一個陣列用來儲存是否被霸佔,只需注意所有數是縱座標相同,和行稍有不同。

3)左上到右下的對角線:這當然是一大難點,我們可以通過座標發現規律,(1,1),(2,2),(3,3),(4,4)都是圖上皇后左上到右下所能控制的點,有沒有發現這一列的點的橫縱座標差值相同,簡單說就是1-1=2-2=3-3=4-4,(不一定非等於零,隨著這個皇后位置的改變,差值是會改變的),所以和上文一樣,我們定義一個陣列duijiaoxian2,如果要判斷(i,j)是否能擺放皇后,只需判斷duijiaoxian2[i-j]是否等於1即可。

4)右上到左下的對角線:同上,只不過是橫縱座標的和相同需要注意就可以了。

上文是擺棋時的判斷,在擺完每一顆棋後要記得把四個陣列相應數值改為1即可。

這樣,**就出來了:

1 #include2

using

namespace

std;

3int hang[1000],lie[1000],duijiaoxian1[1000],duijiaoxian2[1000],n,lujin[1000

],ans,cnt;

4void dfs(intx)5

15return;16

}17for(int i=1;i<=n;i++)

1827}28

}29intmain()

30

小編的陣列起名都是按拼音起的,便於理解,就不在過多解釋了。

codeup 2046 八皇后

會下國際象棋的人都很清楚 皇后可以在橫 豎 斜線上不限步數地吃掉其他棋子。如何將8個皇后放在棋盤上 有8 8個方格 使它們誰也不能被吃掉!這就是著名的八皇后問題。對於某個滿足要求的8皇后的擺放方法,定義一個皇后串a與之對應,即a b1b2.b8,其中bi為相應擺法中第i行皇后所處的列數。已經知道8皇...

八皇后問題

2017 10 07 21 33 16 writer pprp 經典的回溯演算法 include includeusing namespace std int vis 3 15 tot void search int cur int main void backtrack int t cout el...

八皇后問題

問題描述 在棋盤上放置 8 個皇后,使得它們互不攻擊,此時每個皇后的攻擊範圍為同行同列同對角線,要求找出所有解。leetcode上面的描述 這裡使用經典的回溯法。下面的程式簡潔地求解了八皇后問題。在主程式中讀入 n,併為 tot 清零,然後呼叫 search 0 即可得到解的個數 tot。void ...