八皇后问题

西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，

则这八个皇后如何相安无事的放置在棋盘上

解法

关于棋盘的问题，都可以用递归求解，

然而如何减少递归的次数？在八个皇后的问题中，

不必要所有的格子都检查过，例如若某列检查过，该该列的其它格子就不用再检查了，这个方法称为分支修剪。

  1 #include<stdio.h>
  2 int count=0;//用于计数
  3 
  4 int notDanger(int row,int line,int (*chess)[8])
  5 
  6     {
  7 
  8     int i,k,flag1=0,flag2=0,flag3=0,flag4=0,flag5=0; 
  9     //其实我还有一个想法就是再写一个1到5的for循环嵌套 下边的  替换这些 
 10 
 11     //判断列方向
 12 
 13     for(i=0;i<8;i++)
 14 
 15         if(chess[i][line]!=0)
 16     
 17         {
 18     
 19             flag1=1;
 20             
 21             break;
 22     
 23         }
 24 
 25     //判断左上方
 26 
 27     for(i=row,k=line;i>=0&&k>=0;i--,k--)
 28 
 29     {
 30     
 31         if(chess[i][k]!=0)
 32     
 33         {
 34     
 35             flag2=1;
 36     
 37             break;
 38     
 39         }
 40     }
 41 
 42     //判断右下方
 43 
 44     for(i=row,k=line;i<8&&k<8;i++,k++)
 45 
 46     {
 47     
 48         if(chess[i][k]!=0)
 49     
 50         {
 51     
 52         flag3=1;
 53     
 54         break;
 55     
 56         }
 57     }
 58 
 59     //判断左下方
 60 
 61     for(i=row,k=line;i<8&&k>=0;i++,k--)
 62 
 63     {
 64 
 65         if(chess[i][k]!=0)
 66     
 67         {
 68     
 69             flag4=1;
 70         
 71             break;
 72     
 73         }
 74     }
 75 
 76     //判断右上方
 77 
 78     for(i=row,k=line;i>=0&&k<8;i--,k++)
 79 
 80     {
 81 
 82         if(chess[i][k]!=0)
 83     
 84         {
 85     
 86             flag5=1;
 87         
 88             break;
 89     
 90         }
 91     }
 92 
 93     if(flag1==1||flag2==1||flag3==1||flag4==1||flag5==1)
 94 
 95     {
 96 
 97         return 0;
 98 
 99     }
100 
101     else
102 
103         return 1;
104 
105     }
106 
107 void EightQueen(int row,int n,int(*chess)[8])
108 
109     {
110 
111     //参数row：表示起始行
112 
113     //参数n:表示列数
114 
115     //参数(*chess)[8]:传递棋盘的一个指针
116 
117     int chess2[8][8],j,i;//chess2是一个临时的二维数组
118 
119     for(i=0;i<8;i++)
120 
121         for(j=0;j<8;j++)
122 
123             chess2[i][j]=chess[i][j];
124 
125         if(row==8)//如果行到达8，输出
126     
127         {
128     
129             printf("第%d种
",count+1);
130         
131             for(i=0;i<8;i++)
132         
133             {
134         
135                 for(j=0;j<n;j++)
136             
137                 {
138             
139                     printf("%d",chess2[i][j]);
140             
141                 }
142             
143                 printf("
");
144         
145             }
146         
147             count++;
148 
149         }
150 
151     else//否则插入到合适的位置
152 
153     {
154     
155         for(i=0;i<n;i++)
156     
157         {
158     
159             if(notDanger(row,i,chess2)!=0)//判断是否危险
160         
161             {
162             
163                 for(j=0;j<n;j++)
164             
165                 {
166             
167                     chess2[row][j]=0;//行赋值为0，每行只有一个
168             
169                 }
170             
171                 chess2[row][i]=1;
172             
173                 EightQueen(row+1,n,chess2);
174             
175                 }
176             }
177         }
178     }
179 
180 int main(void)
181 
182     {
183 
184     int chess[8][8],i,j;
185 
186     for(i=0;i<8;i++)//初始化
187 
188         for(j=0;j<8;j++)
189 
190             chess[i][j]=0;
191 
192     EightQueen(0,8,chess);
193 
194     return 0;
195 
196     }

回溯算法：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define N 8
 4 int column[N + 1]; // 同栏是否有皇后，1 表示有
 5 int rup[2 * N + 1]; // 右上至左下是否有皇后
 6 int lup[2 * N + 1]; // 左上至右下是否有皇后
 7 int queen[N + 1] = { 0 };
 8 int num = 0; // 解答编号
 9 void backtrack(int); // 递归求解
10 int main(void)
11 {
12     int i;
13     for (i = 1; i <= N; i++)
14         column[i] = 1;
15     for (i = 1; i <= 2 * N; i++)
16         rup[i] = lup[i] = 1;
17     backtrack(1);//从第一个开始
18     return 0;
19 }
20 void showAnswer()
21 {
22     int x, y;
23     printf("
 方案 %d
", ++num);
24     for (y = 1; y <= N; y++)
25     {
26         for (x = 1; x <= N; x++)
27         {
28             if (queen[y] == x)
29             {
30                 printf(" 1");
31             }
32             else {
33                 printf(" 0");
34             }
35         }
36         printf("
");
37     }
38 }
39 void backtrack(int i)
40 {
41     int j;
42     if (i > N)
43     {
44         showAnswer();
45     }
46     else
47     {
48         for (j = 1; j <= N; j++)
49         {
50             if (column[j] == 1 && rup[i + j] == 1 && lup[i - j + N] == 1)
51             {
52                 queen[i] = j;
53                 // 设定为占用
54                 column[j] = rup[i + j] = lup[i - j + N] = 0;
55                 backtrack(i + 1);
56                 column[j] = rup[i + j] = lup[i - j + N] = 1;
57             }
58         }
59     }
60 }

 1 #include <stdio.h>
 2 
 3 int count = 0;
 4 int chess[8][8]={0};
 5 
 6 int notDanger( int row, int col )
 7 {
 8     int i,k;
 9     // 判断列方向
10     for( i=0; i < 8; i++ )
11     {
12         if( chess[i][col]==1 )
13         {
14             return 0;
15         }
16     }
17     // 判断左对角线 
18     for( i=row, k=col; i>=0 && k>=0; i--, k-- )
19     {
20         if(chess[i][k]==1  )
21         {
22             return 0;
23         }
24     }
25     // 判断右对角线 
26     for( i=row, k=col; i>=0 && k<8; i--, k++ )
27     {
28         if(chess[i][k]==1  )
29         {
30             return 0;
31         }
32     }
33     return 1;
34 }
35 
36 void Print()          //打印结果 
37 {
38     int row,col;
39     printf("第 %d 种
", count+1);
40         for( row=0; row < 8; row++ )
41         {
42             for( col=0; col< 8; col++ )
43             {
44                 if(chess[row][col]==1)        //皇后用‘0’表示
45                 {
46                     printf("0 ");
47                 }
48                 else
49                 {
50                     printf("# ");
51                 }
52             }
53             printf("
");
54         }
55         printf("
");
56 }
57 
58 void EightQueen( int row )
59 {
60     int col;
61     if( row>7 )                       //如果遍历完八行都找到放置皇后的位置则打印
62     {
63         Print();                       //打印八皇后的解 
64         count++;
65         return ;
66         
67     }
68 
69     for( col=0; col < 8; col++ )        //回溯，递归
70     {
71         if( notDanger( row, col ) )    // 判断是否危险
72         {
73             chess[row][col]=1;
74             EightQueen(row+1);
75             
76             chess[row][col]=0;           //清零，以免回溯时出现脏数据
77         }
78     }
79 }
80 
81 int main()
82 {
83     EightQueen(0);        
84     printf("总共有 %d 种解决方法!

", count);
85     return 0;
86 }