UC知道c语言编写八皇后问题
来源：百度知道 编辑：UC知道 时间：2024/07/07 04:27:17
实验要求:
实验二、八皇后问题（栈）
实验目的：熟练掌握栈操作的基本算法实现。
实现功能：利用回溯法和栈来实现八皇后问题：在8×8的国际象棋棋盘上，安放8个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一对角线。
实验机时：4
设计思路：
数据结构：
enum boolean { false , true }
enum boolean a[9] , b[17] , c[17] ;//检查皇后之间是否冲突
//皇后位置安全性可用逻辑表达式：a[ j ] && b[ i+j ] && c[ i-j+9 ]
int s[9];
//s[1..8]表示顺序栈，栈的下标值表示皇后所在的行号，栈的内容是皇后所在的列号。
该算法抽象描述如下：
（1） 置当前行当前列均为1；
（2） while(当前行号≤8)
（3） { 检查当前行，从当前列起逐列试探，寻找安全列号；
（4） if ( 找到安全列号 )
（5） 放置皇后，将列号记入栈中，并将下一行置成当前行，第一列置为当前列；
（6） else
（7） 退栈回溯到上一行，移去该行已放置的皇后，以该皇后所在列的下一列作为当前列；
（8） } 结束程序。
实验二、八皇后问题（栈）
实验目的：熟练掌握栈操作的基本算法实现。
实现功能：利用回溯法和栈来实现八皇后问题：在8×8的国际象棋棋盘上，安放8个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一对角线。
实验机时：4
设计思路：
数据结构：
enum boolean { false , true }
enum boolean a[9] , b[17] , c[17] ;//检查皇后之间是否冲突
//皇后位置安全性可用逻辑表达式：a[ j ] && b[ i+j ] && c[ i-j+9 ]
int s[9];
//s[1..8]表示顺序栈，栈的下标值表示皇后所在的行号，栈的内容是皇后所在的列号。
该算法抽象描述如下：
（1） 置当前行当前列均为1；
（2） while(当前行号≤8)
（3） { 检查当前行，从当前列起逐列试探，寻找安全列号；
（4） if ( 找到安全列号 )
（5） 放置皇后，将列号记入栈中，并将下一行置成当前行，第一列置为当前列；
（6） else
（7） 退栈回溯到上一行，移去该行已放置的皇后，以该皇后所在列的下一列作为当前列；
（8） } 结束程序。
#include <stdlib.h>
#include<math.h>
#include<conio.h>
#include<stdio.h>
int N=0;
int a[10][10];
int yp=1;
FILE * fp;
void main()
{
int *pa;
int m,n,f,aa;
int check(),reback();
int prt();
clrscr();
fp=fopen("data.dat","w");
printf("please input the number of queens(4--10):");
scanf("%d",&N);
for(m=0;m<N;m++)
for(n=0;n<N;n++)
a[m][n]=0;
m=0;n=0;aa=0;
do{for(n=0;n<N;n++)
{
f=check(m,n);
if(m==N-1 && f==1){a[m][n]=1; prt();f=0;a[m][n]=0;}
if(f==1){ a[m][n]=1; break;}
if(n==N-1&&f==0)
{
do{
m--;
n=reback(m);
if(m==0 && n==N-1 && aa==1) break;
}while(n>=N-1);
}
}
aa=1;
m++;
if(m>=N)m=0;
}while(m<N &&n<N);
printf("\n\n********IT'S OVER