八皇后

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。

代码实现：

  1 #include <stdio.h>
  2 #include <math.h>
  3 #define NUM 8
  4 
  5 //方案计数器
  6 int count = 0; //可以不进行初始化，因为全局变量在BSS内存区域中，会自动初始化。
  7 
  8 //棋盘
  9 char matrix[8][8];
 10 
 11 //坐标点
 12 typedef struct Position
 13 {
 14     int x;
 15     int y;
 16 }Position;
 17 
 18 //保存皇后坐标点的容器
 19 typedef struct QueenArray
 20 {
 21     int num;
 22     Position pos[NUM];
 23 }QueenArray;
 24 
 25 //皇后容器全局变量
 26 QueenArray queenarr;
 27 /***************************************/
 28 /**************函数声明区***************/
 29 void Init();
 30 bool IsLegal(QueenArray *qa,Position *p);
 31 void PrintQueen();
 32 void Trial(int row);
 33 /***************************************/
 34 
 35 
 36 int main()
 37 {
 38     Init();
 39     Trial(0);
 40     return 0;
 41 }
 42 
 43 //核心函数 — 回溯思想进行遍历
 44 void Trial(int row)
 45 {
 46     int column;
 47     if(row > NUM-1)                                //注意这个坑，因为数组下标从0开始，这里是NUM-1。
 48     {
 49         count++;                                　　//全局变量计数
 50         PrintQueen();                            　　//打印皇后
 51         return;                                    //递归出口
 52     }
 53     for(column = 0;column < NUM;column++)
 54     {
 55         Position pos = {row,column};            //创建一个坐标点。
 56         if(IsLegal(&queenarr,&pos))                //判断当前坐标点是否合法
 57         {
 58             //若合法
 59             matrix[row][column] = 'Q';            // +  设置当列状态
 60             queenarr.pos[++queenarr.num] = pos;    // +  保存当前皇后
 61             Trial(row+1);                        // ->  进入下一层的尝试
 62             matrix[row][column] = '-';            // -  还原本列状态
 63             queenarr.num--;                        // -  当本列的皇后删除
 64         }
 65     }
 66 }
 67 
 68 
 69 //判断传进去的位置是否合法
 70 bool IsLegal(QueenArray *qa,Position *p)
 71 {
 72     int i,x,y,m,n;
 73     if(qa->num == -1)                        //注意，下标从0开始，初始状态为-1，表示当前容器中无皇后
 74         return true;                        //没有皇后当然整个棋盘都是合法的。
 75     m = p->x;
 76     n = p->y;
 77     for(i = 0;i <= qa->num;i++)
 78     {
 79         x = qa->pos[i].x;
 80         y = qa->pos[i].y;
 81         if(x==m||y==n||abs(x-m)==abs(y-n))    //如果在同一行，同一列，同一对角线
 82             return false;                    //不合法
 83     }
 84     return true;
 85 }
 86 
 87 //初始化棋盘
 88 void Init()
 89 {
 90     int i,j;
 91     queenarr.num = -1;
 92     for(i = 0;i<NUM;i++)
 93         for(j = 0;j<NUM;j++)
 94             matrix[i][j] = '-';
 95 }
 96 
 97 //打印出棋盘
 98 void PrintQueen()
 99 {
100     int i,j;
101     if(matrix[0][0] !='Q')
102         return;
103     printf("
第 %d 种方案
",count);
104     for(i = 0;i<NUM;i++)
105     {
106         printf("      ");
107         for(j = 0;j<NUM;j++)
108         {
109             printf("%2c",matrix[i][j]);
110         }
111             
112         printf("
");
113     }
114 }