在n×n的方格棋盘上放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。下图所示为6皇后问题的一个解。
二、问题求解
采用整数q[N]来存放每一个皇后所在的列号，即第i个皇后在(i，q[i])位置上，count_1表示n皇后解的个数。在n皇后求解过程中：
1、确定该皇后是否可以放置，即确定冲突（第一个皇后随意放置）：设上一个皇后位置为(k，q[k])，故不同行：i!=k，不同列：q[i]!=q[k]，不同左右对角线：abs(i - k) == abs(j - q[k])。在这些位置上，皇后不可以放置。
2、递归求解：将大问题转化为小问题，设queen(i，n)是在1~i-1行已经放置了i-1个皇后，用于在i~n行放置剩下的n-i+1个皇后，则queen(i+1，n)表示已经在1~i行上已经放好了i个皇后，用于在i+1~n行放置剩下的n-i个皇后，故queen(i，n)是大问题，queen(i+1，n)是小问题。递归模型如下：
queen(i，n)：n个皇后放置完毕，输出一个解 若i>n;
queen(i，n)：在第i行找到一个位置（i，j）放置皇后；queen(i+1，n) 其他情况
三、代码
#include<iostream> #include<math.h> #define N 20; using namespace std; int q[20]; //存放个皇后所在的列号 int count_1 = 0; //累计解个数 void dispasolution(int n) {//输出n皇后问题的一个解 cout << "第" << ++count_1 << "个解："; for (int i = 1; i <= n; ++i) { cout << "(" << i << "," << q[i] << ") "; } cout << endl; } bool place(int i, int j) {//测试(i,j)位置能否放置皇后（第i行） if (i == 1) return true; int k = 1; while (k < i) { if (q[k] == j || (abs(i - k) == abs(j - q[k]))) {//判断当前位置是否可以放置皇后 return false; } k++; } return true; } void queen(int i, int n) {//放置第i行的皇后 if (i > n) dispasolution(n); //递归出口，输出n皇后 else { //注意：当找到一个解后，遇到递归出口，但j会继续向后遍历，寻找其他解，相当于是递归进去直至最后一行，在返回过程中，发现没有其他解会继续返回，有其他解又会继续递归，直到返回至第一行有其他皇后可以放置在继续递归 for (int j = 1; j <= n; ++j) {//每次放置皇后从左到右依次遍历并判断 if (place(i, j)) { //(i,j)可以放置 q[i] = j; //记录皇后位置 queen(i + 1, n); //递归放置下一行的皇后 } } } } int main() { int n; cout << "皇后问题（n<20）n="; cin >> n; if (n >= 20) cout << "n值太大，不能求解" << endl; else cout << n << "皇后问题求解如下：" << endl; queen(1, n); //放置1~n行的皇后 return 0; }