您的位置: 首页  >  文章  >  八皇后问题 --c语言解决

八皇后问题 --c语言解决

分类: 文章 • 2024-11-30 12:53:10

八皇后问题（C语言版本）

原创 2015年07月05日 15:10:31
  • 八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线(对角线)上，问有多少种摆法。

回溯法详解请参考链接http://baike.baidu.com/view/6056523.htm

解决方法1

下面的C代码可以解决N皇后问题，8皇后问题的解是92。

[cpp] view plain copy
  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3.    
  4. #define max 8  
  5.    
  6. int queen[max], sum=0; /* max为棋盘最大坐标 */  
  7.    
  8. void show() /* 输出所有皇后的坐标 */  
  9. {  
  10.     int i;  
  11.     for(i = 0; i < max; i++)  
  12.     {  
  13.          printf("(%d,%d) ", i, queen[i]);  
  14.     }  
  15.     printf("\n");  
  16.     sum++;  
  17. }  
  18.    
  19. int check(int n) /* 检查当前列能否放置皇后 */  
  20. {  
  21.     int i;  
  22.     for(i = 0; i < n; i++) /* 检查横排和对角线上是否可以放置皇后 */  
  23.     {  
  24.         if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i))  
  25.         {  
  26.             return 1;  
  27.         }  
  28.     }  
  29.     return 0;  
  30. }  
  31.    
  32. void put(int n) /* 回溯尝试皇后位置,n为横坐标 */  
  33. {  
  34.     int i;  
  35.     for(i = 0; i < max; i++)  
  36.     {         
  37.         queen[n] = i; /* 将皇后摆到当前循环到的位置 */  
  38.         if(!check(n))  
  39.         {             
  40.             if(n == max - 1)  
  41.             {  
  42.                 show(); /* 如果全部摆好，则输出所有皇后的坐标 */  
  43.             }           
  44.             else  
  45.             {  
  46.                 put(n + 1); /* 否则继续摆放下一个皇后 */  
  47.             }  
  48.         }  
  49.     }  
  50. }  
  51.    
  52. int main()  
  53. {  
  54.     put(0); /* 从横坐标为0开始依次尝试 */  
  55.     printf("%d", sum);  
  56.     return 0;  
  57. }  
程序运行部分结果截图：

八皇后问题 --c语言解决

解决方法2

                                            由于8个皇后的任意两个不能处在同一行，那么肯定是每一个皇后占据一行。于是我们可以定义一个数组ColumnIndex[8]，数组中第i个数字表示位于第i行的皇后的列号。先把数组ColumnIndex的8个数字分别用0~7初始化，接下来就是对数组ColumnIndex做全排列。因为我们是用不同的数字初始化数组，所以任意两个皇后肯定不同列。我们只需要判断每一个排列对应的8个皇后是不是在同一对角线上，也就是对于数组的两个下标i和j，是不是 i-j==ColumnIndex[i]-ColumnIndex[j]或者 j-i==ColumnIndex[i]-ColumnIndex[j]。
示例代码如下：
[cpp] view plain copy
  1. int queenNumber=0;  
  2. //判断是否是合法的序列  
  3. bool JudgeValid(int* array,int length){  
  4.     for(int i=0;i<length-1;i++)  
  5.         for(int j=i+1;j<length;j++){  
  6.             if(i-j==array[i]-array[j] || j-i==array[i]-array[j])  
  7.                 return false;  
  8.         }  
  9.         return true;  
  10. }  
  11.   
  12. //获得皇后问题的全排列  
  13. void QueuePermutation(int* array,int beginIndex,int length){  
  14.     if(beginIndex==length){  
  15.         if(JudgeValid(array,length))  
  16.             ++queenNumber;  
  17.     }else{  
  18.         for(int curSub=beginIndex;curSub!=length;curSub++){  
  19.             int temp=array[beginIndex];  
  20.             array[beginIndex]=array[curSub];  
  21.             array[curSub]=temp;  
  22.             QueuePermutation(array,beginIndex+1,length);  
  23.             temp=array[beginIndex];  
  24.             array[beginIndex]=array[curSub];  
  25.             array[curSub]=temp;  
  26.         }  
  27.     }  
  28. }  
  29.   
  30. //可以解决N皇后问题  
  31. void QueueProgram(int length){  
  32.     int *array=new int[length];  
  33.     for(int i=0;i<length;i++)  
  34.         array[i]=i;//初始化数组  
  35.     QueuePermutation(array,0,length);  
  36. }   

结果输出为：92。对于合法排列，可以输出皇后放置的详细位置。


相关推荐