今天写点简单的，C 语言求解八皇后问题，相信学过 C 语言的朋友一定知道这个经典问题吧，解法也是多种，目前主要有回溯，递推两种方法，今天讲回溯 + 递归的求法，效率可能不太高，不过直接易于理解
问题 ： 能不能在一个标准的国际象棋棋盘上放 8 个皇后，使她们相互之间不能互吃具体点就是，在一个 8*8 的棋盘上放皇后，皇后是所有方向上都可以移动的，现在要让她们不能互吃的话就要使得她们不会在同一条线上
具体解法：从第一行第一列的位置开始放棋子（假定列优先），然后记录其占用的行斜直线的编号，然后放第二个棋子，在排除前面所有棋子的所占的编号的情况下选择到有效位置，然后继续，直到放满 8 个棋子为止
代码如下：
/*
* 八皇后算法问题
*author CG
*2008 12 22
*/
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#define N 8 /* 设置皇后数量为 8*/
int a [N], b [2*N + 1], c [2*N +1];/* 三个数组记录各个方向上的皇后 */
int count = 0;/* 计数器 */
int Queen(int row) {
int col; /* 局部变量 */
for (col = 1 ; col < = N ; col++){
if (a[col - 1] + b[row + col - 2] + c[row - col + N - 1] == 0) {
/*
* 这里这部很重要，用于判断皇后位置是否符合条件，只有各个方向的直线上
* 都没有皇后才符合条件
* a [col-1] 记录第 col 列有无皇后，1 表示有。
* b [row+col-2] 记录从左上数第 row+col-1 条斜率为 1 的线上有无皇后。
* c [row-col+N-1] 记录从右上数第 row-col+N-1 条斜率为 -1 的线上有无皇后。
*/
a [col - 1] = 1; /* 更改数据 */
b[row + col - 2] = 1;
c[row - col + N - 1] = 1;
gotoxy(col \* 2 , row);/\* 画皇后 \*/
putch('Q');
if (row < N){/\*如果没有遍历所有row\*/
Queen(row + 1); /\*继续\*/
}
else {/\*递归结束\*/
count++; /\*计数器+1\*/
gotoxy(1 , N + 2);
printf("Solution No %d ", count);
getch();
}
a\[col - 1\] = 0; /\* 清空数据 \*/
b\[row + col - 2\] = 0;
c\[row - col + N-1\] = 0;
gotoxy(col \* 2 , row); /\* 清除图象 \*/
putch('.');
}/\*if \*/
}/*for */
return 0;
}/*Queen */
int main()
{
int i, j;
clrscr ();/* 清屏 */
for (i = 1 ; i <= N ; i++){/* 画棋盘 */
for(j = 1 ; j <= N ; j++){
gotoxy (i * 2 , j);/* 注意字符占位问题大写 Q 和点号占两个字符位 */
putch('.');
}/*for*/
}/*for*/
Queen (1); /* 开始回溯算法 */
gotoxy (1 , N + 3); /* 显示最后结果 */
printf("%d Solution(s)n", count);
system("pause");
}/*main*/