皇后控制問題

1、皇后控制問題皇后控制問題解題報(bào)告陳世強(qiáng)2007-7-14問題描述編程任務(wù)輸入輸出設(shè)計(jì)思想與分析皇后的攻擊范圍包括：1) 同一行2) 同一列3) 同一對(duì)角線（包括兩個(gè)方向）分析后可見，皇后之間互不攻擊當(dāng)且僅當(dāng)滿足下列條件：1) 每一行只能有一個(gè)皇后2) 每一列只能有一個(gè)皇后3) 任意條對(duì)角線上面只能有一個(gè)皇后一、先求一次隨機(jī)皇后放置的值具體如下：1、利用拉斯維加斯算法隨機(jī)在棋盤上放置m個(gè)皇后（m可取3）2、利用回溯法，放置下一個(gè)皇后，并判斷已經(jīng)放置的皇后是否已經(jīng)控制整個(gè)棋盤來決定是否已經(jīng)放置完畢。找到一個(gè)解，result=所放置的皇后數(shù)。二、重復(fù)第一步n*n次，best=min(result)

2、算法分析與設(shè)計(jì)：算法分析與設(shè)計(jì)：若:X(j)表示一個(gè)解的空間，j表示行數(shù)，里面的值表示可以放置在的列數(shù)，抽象約束條件得到能放置一個(gè)皇后的約束條件(1)X(i)!=X(k);(2)abs(X(i)-X(k)!=abs(i-k)。應(yīng)用回溯法，當(dāng)可以放置皇后時(shí)就繼續(xù)到下一行，不行的話就返回到第一行，重新檢驗(yàn)要放的列數(shù)，如此反復(fù)，直到將所有解解出。其中，拉斯維加斯算法如下：void Qeeen_search(m) lenb=n; lenc=0; while(lenb=1) int index=rnd.Random(lenb)+1; row=bindex; lenb-; lenc=0; for(int i=1;i0) index=rnd.Random(lenc)+1;關(guān)鍵程序段 lenb=n; / lenb為放置皇后的循環(huán)次數(shù)，我們可知，皇后數(shù)必定小于或者等于n個(gè)。 lenc=0; /已經(jīng)放置的皇后數(shù) Ann:初始為0，1表示已經(jīng)被控制的單元，2表示放置皇后 xi： 存放結(jié)果位置，即第i行第xi列 bestxi：存放最優(yōu)放置結(jié)果的皇后位置算法數(shù)據(jù)結(jié)構(gòu)：算法數(shù)據(jù)結(jié)構(gòu)：算法的準(zhǔn)確性： 該算法綜合了數(shù)值概率算法和拉斯維加斯算法的思想，解的準(zhǔn)確性隨重復(fù)計(jì)算的次數(shù)增加而不斷提高，最終能達(dá)到精確解。但如果時(shí)間復(fù)雜度超過了O(n!)，就失去了算法的意義。 通過不斷測(cè)試，得到循環(huán)次數(shù)=n*n對(duì)準(zhǔn)確