经典八皇后问题
只写的最基本的，对称剪枝，位运算都没有用，以后有时间再看
1 /* ID:linyvxi1
2 PROB:checker
3 LANG:C++
4 */
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8 int N;
9 int total_solutions=0;
10 int times_already_output=0;
11 bool placed[15][15]={false};
12 int diagonals_l[50]={0};
13 int diagonals_r[50]={0};
14 bool column_ok[15]={true};
15 bool can_place_queen(int row,int column)
16 {
17 int r=row-column;
18 if(r<0){
19 r=-1*r+N;
20 }
21 if(column_ok[column]&&!placed[row][column]&&diagonals_l[row+column]<1&&diagonals_r[r]<1){
22 return true;
23 }
24 return false;
25
26 }
27 void place_queen(int row)
28 {
29 if(row==N+1){
30 /*deal with output :)
31 */
32 total_solutions++;
33 if(times_already_output>=3){
34 return;
35 }
36 times_already_output++;
37 int i,j;
38 bool first=true;
39 for(i=1;i<=N;i++){
40 for(j=1;j<=N;j++){
41 if(placed[i][j]){
42 if(!first){
43 putchar(' ');
44 }
45 if(first){
46 first=false;
47 }
48 printf("%d",j);
49 break;
50 }
51 }
52 }
53 putchar('\n');
54 }
55
56 int column;
57 for(column=1;column<=N;column++){
58 if(can_place_queen(row,column)){
59 int l=row+column;
60 int r=row-column;
61 if(r<0){
62 r=-1*r+N;
63 }
64 column_ok[column]=false;
65 placed[row][column]=true;
66 diagonals_l[l]++;
67 diagonals_r[r]++;
68 place_queen(row+1);
69 diagonals_l[l]--;
70 diagonals_r[r]--;
71 placed[row][column]=false;
72 column_ok[column]=true;
73 }
74 }
75 }
76 int main()
77 {
78 freopen("checker.in","r",stdin);
79 freopen("checker.out","w",stdout);
80 scanf("%d",&N);
81 memset(column_ok,true,sizeof(column_ok));
82 place_queen(1);
83 printf("%d\n",total_solutions);
84 }