C语言学习--八皇后问题

浏览数：25 / 时间：2015年06月08日

问题描述：

在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

程序设计：

1、一维数组a[17]，数组分成三段，第一段a[0]用来标记八皇后安置完成；第二段a[1,8]用来标记列位置有无子，方便判断列冲突；第三段a[9,16]用来标记存储位置。

2、关键算法递归判断位置，eightQueens 。

3、对角线位置互斥判断， isDiagonal。

4、输出函数， printResult。

算法描述：

1、首次传入为数组a和起始列变量i=1，判断标记为a[0]是否为1，为1进入2，否则进入3；

2、打印数组a[9,16];

3、测试j是否小于8，下于则递归结束，否则探测j列是否合法,合法进入4，否则j++，重走3;

4、列标记为a[j]置1，存储位置标记a[8+i]置为i,j组合的位置代号（i*10+j）；

5、判断是否已安置所有皇后，是则将标记为a[0]置1。

6、列号加1，再次递归。

7、清除本次递归设置的值，为方便回溯、重新寻找其他组合的，返回3。

  1 /*
  2     功能： Eight queens
  3     时间： 2014-08-31 14:34:56
  4 */
  5 #include <stdio.h>
  6 
  7 int c = 1; //简单的分页
  8 
  9 void eightQueens(int *a, int i);    //递归求解
 10 int isDiagonal(int *a, int n);        //判断是否同对角线
 11 void printResult(int *a);            //输出结果
 12 
 13 int main(void)
 14 {
 15     int a[17];
 16     int i;
 17     
 18     //初始化棋盘
 19     for(i=0; i<17; i++)
 20     {
 21         a[i] = 0;
 22     }
 23 
 24     //求解方法
 25     eightQueens(a, 1);
 26     
 27     return 0;
 28 }
 29 
 30 void eightQueens(int *a, int i)
 31 {
 32     int j;
 33 
 34     if(a[0]==1)
 35     {
 36         //输出结果
 37         printResult(a);
 38     }
 39     else
 40     {
 41         for(j=1; j<9; j++)
 42         {
 43             if(a[j] != 1 && isDiagonal(a, i*10+j)) //非同行、非同列、不再对角线。
 44             {
 45                 a[j] = 1;
 46                 a[8+i] = i*10+j;
 47                 if(i == 8) a[0] = 1;
 48                 //递归
 49                 if(i<=8)
 50                 {
 51                     eightQueens(a, i+1);
 52                 }
 53                 a[j] = 0;
 54                 a[8+i] = 0;
 55                 a[0] = 0;
 56             }
 57         }
 58     }
 59     
 60 }
 61 
 62 //判断是否同对角线
 63 int isDiagonal(int *a, int n)
 64 {
 65     int aDcd, aBit;    //已标记的行列坐标
 66     int nDcd, nBit; //待判断的行列坐标
 67     int tDcd, tBit; //已标记与待判断行列差值
 68     int k;
 69 
 70     nDcd = n/10;
 71     nBit = n%10;
 72 
 73     for(k=9; k<17; k++)
 74     {
 75         if(a[k] != 0)
 76         {
 77             //分离已标记坐标的行与列
 78             aDcd = a[k]/10;
 79             aBit = a[k]%10;
 80             
 81             tDcd = nDcd - aDcd; //计算行差值
 82             tBit = nBit - aBit; //计算列差值
 83 
 84             if((tDcd-tBit) == 0 || (tDcd + tBit) == 0) //行列差值的绝对值相等则在同对角线
 85             {
 86                 return 0;
 87             }
 88         }
 89         else
 90         {
 91             return 1;
 92         }
 93     }
 94     return 1;
 95 }
 96 
 97 //输出结果
 98 void printResult(int *a)
 99 {
100     int m; 
101 
102     printf("Scheme %d :\n", c);
103     for(m=9; m<17; m++)
104     {
105         printf("a[%d]\t", a[m]);
106     }
107     printf("\n");
108     
109     c++;
110 
111     if(c%10 == 0){
112         getchar();
113     }
114 }