八皇后问题C语言程序设计终稿.pdf

八皇后问题C语言程序设计终稿.pdf 八皇后问题是计算机科学中的一种经典问题，它是指在8*8的国际象棋棋盘上，如何摆放八个皇后，使得这八个棋子不能互相被对方吃掉。这个问题可以用C语言进行程序设计，下面是八皇后问题的C语言程序设计终稿。 一、选题及背景知识 八皇后问题是国际象棋中的一种问题，它的目标是摆放八个皇后，使得这八个棋子不能互相被对方吃掉。这个问题可以用C语言进行程序设计，解决这个问题需要使用算法设计和编程技术。 1.1 背景知识 在国际象棋中，皇后是一个威力很大的棋子，她可以“ 横冲直撞”（在正负或垂直方向走任意步数） ，也可以“ 斜刺冲杀”（在正负 45 度方向走任意步数） ，所以在 8*8 的棋盘上要布互相不受攻击的皇后，最多只能布八个，共92 种布法，再也不能有别的布法了——这就是著名的八皇后问题。 1.2 设计要求 要求：判断在国际象棋中，能否在空棋盘上摆放8 个皇后，并使其中任意两个皇后不能在同一行、同一列或同一对角线上。 二、算法设计 2.1 问题分析 设计 —— 图形表示 下图中，Q 代表皇后 假设在第 k 列上找到合适的位置放置一个皇后，要求它与第1—— k-1 列上的皇后不同行、列、对角线 ；可以从图上找到规律：不同列时成立， 皇后放在第k 列上 ；讨论行时，第 j 个皇后的位置（ a[j]，j ）要与（ i ， k）位置的皇后不同行；如果同在／斜线上，行列值之和相同；如果同在＼斜线上，行列值之差相同；如果斜线不分方向则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同, 可以表示为（|a[j]-i|=|j-k|）。 2.2 算法设计 利用计算机运行速度快的特点，采用枚举法，逐一尝试各种摆放方式，来判断最终摆法。其中判断是否同在对角线上用到了：行数差的绝对值与列数差的绝对值相等，来简化问题的判断。 三、详细设计和编码 #include<stdio.h> #include<math.h> #include<conio.h> int main(){ int a, b, c, d, e, f, g, h; // 定义每行所放皇后位置的列数 int x, y; // 定义输入皇后的行数及列数 printf("input position"); scanf("%d", &x); scanf("%d", &y); // 开始确定能摆放八个皇后的摆法 for(a=1; a<=8; ++a) // 开始确定第一个皇后的列数 for(b=1; b<=8; ++b){ // 开始确定第二个皇后的列数 if(a==b) continue; // 以此类推 if(abs(b-a)==1) continue; for(c=1; c<=8; ++c){ // ... } } } return 0; } 四、调试结果及分析 4.1 调试结果 通过编写的程序，可以输出八皇后问题的解决方案。 4.2 调试分析 通过调试结果，可以分析八皇后问题的解决方案，并可以优化程序的性能。 五、课程设计总结 5.1 总结及体会 八皇后问题的解决方案可以用C语言进行程序设计，通过枚举法，可以找到摆放八个皇后的方法。 六、答辩 6.1 答辩记录 八皇后问题的解决方案可以用C语言进行程序设计，通过枚举法，可以找到摆放八个皇后的方法。 6.2 教师意见 八皇后问题的解决方案可以用C语言进行程序设计，通过枚举法，可以找到摆放八个皇后的方法。