目錄
[TOC]
問(wèn)題分析：
相信八皇后規(guī)則的問(wèn)題，大家都很熟悉悠反，接下來(lái)是如何分析回溯法的應(yīng)用莉御≡啻穑回溯法與圖里面的深度優(yōu)先遍歷非常的類似，就是探熔，在滿足題目條件時(shí)候，它總是優(yōu)先選擇第一個(gè)烘挫，當(dāng)不滿足的時(shí)候诀艰，它會(huì)選擇接下來(lái)的一個(gè)點(diǎn)，通常會(huì)用遍歷數(shù)組的方式饮六。
總體的代碼構(gòu)建如下
void fun(n){
if(總體條件){
for(){
fun(n+1);
}
}
本問(wèn)題分析：
每次填滿第一行第一列其垄，當(dāng)不滿足時(shí)候，試下第一行第二列卤橄，依次進(jìn)行绿满，遞歸的出口為找到第八個(gè)點(diǎn)，跳出遞歸窟扑。喇颁，在循環(huán)里面還要判斷是否滿足不同行，不同列嚎货，不同對(duì)角線橘霎。
具體代碼實(shí)現(xiàn)：
#include<stdio.h>
#include<math.h>
int max=8,sum=0,a[8];
void show(){ //顯示每次成功后整個(gè)界面的坐標(biāo)
for(int i=0;i<max;i++){
printf("(%d,%d)\t",i,a[i]);
}
printf("\n");
}
int check(int n){
for(int i=0;i<n;i++){ //這里只需要比較到已知就行
if(a[i]==a[n]||abs(a[n]-a[i])==(n-i))//這里比較關(guān)鍵，就是判斷現(xiàn)在放下的皇后是否與之前
return 0 ; //放下的皇后有沖突（即不同列殖属，不同對(duì)角線姐叁，因?yàn)橹坝?
}
return 1; //之前有調(diào)用 eightQueen(n+1); //保證了不同行
}
int eightQueen(int n){
int i;
if(n<max){
for(i=0;i<max;i++){
a[n]=i;
if(check(n))
eightQueen(n+1);
}
}
else{
sum++;
show();
}
}
int main(){
eightQueen(0); //從第零行開(kāi)始
printf("%d",sum);
}
Alt text
總共有92種。
結(jié)論：
主要是找到遞歸的出口，當(dāng)滿足添加時(shí)候外潜，執(zhí)行遞歸原环，不滿足時(shí)候，執(zhí)行循環(huán)的下一步处窥。 馬走日問(wèn)題也是類似的嘱吗。
