Question

用C语言编写八皇后问题

八皇后问题要求在一个8 × 8 的 棋盘上放上8个皇后，使得每一个皇后既攻击不到另外 7 个皇后，也不被另外 7 个皇后所攻击。 按照国际象棋的规则， 一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子。 因此， 八皇后问题等于要求 8 个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 要有注释

Answer 1

如下是8皇后的程序：
#include<stdio.h>
#include<stdlib.h>
void eightqueen(int a[][99],int n);
void print(int a[][99]);
int up(int a[][99],int row,int col);
int down(int a[][99],int row,int col);
int left(int a[][99],int row,int col);
int right(int a[][99],int row,int col);
int num=0;
main()
{
int a[99][99]={0},n; //将皇后的位置放在一个二维的数组里面，a[i][j]=1表示该位置有一个皇后
eightqueen(a,0);

system("pause");
return 0;
}

void print(int a[][99]) //输出当前的一种合理的走法。
{
int i,row,col;
printf("Case %d\n",num);
for(row=0;row<8;row++)
{

for(col=0;col<8;col++)
{
printf("%d ",a[row][col]);
}
printf("\n");

}
printf("\n");
}
void eightqueen(int a[][99],int row) //通过回溯法计算8皇后的走法。
{
int col,i;
for(col=0;col<=7;col++)
{

//判断都前位置是否是合理的位置。
if ((up(a,row,col)==0)&&(down(a,row,col)==0)&&(left(a,row,col)==0)&&(right(a,row,col)==0))
{
a[row][col]=1; //如果是，将当前位置置为1（摆放一个皇后）
if(row==7) //所有的8个皇后都已经摆放好了，输出当前的情况。
{
num++;
print(a);
}
else
{
eightqueen(a,row+1); //在row+1摆放下一个皇后。
}
a[row][col]=0;
}
}
}
//判断同一行列是否有其他的皇后
int up(int a[][99],int row,int col)
{
int i;
for(i=0;i<8;i++)
{
if(a[i][col]==1)
{
return 1;
}
}
return 0;
}
//判断同一行上是否有其他的皇后
int down(int a[][99],int row,int col)
{
int i;
for(i=0;i<8;i++)
{
if(a[row][i]==1)
{
return 1;
}
}
return 0;
}

//判断左上到右下的对接线上是否有其他的皇后
int left(int a[][99],int row,int col)
{
int i;
for(i=0;i<8;i++)
{
if(((row+i)<8)&&((col+i)<8))
{
if(a[row+i][col+i]==1)
{
return 1;
}
}
if(((row-i)>=0)&&((col-i)>=0))
{
if(a[row-i][col-i]==1)
{
return 1;
}
}

}
return 0;
}
//判断左下到右上的对接线上是否有其他的皇后
int right(int a[][99],int row,int col)
{
int i;
for(i=0;i<8;i++)
{
if(((row+i)<8)&&((col-i)>=0)) //
{
if(a[row+i][col-i]==1)
{
return 1;
}
}
if(((row-i)>=0)&&((col+i)<8)) //这儿的判断有问题，
{
if(a[row-i][col+i]==1)
{
return 1;
}
}

}
return 0;
}

Answer 2

#include "stdio.h"
#include "windows.h"
#define N 8 /* 定义棋盘大小 */
int place(int k); /* 确定某一位置皇后放置与否，放置则返回1，反之返回0 */
void backtrack(int i);/* 主递归函数，搜索解空间中第i层子树 */
void chessboard(); /* 每找到一个解,打印当前棋盘状态 */
static int sum, /* 当前已找到解的个数 */
x[N]; /* 记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i]列 */
int main(void)
{
backtrack(0);
system("pause");
return 0;
}
int place(int k)
{
/* 测试皇后k在第k行第x[k]列时是否与前面已放置好的皇后相攻击。 x[j] == */
/* x[k] 时，两皇后在同一列上；abs(k - j) == abs(x[j] - x[k]) 时，两皇 */
/* 后在同一斜线上。两种情况两皇后都可相互攻击，故返回0表示不符合条件。*/
for (int j = 0; j < k; j ++)
if (abs(k - j) == abs(x[j] - x[k]) || (x[j] == x[k])) return 0;
return 1;
}
void backtrack(int t)
{
/* t == N 时，算法搜索至叶结点，得到一个新的N皇后互不攻击的放置方案 */
if (t == N) chessboard();
else
for (int i = 0; i < N; i ++) {
x[t] = i;
if (place(t)) backtrack(t + 1);
}
}
void chessboard()
{
printf("第%d种解法:\n", ++ sum);
for (int i = 0; i < N; i ++) {
for (int j = 0; j < N; j ++)
if (j == x[i]) printf("@ ");
else printf("* ");
printf("\n");
}
printf("\n");
}

Answer 3

这个题目用递归的方法呢，想楼上的那样。