八皇后问题原理：在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后，因此，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n1×n1，而皇后个数也变成n2。而且仅当 n2 ≥ 1 或 n1 ≥ 4 时问题有解
queen.c（编译环境：Ubuntu18.04 Vim）
代码语言：javascript复制 #include <stdio.h>
#define N 4 //N 皇后问题
int board[N][N]; //棋盘 0表示空白 1表示有皇后
int way; //摆放的方法数
//判断能否在(x,y)的位置摆放一个皇后；0不可以，1可以
int is_feasible(int row, int col)
{
int i;
int j;
//位置不合法
if(row > N || row < 0 || col > N || col < 0)
{
return 0;
}
//该位置已经有皇后了，不能
//在行列冲突判断中也包含了该判断，单独提出来为了提高效率
if(board[row][col] != 0)
{
return 0;
}
//下面判断是否和已有的冲突
//行和列是否冲突
for(i = 0; i < N; i)
{
if(board[row][i] != 0 || board[i][col] != 0)
{
return 0;
}
}
//斜线方向冲突
for(i = 1; i < N; i)
{
/* i表示从当前点(row,col)向四个斜方向扩展的长度
左上角 / 右上角 i=2
/ i=1
/ i=1
左下角 / 右下角 i=2
*/
//左上角
if((row - i) >= 0 && (col - i) >= 0) //位置合法
{
if(board[row - i][col - i] != 0) //此处已有皇后，冲突
{
return 0;
}
}
//左下角
if((row i) < N && (col - i) >= 0)
{
if(board[row i][col - i] != 0)
{
return 0;
}
}
//右上角
if((row - i) >= 0 && (col i) < N)
{
if(board[row - i][col i] != 0)
{
return 0;
}
}
//右下角
if((row i) < N && (col i) < N)
{
if(board[row i][col i] != 0)
{
return 0;
}
}
}
return 1; //不会发生冲突，返回1
}
//摆放第t个皇后 ；从1开始
void queen(int t)
{
int i;
int j;
//摆放完成，输出结果
if(t > N)
{
way ;
#if 0
printf("%dn", way);
/*如果N较大，输出结果会很慢；N较小时，可以用下面代码输出结果*/
for(i = 0; i < N; i)
{
for(j = 0; j < N; j)
{
printf("%-3d", board[i][j]);
}
printf("n");
}
printf("n------------------------nn");
#endif
return;
}
for(i = 0; i < N; i)
{
for(j = 0; j < N; j)
{
//（i,j）位置可以摆放皇后，不冲突
if(is_feasible(i, j))
{
board[i][j] = 1; //摆放皇后t
queen(t 1); //递归摆放皇后t 1
board[i][j] = 0; //恢复
}
}
}
}
//返回num的阶乘,num!
int factorial(int num)
{
if(num==0 || num==1)
{
return 1;
}
return num * factorial(num - 1);
}
//回溯法解决八皇后问题
int main(int argc, char* argv[])
{
int i;
int j;
//初始化
for(i = 0; i < N; i)
{
for(j = 0; j < N; j)
{
board[i][j] = 0;
}
}
way = 0;
queen(1); //从第1个皇后开始摆放
//如果每个皇后都不同
printf("考虑每个皇后都不同，摆放方法：%dn", way); //N=8时, way=3709440 种
//如果每个皇后都一样，那么需要除以 N！出去重复的答案（因为相同，则每个皇后可任意调换位置）
printf("考虑每个皇后都不同，摆放方法：%dn", way / factorial(N)); //N=8时, way=3709440/8! = 92种
return 0;
}
