n皇后問題

1、一、實(shí)驗(yàn)名稱：一、實(shí)驗(yàn)名稱：n皇后問題皇后問題二、實(shí)驗(yàn)?zāi)康募耙蠖?shí)驗(yàn)?zāi)康募耙?皇后問題是一個(gè)廣為人知的問題：將8個(gè)皇后放在88的棋盤上，皇后之間不能互相攻擊，求各種放法。更一般的，把8換成n，其解法個(gè)數(shù)是隨n成幾何級(jí)增長的，因此程序運(yùn)行時(shí)間也是幾何級(jí)別的?，F(xiàn)在我們關(guān)注這樣一個(gè)問題，既然不能很快的把所有解都枚舉出來，那么我們能不能很快的求出一個(gè)解來呢？這就是n皇后問題。有人說，我就用純搜索來搜第一個(gè)解，會(huì)不會(huì)快呢？你可以試一試，當(dāng)n

2、增大的時(shí)候會(huì)變的非常非常慢。除了搜索，還能有什么更好的辦法呢？下面介紹一個(gè)QS2算法，可以在當(dāng)n大到500000的時(shí)候仍能在幾分鐘之內(nèi)得到解。了這個(gè)查找的狀態(tài)空間樹。五、算法描述及實(shí)驗(yàn)步驟五、算法描述及實(shí)驗(yàn)步驟voidQueen(intn)n皇后問題voidTrySolution(intiintninta[]intb[]intc[]intx[])回溯求解n皇后問題voidOutSolution(intnintx[])輸出一組解intma