赞
踩
学习回溯法和dfs, N皇后是一个经典问题。
力扣上是这莫描述的:
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上,
并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回 n 皇后问题 不同的解决方案的数量。
不能相互攻击的意思是:
在棋盘中每位皇后,不能再同一行,同一列,同一对角线。
不太熟悉题目的同学,可以点网址进入了解一下:https://leetcode-cn.com/problems/n-queens-ii/
问题要求我们,皇后不能再同一行,同一列,同一对角线。我们先来看看,如何判断皇后是否在同一行 OR 在同一列? 我们可以声明2个数组来解决这个问题
bool col[n], row[n];
col[ i ] 表示 第 i 行是否放了皇后(是否被占用), 我们初始化col[ i ]为 false,表示这一行我们还没有放皇后, 若我们在第 i 行放了一个皇后, 则我们 执行 。
col[ i ] = ture;
这样我们就可以通过col[ i ]的值,来判断 i 行是否被占用。
当然row[i] 表示 第 i 列是否被占用。
再来看看对角线(这个涉及些数学:),对于整个算法来说, 不是很重要~ ),一个棋盘对角线有两条,先来看第一条
我们对棋盘的每一个格子标上序号(二维数组内对应的下标),图上的棋盘的 n = 4。 我们可以发现斜向上方的对角线一共有七条。这里的秘密是 棋盘的斜向上放的对角线 是 2*n - 1条。我们可以声明一个数组 dia1[ i ]来记录每一条对角线是否被占用。
我们可以发现 : 每一条对角线上的 i + j 是固定的值。 我们可以对每一条对角线进行标号,用 i+ j。
这样我们就可以声明一个数组 dia1[ i + j ]来记录第i + j对角线是否被占用。
再来看看第二条对角线:
我们可以发现 每一条对角线上 i - j上的值是固定的。但是我们不能通过 i - j来迅速索引该对角线。因为 i - j 会出现负值。我们不难得出,可以用 i - j + n - 1进行索引。dia[ i - j + n - 1 ]的下标范围 是 【0… n - 1】。合理!
(最麻烦的部分终于结束了,接下来就是算法最精彩的思路了)
思路: 棋盘上的每一个格子, 只有两种状态,放皇后 和 不放皇后(01背包)。那我们直接嘎嘎枚举好了。枚举每一个格子的状态,得到整个棋盘的状态。总有几种状态时我们想要的。看看代码吧~(我给出的时力扣题目的答案)
class Solution { public: //记录行,列,对角线是否被占用的数组们 vector<bool> col, row, dia1, dia2; //res: 合法的摆放策略, nn:皇后总数 int res = 0, nn; //在整个问题中 该函数解决在(x, y)点放皇后的问题 // x 和 y 定位现在枚举到棋盘的那个位置了 // q 表示已经放了皇后的数量 void dfs(int x, int y, int q) { //走到了本行的末尾, 进入下一行 if (y == nn) { x++; y = 0; } //抵达了最后一行, 搜索完毕了。 if (x == nn ) { if (q == nn) { //成功的条件 ,恰好放了 n 个皇后 res++; } return; } //不放皇后, 枚举下一个格子 dfs(x, y + 1, q); // 首先判断该位置的合法性 if (!row[x] && !col[y] && !dia1[x + y] && !dia2[x - y + nn - 1]) { //,若合法, 放皇后 row[x] = col[y] = dia1[x + y] = dia2[x - y + nn - 1] = true; dfs(x, y + 1, q + 1); // 下面的这条语句是回溯的体现。 // 再递归的过程中,如果无法达到成功条件,那么回退,并且从这个格子上撤走皇后 row[x] = col[y] = dia1[x + y] = dia2[x - y + nn - 1] = false; } } int totalNQueens(int n) { //TODO::初始化参数 nn = n; col = vector<bool>(n, false); row = vector<bool>(n, false); dia1 = vector<bool>(2 * n - 1, false); dia2 = vector<bool>(2 * n - 1, false); //TODO::从位置(0, 0)开始枚举, 已经放了 0 个皇后 dfs(0, 0, 0); return res; } };
这样的写法的时间复杂度是 O(n !).这种写法的回溯思想, 体现的不是特别明显。让我们来看看第二种搜索方式。
按行搜索
class Solution { public: //记录行,列,对角线是否被占用的数组们 vector<bool> col, dia1, dia2; //res: 合法的摆放策略, nn:皇后总数 int res = 0, nn; //在整个N皇后问题中,该函数解决在cur行放皇后的问题 void dfs(int cur) { //整个棋盘摆完了 if(cur == nn) { res++; return; } //尝试将皇后放在 cur 行 第 i 列。 for(int i = 0; i < nn; i++) { //放皇后, 首先判断该位置的合法性,有剪枝的作用 if (!col[i] && !dia1[cur + i] && !dia2[cur - i + nn - 1]) { col[i] = dia1[cur + i] = dia2[cur - i + nn - 1] = true; dfs(cur + 1); //回溯的体现,分析一下 /*假设 : 在我们递归搜索到下一行, 我们并没有得到正确的摆放方式, 所以我们回退回来,我们已经知道从该行的 i 格子出发得不到正确答案, 那么我们 i++,去把皇后放到该行的下一个位置。这条语句是解除限制, 可以理解为从 i 位置拿起皇后。在第 i 位置放皇后已然行不通了,去 试试放到i + 1 位置*/ col[i] = dia1[cur + i] = dia2[cur - i + nn - 1] = false; } } } int totalNQueens(int n) { //TODO::初始化参数 nn = n; col = vector<bool>(n, false); dia1 = vector<bool>(2 * n - 1, false); dia2 = vector<bool>(2 * n - 1, false); //TODO::从第 0 行开始 dfs(0); return res; } };
溯的有逆流而上 和 追溯本源 的意思。而我个人最喜欢的算法就是回溯。因为他告诉我就算失败了,这条路走不通,那你也可以换一条路试一试。不断的去摸索,大不了尝试完所有不可能,接下来就是可能。愿你我都有面对失败的运气:)
大家加油!
感谢liuyubobobo老师!
文章有问题 烦请指正 ~
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。