N皇后问题解的个数

 

暴力递归

#include <stdio.h>int count=0,a[15],flag;
void queen(int,int);
int main(){int n;scanf("%d",&n);queen(n,n);printf("%d",count);
}
void queen(int n,int n0){if(n<1){flag=1;for(int i=1;i<=n0;i++){for(int j=1;j<=n0;j++){if(a[i]==a[j]&&i!=j)flag=0;if((a[i]-a[j]==i-j&&i!=j)||(a[i]-a[j]==j-i&&i!=j))flag=0;}}if(flag==1)count++;}else{for(int i=1;i<=n0;i++){a[n]=i;queen(n-1,n0);}}
}

不那么暴力递归

#include <stdio.h>int count=0,a[15],flag;
void queen(int,int);
int main(){int n;scanf("%d",&n);for(int i=0;i<=0;i++){a[i]=0;}queen(n,n);printf("%d",count);
}
int isconflict(int n0){for(int i=1;i<=n0;i++){for(int j=1;j<=n0;j++){if(a[i]==a[j]&&i!=j){return 0;}if((a[i]-a[j]==i-j&&i!=j)||(a[i]-a[j]==j-i&&i!=j)){return 0;}}}return 1;
}
void queen(int n,int n0){if(n<1){flag=1;flag= isconflict(n0);if(flag==1)count++;}else{for(int i=1;i<=n0;i++){for(int j=n0;j>n;j--){if(a[j]==i&&i+1<=n0)i++;if((i-a[j]==n-j||a[j]-i==n-j)&&i+1<=n0)i++;}a[n]=i;queen(n-1,n0);}}
}

 最终

#include <stdio.h>int count, mark;void test(int col, int ld, int rd) {if (col != mark) {int pos = mark & ~(col | ld | rd);while (pos) {int p = pos & -pos;pos -= p;test(col | p, ((ld | p) << 1) & mark, (rd | p) >> 1);}} else {count++;}
}int main() {int n;scanf("%d", &n);count = 0;mark = 1;mark = (mark << n) - 1;test(0, 0, 0);printf("%d\n", count);return 0;
}