n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q…", // 解法 1
“…Q”,
“Q…”,
“…Q.”],
["…Q.", // 解法 2
“Q…”,
“…Q”,
“.Q…”]
]
解释: 4 皇后问题存在两个不同的解法。
1、使用二维数组mark[][]表示一张空的棋盘
设置方向数组： //采用方向数组控制八个方向的切换
(x-1,y-1) (x-1, y) (x-1, y+1)
(x, y-1) (x, y) (x, y+1)
(x, y-1) (x+1, y) (x+1, y+1)

put_down_the_queen()函数的功能就是将皇后放置在坐标（x,y）处，并且对mark数组进行修改，使得该位置的八个方向上所有位置坐标值都为1

void put_down_the_queen(int x int y, vector<vector<int>>& mark)
{
	static const int dx[] = { -1,1,0,0,-1,-1,1,1 };  //方向数组
	static const int dy[] = { 0,0,-1,1,-1,1,-1,1 };
	mark[x][y] = 1;  //(x,y)放置皇后进行标记
	for (int i = 1; i < mark.size(); i++) {
		for (int j = 0; j < 8; j++){  //8个方向，每个方向向外延申1至N-1
			int new_x = x + i * dx[j];
			int new_y = y + i * dy[j];
			if (new_x >= 0 && new_x < mark.size() && new_y >= 0 && new_y < mark.size()) {
				//检查新位置是否还在棋盘内
				mark[new_x][new_y] = 1;
			}
		}
	}
}

回溯算法：
N皇后问题，对于N*N的棋盘，每行都要放置且只能放置1个皇后。利用递归对棋盘的每一行放置皇后，放置时，按列顺序寻找可以放置皇后的列，若可以放置皇后，将皇后放置在该位置，并更新mark标记数组，递归进行下一行的皇后放置；当该次递归结束后，恢复mark数组，并尝试下一个可能放置皇后的列。当递归可以完成N行的N个皇后放置，则将结果保存并返回。

完整程序代码如下：
思路：主函数solveNQueens()函数的功能是输入棋盘大小N，对mark数组和location数组进行初始化，mark数组初始化为全0，代表每个位置都可以放置皇后，location设置为全为点符号，按照leetcode的初始化要求，初次调用函数generate(),对第0行的n列尝试放置皇后，并将修改location和mark数组的状态，不断的尝试递归下一行皇后的放置，但在尝试之前，应该保存该行的location和mark的数组状态，因为如果下一行不能放置皇后，说明该放置路径错误，此时应该进行回溯，回溯到上一行状态（状态已经被保存），然后在上一行的状态下，for()循环至下一列判断能不能再次放置皇后，再次进行递归，直到最终成功放置皇后的列数K == n时，说明皇后被放置完了，此时location中记录着皇后的具体位置，用’Q’表示，mark中除了皇后的位置之外的其他位置变为了全1状态，在其他位置再放置棋子都会被攻击到，此时就只需要Push该location进入result,返回即可。

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;  //储存最终结果的数组
        vector<vector<int>> mark;   //标记棋盘是否可以放置皇后的二维数组      
        vector<string> location;   //存储某个摆放结果，当完成一次递归找到结果后，将location push进入result
        for(int i = 0; i < n; i++){    //每一行进行循环
            mark.push_back(vector<int>());
            for(int j = 0; j < n; j++){   //每一列进行循环
                mark[i].push_back(0);    //将mark二维数组初始化为0
            }
            location.push_back("");  //location中每一行string先设为空
            location[i].append(n,'.'); //再添加n个.进去，完成location的初始化
        }  //初始状态设置结束
        generate(0, n, location, result, mark); 
        return result;
    }
