C/C++知识点之C语言解决八皇后问题
小标 2018-11-13 来源 : 阅读 802 评论 0

摘要:本文主要向大家介绍C/C++知识点之C语言解决八皇后问题了,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。

本文主要向大家介绍C/C++知识点之C语言解决八皇后问题了,通过具体的内容向大家展示,希望对大家学习C/C++知识点有所帮助。  

  1 #include 
  2 #include 
  3 
  4 /* this code is used to cope with the problem of the eight queens.
  5  * array borad[9][9] is a virtual borad.
  6  * line 0 and volumn 0 is ignored.
  7  * at first we find a place to set a queen on it, then mark this queen‘s
  8  * domain. the way of marking domain is add 1 on the board[line][volumn],
  9  * so the number of board[line][volumn] means this place can attacked by
 10  * how many queens. after we mark this queen‘s domain, we move on to next line.
 11  * if there is no next line, we got a solution */
 12 /* 这些代码主要用来解决八皇后问题
 13  * 数组borad[9][9]是一个虚拟的棋盘。
 14  * 第0行跟第0列被忽略
 15  * 在最开始时,我们在某一行上找到一个位置,放上皇后后,我们把这个皇后能
 16  * 攻击的范围都标志起来。我们标志的方法是在board[行][列]上加1,
 17  * 所以board[行][列]上的值意味着这个位置能被多少个皇后攻击
 18  * 当我们标志好这个皇后的范围后,我们就跳到下一行去。
 19  * 如果已经没有下一行了,那么我们就找到一个放置方法了 */
 20 
 21 /* if a place on board have been marked by NONE
 22  * it means no queen can attack this place, it is a potential place to set a queen */
 23 /* 如果棋盘上一个位置被设置为NONE,意味着没有皇后能攻击这个位置,这个位置可以被设置为皇后 */
 24 #define NONE        (0)
 25 #define QUEEN       (-1)
 26 
 27 #define OCCUPY      (1)
 28 #define DISOCCUPY   (0)
 29 
 30 void Compute(int line) ;
 31 void PrintBorad(void) ;
 32 void operate_borad(int line, int volumn, int function) ;
 33 
 34 int main(void)
 35 {
 36     Compute(1) ;
 37     return 0 ;
 38 }
 39 
 40 /* ignored the first line and the first volumn */
 41 int borad[9][9] ;
 42 
 43 /* this is a recursive function.
 44  * it will find a queen on this line,
 45  * then fine next one of next line by call itself */
 46 /* 这是一个递归函数。在某一行上找到皇后的位置,然后调用自己找下一行的皇后 */
 47 void Compute(int line)
 48 {
 49     int i ;
 50     static int num_of_solution = 0;
 51     
 52     for(i = 1; i <= 8; i++)
 53         if(borad[line][i] == NONE)
 54         {
 55             operate_borad(line, i, OCCUPY) ;             
 56             if(line == 8) // find a solution
 57             {
 58                 printf("%d\n", ++num_of_solution) ;
 59                 PrintBorad() ;
 60             }
 61             else Compute(line +1) ; /* contine to next line */ /* 查找一行的皇后 */
 62             operate_borad(line, i, DISOCCUPY) ;
 63         }
 64 }
 65 
 66 /* function:
 67  * if function is OCCUPY, then set a flag of queen on borad[line][volumn]
 68  *   and set a flag on the domain of this queen
 69  * if function is DISOCCUPY, then clear flag of queen on borad[line][volumn]
 70  *   and clear the flag on the domain of this queen */
 71 /* 功能:
 72  * 如果function变量是OCCUPY,那么在board[line][volumn]上放上皇后,
 73  * 并设置这个皇后的攻击范围
 74  * 如果function变量是DISOCCUPY,那么把皇后从board[line][volumn]上清除
 75  * 并清除这个皇后在其攻击范围上所设置的标志 */
 76 void operate_borad(int line, int volumn, int function)
 77 {
 78     int i, j, *temp, nl, nv ;
 79     
 80     borad[line][volumn] = (function == OCCUPY ? QUEEN : NONE) ;
 81 
 82     /* i and j are used to decide the direction*/
 83     for(i = -1; i <= 1; i++)
 84         for(j = -1; j <= 1; j++)
 85             if(i == 0 && j == 0) continue ;
 86             else
 87             for(nl = line +i, nv = volumn +j ;
 88                 nl >= 1 && nl <= 8="" nv="">= 1 && nv <= 8 ;
 89                 nl += i, nv += j)
 90             {
 91                 temp = &borad[nl][nv] ;
 92                 /* add one means this place can be attack by another queen */
 93                 function == OCCUPY ? (*temp)++ : (*temp)-- ;
 94             }
 95 }
 96 /* function: print the board on the screen */
 97 /* 打印棋盘 */
 98 void PrintBorad(void)
 99 {
100     int x, y, chess ;
101 
102     for(x = 1; x <= 8; x++)
103     {
104         for(y = 1; y <= 8; y++)
105         {
106             chess = borad[x][y] ;
107             if(chess != QUEEN)
108                 putchar(‘*‘) ;
109             else
110                 putchar(‘Q‘) ;
111         }
112         putchar(‘\n‘) ;
113     }
114 }

本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道!

本文由 @小标 发布于职坐标。未经许可,禁止转载。
喜欢 | 1 不喜欢 | 0
看完这篇文章有何感觉?已经有1人表态,100%的人喜欢 快给朋友分享吧~
评论(0)
后参与评论

您输入的评论内容中包含违禁敏感词

我知道了

助您圆梦职场 匹配合适岗位
验证码手机号,获得海同独家IT培训资料
选择就业方向:
人工智能物联网
大数据开发/分析
人工智能Python
Java全栈开发
WEB前端+H5

请输入正确的手机号码

请输入正确的验证码

获取验证码

您今天的短信下发次数太多了,明天再试试吧!

提交

我们会在第一时间安排职业规划师联系您!

您也可以联系我们的职业规划师咨询:

小职老师的微信号:z_zhizuobiao
小职老师的微信号:z_zhizuobiao

版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
 沪公网安备 31011502005948号    

©2015 www.zhizuobiao.com All Rights Reserved

208小时内训课程