阅读 429

N皇后问题暴力解和回溯解问题分析和算法实现-leetcode困难难度

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

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

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

可以看到n皇后是leetcode上一道难度为困难的题

基本事实

  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行是否满足条件
	if (ok) {
		ok = is_ok(row + 1);
	}
	
	return ok;
}

void recordAnswer()
{
	vector<string> oneResult;
	for (int i = 0; i < QUEUE_NUM; i ++) {
		string row(QUEUE_NUM, '.');
		row[QUEUE_LIST[i]] = '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;
	}
}

void queue(int row)
{
	for (int i = 0; i < QUEUE_NUM; i ++) {
		QUEUE_LIST[row] = i;
		if (row == QUEUE_NUM - 1) {
			// 找到一个组合,进行判断是否满足8皇后定义
			if (is_ok(0)) {
				// 进行记录
				recordAnswer();
			}
			continue;
		}
		queue(row + 1);
	}
}

int main(int argc, char *argv[]) {
	queue(0);
	printAnswer();
}
复制代码

由于穷举解多出了很多无效的组合,lc上直接超时了...,可以在本地计算机上自行验证

一些注意的点

暴力解是先求出所有的皇后的组合,然后逐个判断皇后是否满足位置条件

回溯解就是在求皇后组合是否满足条件时,提前进行判断,提前剪掉了这部分皇后的组合

回溯法的col, row值从1开始是为了避免usedRowAndCol默认值的0和col, row索引的0冲突,导致的判断异常

参考资料

  1. www.cplusplus.com/reference/c…
  2. zh.wikipedia.org/wiki/八皇后问题
关注下面的标签,发现更多相似文章
评论