在n＊n的棋盤上放置彼此不受攻擊的n個皇后欲主，按照國際象棋的規(guī)則较木，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子载碌。n后問題等價于在n＊n格的棋盤上放置n個皇后胁后，任何2個皇后不放在同一行或同一列或同一斜線上。
計算總共多少種方案琼娘。
//暴力：
//n^n種情況峭弟，暴力無非就是從頭到尾遍歷一遍。c[i]指第i個皇后脱拼，放到第c[i]列
#include<stdio.h>
#include<math.h>
#define n 8
int c[n]={0};
int flag=1;
int count=0;
int main(){
for(int i=0;i<pow(n,n);i++){ //代表n^n種情況
int t=i; //對每一種情況進(jìn)行操作
for(int j=0;j<n;j++){
c[j]=t%n;
t/=n;
}
flag=1;
for(int k=0;k<n;k++){ //控制行
for(int m=k+1;m<n;m++){ //控制行
if(c[k]==c[m]||fabs(m-k)==fabs(c[k]-c[m]))//列相同瞒瘸，或者同一斜線
{
flag=0;
break;
}
}
}
if(flag)
count++;
}
printf("%d\n",count);
return 0;
}
//回溯：
#include<stdio.h>
#include<math.h>
#define n 8
int c[n]={0};
int count=0;
bool ok(int t){
for(int i=0;i<n;i++){
if(i<t){
if(c[t]==c[i]||fabs(c[i]-c[t])==fabs(i-t))
return false;
}
}
return true;
}
void traceback(int t){
if(t==n){ //8個皇后都安置好了
count++;
return;
}
for(int i=0;i<n;i++){ //控制列
c[t]=i;
if(ok(t)){
traceback(t+1);
}
c[t]=0;
}
}
int main()
{
traceback(0);//t代表的是第幾行的皇后
printf("%d\n",count);
return 0;
}
運(yùn)行截圖
