首页 > 代码库 > C语言学习--八皇后问题
C语言学习--八皇后问题
问题描述：
在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 }
C语言学习才开始，许多还不太熟悉，还没看到算法，只是凭自己想的写的，比较粗糙，至于优化之类留与后期吧。
C语言学习--八皇后问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。