[toc]
回溯可以理解为：通过选择不同的岔路口来通往目的地（找到想要的结果）
每一步都选择一条路出发，能进则进，不能进则退回上一步（回溯），换一条路再试
树、图的深度优先搜索（DFS）、八皇后、走迷宫都是典型的回溯应用
image.png
不难看出来，回溯很适合使用递归
1. 八皇后问题（Eight Queens）
八皇后问题是一个古老而著名的问题
- 在8x8格的国际象棋上摆放八个皇后，使其不能互相攻击：任意两个皇后都不能处于同一行、同一列、同一斜线上
- 请问有多少种摆法？
leetcode上的皇后问题
- leetcode_51_N皇后：https://leetcode-cn.com/problems/n-queens/
- leetcode_52_N皇后 II： https://leetcode-cn.com/problems/n-queens-ii/
1.1 思路
思路一：暴力出奇迹
从 64 个格子中选出任意 8 个格子摆放皇后，检查每一种摆法的可行性
一共 种摆法（大概是
种摆法）
思路二：根据题意减小暴力程度
很显然，每一行只能放一个皇后，所以共有 种摆法（16777216 种），检查每一种摆法的可行性
思路三：回溯法
回溯 + 剪枝
1.2 回溯法解题
在解决八皇后问题之前，可以先缩小数据规模，看看如何解决四皇后问题
image.png
四皇后 – 剪枝（Pruning）
image.png
当q1放到0号位置后，q2本来可以有4中选择，但是根据条件，可以把第二行的0和1减掉，只剩下2和3
代码
import 'dart:math';
class Queens {
List<int> _cols; //数组索引是行号，数组元素是列号
int _ways; //一共有多少种摆法
///
/// Author: liyanjun
/// description: 摆放n个皇后
///
plceQueens(int n) {
if (n < 1) return;
_ways = 0;
_cols = List(n);
_place(0);
print('$n 皇后 一共有 $_ways 摆法');
}
///
/// Author: liyanjun
/// description: 从第[row]行开始摆放皇后
///
_place(int row) {
if (row == _cols.length) {
//已经摆放成功
_ways++;
_shows();
return;
}
for (var col = 0; col < _cols.length; col++) {
if (_isValid(row, col) == true) {
_cols[row] = col; // 在第row行第col列摆放皇后
_place(row + 1);
}
}
}
///
/// Author: liyanjun
/// description: 判断第[row]行第[col]列是否可以摆放皇后
///
bool _isValid(int row, int col) {
for (var i = 0; i < row; i++) {
// 第col列已经有皇后
if (_cols[i] == col) {
// print('$row 行 $col 列 是false');
return false;
}
// 第i行的皇后跟第row行第col列格子处在同一斜线上
//利用数学上斜率，因为是斜线上 所以斜率是 正负1
if (row - i == (col - _cols[i]).abs()) {
// print('$row 行 $col 列 是false');
return false;
}
}
// print('$row 行 $col 列 是true');
return true;
}
_shows() {
print('方法 $_ways :');
for (int row = 0; row < _cols.length; row++) {
String logs = '';
for (int col = 0; col < _cols.length; col++) {
if (_cols[row] == col) {
logs = '$logs Q';
}else{
logs = '$logs .';
}
}
print(logs);
}
print('---------');
}
}
验证一下
main(List<String> args) {
Queens q = Queens();
q.plceQueens(4);
}
打印结果是
方法 1 :
. Q . .
. . . Q
Q . . .
. . Q .
---------
方法 2 :
. . Q .
Q . . .
. . . Q
. Q . .
---------
4 皇后 一共有 2 摆法
Exited
1.2 回溯法解题优化1
_isValid方法每一次都for循环，进行优化
List<bool> _cols;//标记着某一列是否有皇后
List<bool> _leftTop;//标记着某一斜线上是否有皇后（左上角 -> 右下角）
List<bool> _rightTop;//标记着某一斜线上是否有皇后（右上角 -> 左下角）
利用三个变量记录是否有皇后，不用每次遍历
八皇后为例
左上角 -> 右下角的对角线索引：row – col + 7
对应n皇后就是 row – col + n -1
image.png
右上角 -> 左下角的对角线索引：row + col
image.png
代码
class Queens {
int _ways; //一共有多少种摆法
List<bool> _cols; //标记着某一列是否有皇后
List<bool> _leftTop; //标记着某一斜线上是否有皇后（左上角 -> 右下角）
List<bool> _rightTop; //标记着某一斜线上是否有皇后（右上角 -> 左下角）
List<int> _queens;//方便打印 //数组索引是行号，数组元素是列号
///
/// Author: liyanjun
/// description: 摆放n个皇后
///
plceQueens(int n) {
if (n < 1) return;
_ways = 0;
_cols = List<bool>(n);
_queens = List<int>(n);
_leftTop = List<bool>((n << 1) - 1); //2n-1条斜线
_rightTop = List<bool>(_leftTop.length); //2n-1条斜线
_place(0);
print('$n 皇后 一共有 $_ways 摆法');
}
///
/// Author: liyanjun
/// description: 从第[row]行开始摆放皇后
///
_place(int row) {
if (row == _cols.length) {
//已经摆放成功
_ways++;
_shows();
return;
}
for (int col = 0; col < _cols.length; col++) {
if (_cols[col] == true) continue;//这一列
int ltIndex = row - col + _cols.length - 1;
if (_leftTop[ltIndex] == true) continue;//左斜线
int rtIndex = row +col;
if (_rightTop[rtIndex] == true) continue;//有斜线
_cols[col] = true; // 在第row行第col列摆放皇后
_leftTop[ltIndex] = true;
_rightTop[rtIndex] = true;
_queens[row] = col;
_place(row + 1);
//回溯 还原现场
_cols[col] = false; // 在第row行第col列摆放皇后
_leftTop[ltIndex] = false;
_rightTop[rtIndex] = false;
}
}
_shows() {
print('方法 $_ways :');
for (int row = 0; row < _queens.length; row++) {
String logs = '';
for (int col = 0; col < _queens.length; col++) {
if (_queens[row] == col) {
logs = '$logs Q';
}else{
logs = '$logs .';
}
}
print(logs);
}
print('---------');
}
}
这里不就验证了
验证一下
main(List<String> args) {
Queens q = Queens();
q.plceQueens(4);
}
结果
方法 1 :
. Q . .
. . . Q
Q . . .
. . Q .
---------
方法 2 :
. . Q .
Q . . .
. . . Q
. Q . .
---------
4 皇后 一共有 2 摆法
Exited
1.3 回溯法解题优化2
只针对8皇后
因为bool数组，
[true,false,false,false,false,false,false,false]
可以用位运算 10000000表示
- 判断某一位的值，直接&与运算即可，比如
int n = 223;// 11011111
int col = 5;//
int v = 1<<col;// 000100000
print((n & v));//打印的是0
- 把某一位设置1，只需要|或运算即可
- 把某一位设置0，只需要对目标数字取反，然后进行与运算即可
class Queens {
int _ways; //一共有多少种摆法
int _cols; //标记着某一列是否有皇后
int _leftTop; //标记着某一斜线上是否有皇后（左上角 -> 右下角）
int _rightTop; //标记着某一斜线上是否有皇后（右上角 -> 左下角）
List<int> _queens;//方便打印 //数组索引是行号，数组元素是列号
///
/// Author: liyanjun
/// description: 摆放n个皇后
///
plceQueens(int n) {
if (n < 1) return;
_ways = 0;
_cols = 0;
_leftTop = 0;
_rightTop = 0;
_queens = List<int>(n);
_place(0);
print('$n 皇后 一共有 $_ways 摆法');
}
///
/// Author: liyanjun
/// description: 从第[row]行开始摆放皇后
///
_place(int row) {
if (row == _queens.length) {
//已经摆放成功
_ways++;
_shows();
return;
}
for (int col = 0; col < _queens.length; col++) {
int cv = 1 << col;
if ((_cols & cv) != 0) continue;
int lv = 1 << (row - col + 7);
if ((_leftTop & lv) != 0) continue;
int rv = 1 << (row + col);
if ((_rightTop & rv) != 0) continue;
_cols |= cv;
_leftTop |= lv;
_rightTop |= rv;
_queens[row] = col;
_place(row + 1);
//回溯 还原现场
_cols &= ~cv;
_leftTop &= ~lv;
_rightTop &= ~rv;
}
}
_shows() {
print('方法 $_ways :');
for (int row = 0; row < _queens.length; row++) {
String logs = '';
for (int col = 0; col < _queens.length; col++) {
if (_queens[row] == col) {
logs = '$logs Q';
}else{
logs = '$logs .';
}
}
print(logs);
}
print('---------');
}
}
main(List<String> args) {
Queens q = Queens();
q.plceQueens(8);
// print(Short)
}
1.3.1 考虑位运算情况
- 存储的是bool
- bool数组不是很长
2 回溯思路
做题的时候，建议 先画树形图 ，画图能帮助我们想清楚递归结构，想清楚如何剪枝。拿题目中的示例，想一想人是怎么做的，一般这样下来，这棵递归树都不难画出。
在画图的过程中思考清楚：
- 分支如何产生；
- 题目需要的解在哪里？是在叶子结点、还是在非叶子结点、还是在从跟结点到叶子结点的路径？
- 哪些搜索会产生不需要的解的？例如：产生重复是什么原因，如果在浅层就知道这个分支不能产生需要的结果，应该提前剪枝，剪枝的条件是什么，代码怎么写？
网友评论