n皇后问题描述为:在一个nxn的棋盘上摆放n个皇后，要求任意两个皇后不能冲突，即任意两个皇后不在同一行、同一列或者同一斜线上。

 

1,1	1,2	1,3	1,4
2,1	2,2	2,3	2,4
3,1	3,2	3,3	3,4
4,1	4,2	4,3	4,4

上面是4皇后摆放方案，只有两种

寻找皇后摆放方案，可采用回溯法设计策略

算法的基本思想如下:

将第个皇后摆放在第行，从1开始，每个皇后都从第1列开始尝试。尝试时判断在该列摆放皇后是否与前面的皇后有冲突，如果没有冲突，则在该列摆放皇后，并考虑摆放下一个皇后;如果有冲突，则考虑下一列。如果该行没有合适的位置，回溯到上一个皇后，考虑在原来位置的下一个位置上继续尝试摆放皇后，直到找到所有合理摆放方案。

核心代码问题是：如何判断某行某列的位置是否有冲突，即是否有任意两个皇后在同一行、同一列或者同一斜线上

判断是否在同一列上非常好判断，列号相同即为在同一列

是否在同一行没必要判断，因为他是一行一行深度优先遍历的

判断是否处于同一右斜线，由下图可以总结规律两位置的行号加上列号相等，如1+4=2+3

判断是否处于同一左斜线，由下图可以总结规律两位置的行号减上列号相等，如2-1=3-2

queen[i]+i=queen[j]+j和queen[i]-i=queen[j]-j  ===>  queen[i]- queen[j]= j-i和queen[i]- queen[j]= -(j-i)  ====>  abs(queen[i]- queen[j]) = j-i

#include <stdio.h>#define N 4  //N代表皇后个数
int queen[N+1];  //表示皇后所在的位置，如queen[1]=2表示皇后在第一行第二列
int count = 0;void show(){printf("(");for (int i = 1; i <= N; i++){printf("%d ", queen[i]);}printf(")\n");
}int isQueen(int j){  //判断该列能否放置皇后，能放返回1，不能返回0int i;for (i = 1; i < j; i++){   //检查已经摆放好的皇后是否在同一列上或者在同一斜线上if(queen[i] == queen[j] || abs(queen[i]-queen[j]) == j-i){return 0;}}return 1;
}/*** @brief * * @param j 行数，递归时用到* i为列数*/
void Nqueen(int j){int i;for (i = 1; i <= N; i++)  //遍历行,即遍历所有方案，找出可行方案{queen[j] = i;if(isQueen(j)){  //判断该列能否放置皇后if(j == N){  //所有皇后拜访好了，输出摆放方案count ++;show();}else{Nqueen(j+1);  //递归，摆放下一个皇后}}}
}int main(void){Nqueen(1);printf("方案数：%d", count);return 0;
}