Question

八皇后问题的C语言代码

在国际象棋中，能否在空棋盘上摆放八个皇后，并使其中任意两个皇后不能在同一行或同一列或同一对角线上，并编写完整的摆放八皇后问题的程序。要求：第一个皇后的起始位置由键盘输入，国际象棋的棋盘为8*8的方格。

Answer 1

#include <math.h>
#include <stdio.h>
#define MAX 8 /* 棋子数及棋盘大小MAXxMAX */
int board[MAX];

/* 印出结果 */
void show_result()
{
int i;
for(i=0;i<MAX;i++)
printf("(%d,%d)",i,board[i]);
printf("\n");
}

/* 检查是否在同一直横斜线上有其它棋子 */
int check_cross(int n)
{
int i;
for(i=0;i<n;i++){
if(board[i]==board[n] || (n-i)==abs(board[i]-board[n]))return 1;
}
return 0;
}

/* 放棋子到棋盘上 */
void put_chess(int n)
{
int i;
for(i=0;i<MAX;i++){
board[n]=i;
if(!check_cross(n)){
if(n==MAX-1) show_result();/* 找到其中一种放法了...印出结果 */
else put_chess(n+1);
}
}
}

void main()
{
clrscr();
puts("The possible placements are:");
put_chess(0);
puts("\n Press any key to quit...");
getch();
return;
}


到底是哪些奇葩老师布置的作业？

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");
}