八皇后问题 学
2012年  9 月 5 日
一、选题
1.1背景知识………………………………………………………………………2
1.2设计目的与要求………………………………………………………………2
二、算法设计
2.1问题分析………………………………………………………………………3
2.2算法设计………………………………………………………………………3
三、详细设计
3.1源程序清单……………………………………………………………………4
四、调试结果及分析
4.1调试结果………………………………………………………………………6
4.2调试分析………………………………………………………………………7
五、课程设计总结
5.1总结及体会……………………………………………………………………7
六、答辩
6.1答辩记录………………………………………………………………………8
6.2教师意见………………………………………………………………………8
一、选题及背景知识
1.1 背景知识
    在国际象棋中，皇后是一个威力很大的棋子，她可以“横冲直撞”（在正负或垂直方向走任意步数），也可以“斜刺冲杀”（在正负45度方向走任意步数），所以在8*8的棋盘上要布互相
不受攻击的皇后，最多只能布八个，共92种布法，再也不能有别的布法了——这就是著名的八皇后问题
在8*8的国际象棋棋盘上，放置八个皇后，使得这八个棋子不能互相被对方吃掉。也就是说一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 
1.2 设计要求
要求：·判断在国际象棋中，能否在空棋盘上摆放8个皇后，并使其中任意两个皇后不   
      能在同一行，同一列或同一对角线上。
·编写完整的摆放八皇后问题的程序
·具体要求第一个皇后的起始位置由键盘输入 
二、算法设计               
2.1问题分析
设计——图形表示  下图中，Q代表皇后
假设在第k列上到合适的位置放置一个皇后，要求它与第1——k-1列上的皇后不同行、列、对角线；可以从图上到规律：不同列时成立，皇后放在第k列上；讨论行时，第j个皇后的位置（a[j] ，j）要与（i，k）位置的皇后不同行；如果同在／斜线上，行列值之和相同；如果同在＼斜线上，行列值之差相同；如果斜线不分方向则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同,可表示为（|a[j]-i|=|j-k|）。
2.2 算法设计
  利用计算机运行速度快的特点，采用枚举法，逐一尝试各种摆放方式，来判断最终摆法。
其中判断是否同在对角线上用到了：  行数差的绝对值与列数差的绝对值相等，来简化问题的判断。以a,b,c,d,e,f,g,h 的值表示皇后在第一，二，三，四，五，六，七，八行对应的列数就很好的解决了行列的问题。
      我的想法：，只是要能根据输入的位置进行程序。我使用了switch 选择结构语句，j表示行数，k表示列数，当j为一时即皇后在第一行，然后再看a与k是否相等，当a不等于k时，则continue，跳出本次循环，知道a等于k时。
    其中函数大致分为三大模块：
    1、排列出一种八皇后排列方法
    2、 用swich判断是否有一个位置与输入的相同
    3、若满足，输出皇后列数，即a,b,c,d,e,f,g,h.
                                           
三、详细设计和编码
#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;                      //以此类推...
printf输出格式 同行
if(abs(b-a)==1) continue;
for(c=1;c<=8;++c) {
if(c==a||c==b) continue;
if(abs(c-a)==2||abs(c-b)==1) continue;
for(d=1;d<=8;++d) {
if(d==a||d==b||d==c) continue;
if(abs(d-a)==3||abs(d-b)==2||abs(d-c)==1) continue;
for(e=1;e<=8;++e) {
if(e==a||e==b||e==c||e==d) continue;
if(abs(e-a)==4||abs(e-b)==3||abs(e-c)==2||abs(e-d)==1) continue;
for(f=1;f<=8;++f){
if(f==a||f==b||f==c||f==d||f==e) continue;
if(abs(f-a)==5||abs(f-b)==4||abs(f-c)==3||abs(f-d)==2||abs(f-e)==1) continue;
for(g=1;g<=8;++g) {
if(g==a||g==b||g==c||g==d||g==e||g==f) continue;
if(abs(g-a)==6||abs(g-b)==5||abs(g-c)==4||abs(g-d)==3||abs(g-e)==2||abs(g-f)==1) continue;
for(h=1;h<=8;++h) {
if(h==a||h==b||h==c||h==d||h==e||h==f||h==g) continue;
if(abs(h-a)==7||abs(h-b)==6||abs(h-c)==5||abs(h-d)==4||abs(h-e)==3||abs(h-f)==2||abs(h-g)==1) continue;
                            //  判断以上产生的结果是否满足 所输入的皇后位置
switch(x) {                //  若不满足，从新尝试其他摆法。若满足则输出八个皇   
case 1:                    //  后的位置
if(y!=a) continue;
break;
case 2:
if(y!=b) continue;
break;
case 3:
if(y!=c) continue;
break;
case 4:
if(y!=d) continue;
break;
case 5:
if(y!=e) continue;
break;
case 6:
if(y!=f) continue;
break;
case 7:
if(y!=g) continue;
break;
case 8:
if(y!=h) continue;
break;
}
printf("(1,%d) ",a);                // 输出皇后位置的一种摆法
printf("(2,%d) ",b);
printf("(3,%d) ",c);

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。