八皇后

原创

---

八皇后问题是动态规划类算法的经典问题之一，写此博客旨在学习DP，巩固知识，有错误的地方，非常欢迎大家指出。

问题描述：在一个8行8列的宫格中摆放8个皇后，要求每个皇后所在行、所在列、所在45°方向（左上方、左下方、右上方、右下方）不能有其他皇后；

要求算出一共有多少种摆法。

解决方法很简单，在宫格中，每一行每一列只能放置一个皇后，这里我以列为单位进行放置皇后（也可以以行为单位放置），在第J列中，从上都下遍历此列的所有宫格，

判断此宫格是否满足条件（行、列、斜方无其他皇后），满足条件放置皇后搜索下一列，不满足条件搜索此列的下一个宫格，如果此列的所有宫格都不满足条件，回到上一列改变

上一列宫格的位置（回溯）重新进入此列搜索；当放置完8个皇后以后计算器+1，回溯，搜索其他位置。

答案：92

 

 1 #include<stdio.h>
 2 
 3 int eight[8][8];
 4 
 5 int count;
 6 
 7 int Judge(int row,int rank)    //判断
 8 {
 9     int i,j;
10     for(j=0;j<=7;j++)    //行 
11         if( eight[row][j]==1 )
12             return 1;
13     
14     for(i=0;i<=7;i++)    //列 
15         if( eight[i][rank]==1 )
16             return 1;
17     
18     for(i=row,j=rank;i>=0 && j>=0;i--,j--)    //左上方 
19         if( eight[i][j]==1 )
20             return 1;
21             
22     for(i=row,j=rank;i>=0 && j<=7;i--,j++)    //右上方
23         if( eight[i][j]==1 )
24             return 1;
25             
26     for(i=row,j=rank;i<=7 && j>=0;i++,j--)    //左下方 
27         if( eight[i][j]==1 )
28             return 1;
29             
30     for(i=row,j=rank;i<=7 && j<=7;i++,j++)    //右下方
31         if( eight[i][j]==1)
32             return 1; 
33         
34     return 0;    
35 }
36 
37 void eightqueen(int rank)
38 {
39     if(rank==8)    //8个皇后放置完毕
40     {
41         count++;
42         return;
43     } 
44     
45     int i;
46     for(i=0;i<=7;i++)    //i代表行下标 
47     {
48         if( Judge(i,rank)==0 )    //满足条件，放置皇后
49         {
50             eight[i][rank]=1;
51             eightqueen(rank+1);
52             eight[i][rank]=0;    //回溯
53         } 
54     }
55 
56 }
57 
58 int main()
59 {
60     eightqueen(0);
61     printf("%d",count);
62     return 0;
63 } 

2018-04-07