八皇后-解題報(bào)告

《八皇后問題》解題報(bào)告簡述這里八皇后問題使用遞歸式深搜解法。要點(diǎn)在于：首先深搜方法得出部分排列，再判斷這樣的排列是否滿足不互相攻擊，滿足則進(jìn)行下一階段搜索，否則搜索本階段下一個部分排列，至本階段搜索完則回溯。難點(diǎn)主要的兩個難點(diǎn)是深搜函數(shù)和判斷是否會相互攻擊。前者已經(jīng)有詳細(xì)的講解，故不做過多敘述；主要對后者做討論。我們把問題作簡化：很容易知道，對于每行與每列，有且只有一個皇后。如果對64個點(diǎn)選出8個做深搜進(jìn)行判斷，既不利于判斷函數(shù)編寫，也不利于程序的效率（程序需要運(yùn)行64！/56！次）。既然具備簡化問題的條件，我們應(yīng)該積極地尋求解決問題的方法。我們利用下標(biāo)存儲行號，建立數(shù)組存儲每一行對應(yīng)的列，就極大地簡化了數(shù)據(jù)量。接下來是判斷函數(shù)的編寫。做一個簡單的推理：添加一個新的皇后時，只需檢查它與之前的皇后是否有沖突。同時由于新皇后一定在舊后的下邊，故簡化后我們只需判斷新皇后是否在如圖線上：（為節(jié)省時間簡化問題至6個皇后）（黃色六芒星表示皇后，紅色圓表示攻擊范圍）。對問題再次做簡化以適應(yīng)于簡易的算法：我們得到需要判斷的某行，在這樣的一行，對于某個皇后，最多只有兩個位置可被攻擊到。進(jìn)行一次循環(huán)并判斷，即可得到所求的解。這樣的點(diǎn)可以用簡單的幾何方法求得。至此把判斷的問題難點(diǎn)已經(jīng)攻破。代碼展示如下：#defineSTATUSint //沿用我曾看過的一本數(shù)據(jù)結(jié)構(gòu)書的方法把返回狀態(tài)的函數(shù)返回值類型 //定義為status#defineQ8 //皇后數(shù)#include<stdio.h>#include<conio.h> //提供getch()方法以中斷程序提供視點(diǎn)#include<string.h> //提供memset方法但似乎沒用上。。 //好多東西說成了java的方式。。intwer=0,ans[100];//wer存儲題解個數(shù)ans數(shù)組存儲解并即時輸出STATUSvis[100];//vis數(shù)組表示當(dāng)前的訪問狀態(tài) voiddfs(int);//深度搜索的函數(shù)聲明voidprint();//輸出的函數(shù)聲明intjudge(int,int);//判斷函數(shù)聲明voidprint(){ for(inti=1;i<=Q;i++) printf("%d",ans[i]);//依序輸出當(dāng)前取得的解 printf("\n"); //換行 wer++; //解的個數(shù)自增 if(wer%10==0)getch();//每輸出10個暫停一下}STATUSjudge(intn,intp)//這里判斷是否放置的皇后會互相攻擊{ //傳來的參數(shù)表示新皇后放置第n行第p列 for(inti=1;i<n;i++)//對于從第一個到第n個每一個皇后進(jìn)行下列檢測 { //if(p==ans[i])return-1;//首先判斷是否處于同一列上 //突然意識到?jīng)]有這樣做的必要,因?yàn)榘嘶屎髥栴}實(shí)質(zhì)上是全排列的特例, //不可能出現(xiàn)兩皇后同列 intshift=n-i;//存儲“偏移量”，對應(yīng)新添加的n+1層在對角線上的點(diǎn) //相對第一層列坐標(biāo)的位置變化，詳見我編完程序畫張圖~ if(p==ans[i]+shift||p==ans[i]-shift) return-1; //判斷是否在一條對角線上 //i+-shift可能會溢出，但是溢出后不會相等，故無需做判斷 } return0; //檢測通過 } voiddfs(intn){ if(n==Q+1)//遞推至n+1層 { print();//輸出答案 return;//回溯 } for(inti=1;i<=Q;i++)//升序搜索滿足條件的答案 { if(!vis[i])//如果這一列沒有皇后 { if(judge(n,i)==0)//如果對于新皇后放置在第n行第p列的情況不致互相攻擊 { ans[n]=i;//把第n行的皇后放置在第i列 vis[i]=1;//第i列已放置皇后 dfs(n+1);//進(jìn)行下一行的搜索 vis[i]=0;//此時已經(jīng)是回溯到上一行的搜索，重新把第i列置空 } } }} intmain(){ dfs(1);//從第1行進(jìn)行皇后的搜索 printf("%d\n",wer);//輸出解的個數(shù) getch();//全部運(yùn)行完畢制造斷點(diǎn)供觀看}結(jié)語這是我第一次做這樣的解題報(bào)告，排版什么的都很渣，希望勿怪。部分思路沿用自網(wǎng)上及此前的知識儲備，還有很多想法是自己想到的。值得注意的是，與上一次的全排列不同，主函數(shù)調(diào)用dfs函數(shù)時參數(shù)是1，否則無法產(chǎn)生正確結(jié)果。