问题描述
在n*n的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n*n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
//暴力 #include<stdio.h> #include<math.h> #include<stdlib.h> #define n 8//指定了8个皇后可以修改 int a[n]; int ok() { int i,j; for(i=0;i<n;i++) { for(j=0;j<i;j++) if(a[i]==a[j]||abs(j-i)==abs(a[j]-a[i])) return 0; } return 1; } int main() { int sum=0; int temp; int i,j; for(i=0;i<pow(n,n);i++) { temp=i; for(j=0;j<n;j++) { a[j]=temp%n; temp/=n; } if(ok()) { sum++; } } printf("\n%d",sum); return 0; } //回溯 #include<stdio.h> #include<stdlib.h> #define n 8 int a[n]; int sum=0; int ok(int k) { for(int i=0;i<k;i++) if(a[k]==a[i]||abs(i-k)==abs(a[i]-a[k])) return 0; return 1; } void back(int h) { int i,j; if(h>=n) { sum++; } for(i=0;i<n;i++) { a[h]=i; if(ok(h)) back(h+1); } } int main() { back(0); printf("\n the number of the method is %d\n",sum); return 0; }