private:
    //放置皇后的函数
    void put_down_the_queen(int x ,int y, vector<vector<int>>& mark){
	    static const int dx[] = { -1,1,0,0,-1,-1,1,1 };  //方向数组
	    static const int dy[] = { 0,0,-1,1,-1,1,-1,1 };
	    mark[x][y] = 1;  //(x,y)放置皇后进行标记
	    for (int i = 1; i < mark.size(); i++) {
		    for (int j = 0; j < 8; j++) {  //8个方向，每个方向向外延申1至N-1
			    int new_x = x + i * dx[j];
			    int new_y = y + i * dy[j];
			    if (new_x >= 0 && new_x < mark.size() && new_y >= 0 && new_y < mark.size()) {
			    //检查新位置是否还在棋盘内
				    mark[new_x][new_y] = 1;
			    }
            }
	    }
    }
    //k代表正在放置第几行皇后
    //将某次结果储存在location中
    //最终结果储存在result
    //mark表示棋盘的标记数组
    void generate(int k, int n, vector<string> &location, vector<vector<string>> &result,                   vector<vector<int>> &mark){
        if(k == n){ //当k == n时，代表完成了第n至第n-1行皇后的位置
            result.push_back(location); //将记录皇后位置的location数组push进入result
            return;
        }
        for (int i = 0; i < n; i++){ //按顺序尝试第0至第n-1列
            if(mark[k][i] == 0){  //表示该位置可以放置皇后
                vector<vector<int>> tmp_mark = mark;  //记录回溯前的镜像
                location[k][i] = 'Q'; //记录当前皇后的位置
                put_down_the_queen(k, i, mark); //放置皇后
                generate(k + 1, n, location, result, mark);  //递归放置下一行皇后的位置
                mark = tmp_mark;   //将mark重新赋值为回溯前状态
                location[k][i] = '.'; //将当前尝试的皇后位置重新置为.
            }
        }
    }
};

测试程序如下：

int main() {
	vector<vector<string>> result;
	Solution solve;
	result = solve.solveNQueens(4);
	for (int i = 0; i < result.size(); i++) {
		printf("i = %dn", i);
		for (int j = 0; j < result[i].size(); j++) {
			printf("%sn", result[i][j].c_str());
		}
		printf("n");
	}
	return 0;
}

著名的八皇后问题，有92种方法，采用递归回溯的方法解决，代码如下，可以和leetcode中的代码进行对比：

#include <conio.h>
#include <iostream>
using namespace std;
//首先要求皇后不冲突，那么每行只应该有一个皇后
//用queens[]数组储存每个皇后的位置
//例如：queens[m] = n表示第m行的皇后放在第n列上
#define MAX 8
int sum = 0;
class QueenPuzzle
{
	int queens[MAX];    //储存每行皇后的列表
public:
	void PrintOut();    //打印结果
	int IsValid(int n);   //判断第n个皇后放上去之后，是否合法
	void PlaceQueen(int i);   //递归算法，放置皇后
};

void QueenPuzzle::PrintOut() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			if (j == queens[i])
				cout << "Q ";
			else
				cout << "0 ";
		}
		cout << endl;
	}
	cout << endl << "按q键退出，按其他键继续" << endl << endl;
	if (_getch() == 'q')
		exit(0);
}
//在第i行放置皇后
void QueenPuzzle::PlaceQueen(int i) {
	for (int j = 0; j < MAX; j++) {
		//如果全部放置完成，则输出结果
		if (i == MAX) {
			sum++;
			cout << "第" << sum << "组解：" << endl;
			PrintOut();
			return;
		}
		//放置皇后
		queens[i] = j;
		//此位置可以放置皇后，就继续实验下一行位置，若不能放置皇后，就递增列数
		if (IsValid(i)) {
			PlaceQueen(i + 1);
		}
	}
}

//判断第n个皇后放上去之后，是否合法
int QueenPuzzle::IsValid(int n) {
	//将第n个皇后的位置依次于前面n-1个皇后的位置比较
	for (int i = 0; i < n; i++) {
		//两个皇后放在同一列上，返回0
		if (queens[i] == queens[n])
			return 0;
		//两个皇后在同一对角线上，返回0
		if (abs(queens[i] - queens[n]) == (n - i))
			return 0;
	}
	//没有冲突，返回1
	return 1;
}

int main() {
	QueenPuzzle queen;
	queen.PlaceQueen(0);
	cout << "共" << sum << "组解" << endl;
}

参考资料：算法之美