n皇后问题是经典的回溯解题的案例，回溯一般用在有多个解的算法中，回溯的核心是穷举，一般通过必要的减枝提高效率(减少重复计算等)，得到一个解后，把当前解进行保存，然后将当前解标记为未解决，继续尝试下一个可能满足条件的解，即回溯

穷举解有利于理解问题的本质，回溯解提高解题效率

题目参考：leetcode-cn.com/problems/n-…

基本事实

1. 皇后的个数和行数相等

2. 每行必定有且只有一个皇后, 如果用row1, row2表示两个皇后所处的行，必定存在row1 != row2

3. 两个皇后必定存在不在同一条斜线上, [row1, col1], [row2, col2]，

   必定存在 | row1 - row2 | != | col1 -col2 |

   或者 左右对角线分开判断 左对角线 row1 - col1 == row2 - col2 右对角线 row1 + col1 = row2 + col2

4. 两个皇后必定不在同一列上，必定存在col1 != col2

5. 要找到所有皇后的集合，必定在找到满足的一个皇后后，不能停，需要继续查找下一个皇后

满足以上条件，即可求得n皇后的解

回溯解

#include <iostream>
#include <vector>
#include <cmath> 

using namespace std;

#define QUEUE_NUM 8

int usedRowAndCol[QUEUE_NUM + 1] = {0}; // 已经使用的行和列, 0表示未使用，有值表示列值, 键是行 值是列

vector< vector<string> > result; // 存储n皇后所有可能结果

void findAQueue(int);
void recordAnswer();
void printAnswer();

void findAQueue(int row)
{
	// row这行肯定是可以用的，主要是获取可用的列，列也有8列，所以进行穷举, 判断row行的col列是否可用
	for (int col = 1; col <= QUEUE_NUM; col ++) {
		// 检查列是否可用 1. 两个皇后必定不在同一列上，必定存在col1 != col2
		// 2. 两个皇后必定存在不在同一条斜线上, [row1, col1], [row2, col2]，必定存在 | row1 - col1 | != | row2 -col2 |
		// 判断当前行的，当前col列在不在对角线上已经占用了
		bool canPlaceInThisCol = true;
		for (int currentRow = 1; currentRow < row; currentRow ++) {
			// currentRow行的col列用过了
			if (usedRowAndCol[currentRow] == col) {
				canPlaceInThisCol = false;
				break;
			}
			
			// 左对角线有用过了
			if (currentRow - usedRowAndCol[currentRow] == row - col) {
				canPlaceInThisCol = false;
				break;
			}
			// 右对角线是否用过了
			if (currentRow + usedRowAndCol[currentRow] == row + col) {
				canPlaceInThisCol = false;
				break;
			}
		}
		if (canPlaceInThisCol) {
			// 列可用，进行记录
			usedRowAndCol[row] = col;
			// 找下一行的那列可以使用
			if (row < QUEUE_NUM) {
				findAQueue(row + 1);
			}
			if (row == QUEUE_NUM) { // 如果当前是最后一行了，就不用再继续找了，记录答案
				recordAnswer();
			}
		}
	}
}

void recordAnswer()
{
	vector<string> oneResult;
	for (int i = 1; i <= QUEUE_NUM; i ++) {
		string row(QUEUE_NUM, '.');
		row[usedRowAndCol[i] - 1] = 'Q';
		
		oneResult.push_back(row);
	}
	result.push_back(oneResult);
}

void printAnswer()
{
	for (int i = 0; i < result.size(); i ++) {
		for (int j = 0; j < result[i].size(); j ++) {
			cout << result[i][j] << endl;
		}
		cout << "---------sep----------" << endl;
	}
}

int main(int argc, char *argv[])
{
	findAQueue(1);
	cout << result.size() << endl;
}
复制代码

这里为了提高代码的可读性，使用了分别排除左对角线和右对角线的方法排除皇后，也可以直接使用绝对值方法

把代码稍作修改填到leetcode上即可

暴力解

排列出所有的组合，挨个判断每个组合是否满足n皇后的条件

#include <iostream>
#include <vector>

using namespace std;

#define QUEUE_NUM 4

int QUEUE_LIST[QUEUE_NUM];

vector< vector<string> > result; // 存储n皇后所有可能结果

bool is_ok(int row)
{
	if (row == QUEUE_NUM - 1) {
		return true;
	}
	
	int first = QUEUE_LIST[row];
	bool ok = true;

	for (int currentRow = row + 1; currentRow < QUEUE_NUM; currentRow ++) {
		// 不能在同一列
		if (QUEUE_LIST[currentRow] == first) {
			ok = false;
			break;
		}
		// 左对角线有用过了
		if (currentRow - QUEUE_LIST[currentRow] == row - first) {
			ok = false;
			break;
		}
		// 右对角线是否用过了
		if (currentRow + QUEUE_LIST[currentRow] == row + first) {
			ok = false;
			break;
		}
	}
	
	// 检查 row + 1行和 row + 2 -> QUEUE_NUM行是否满足条件
                            

                            






                            

                                请到「今天看啥」查看全文