好久没聊算法啦!这次我们来聊聊n皇后问题。n 皇后问题,研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。好多同学对这样的问题都比较慌张,觉得规则多烧脑抗拒,祈祷面试中不要遇到,别急,我们今天就来尝试把这其中的逻辑给说道说道。
一个皇后可以向水平、垂直以及向斜对角方向移动,如果一个皇后出现在另一个皇后的同一行,同一列或者斜对角,那它就可以被这个皇后攻击。
那我们直觉里的一个比较粗暴的办法,就是列举出在棋盘上所有的情况,然后我们判断每个组合是不是符合我们的条件。但是实际上我们不需要尝试所有的组合,我们知道当我们在某一列上放置了一个皇后之后,其它的皇后就不能放在这一列了,在它的同一个水平线上跟四个斜对角也放不了。这样我们可以最早发现“此路不通”。
当我们发现一条路行不通时,我们赶紧回到前面一步,然后尝试另外一个不同的选择,我们称之为回溯
。
针对n皇后问题我们把这个思路再展开一下:
是不是还觉得有点抽象?
那我们拿其中一个场景来具体说说:
棋盘,X代表一个皇后
现在是不是觉得眼睛会了??,接下来我们可以让手来试试了。
首先我们需要一个方法来判断某一个位置能不能放皇后,这样如果一个位置会被棋盘上已有的皇后攻击的话,我们可以直接跳过这个位置:
// 这个方法用来判断我们接下来要放置的皇后在不在某个已经放置的皇后的水平方向、垂直方向或者斜对角,
// 如果都不,那我们找到了一个合适的位置来放一个新皇后了
static boolean isValidPosition(int proposedRow, int proposedCol, List<Integer> solution) {
//对当前棋盘上的所有皇后,我们都要做判断
for (int oldRow = 0; oldRow < proposedRow; ++oldRow) {
int oldCol = solution.get(oldRow);
int diagonalOffset = proposedRow - oldRow;
if (oldCol == proposedCol ||
oldCol == proposedCol - diagonalOffset ||
oldCol == proposedCol + diagonalOffset) {
return false;
}
}
return true;
}
有了这个方法之后,我们就需要实现逐行搜索以及在所有路不通时回到前一行的搜索里面来,继续寻找其它可能性。每一行的搜索方式都一致,所以这边适合使用递归来实现我们的逻辑:
static void solveNQueensRec(int n, List<Integer> solution, int row, List<List<Integer>> results) {
// 最后一行也找到了一个合适的位置,我们成功找到了一种解决方案
if (row == n) {
results.add(new ArrayList<Integer>(solution));
return;
}
// 从每一行的第一列开始尝试
for (int i = 0; i < n; ++i) {
// 对于走到最后一列还没都没有找到合适的点的情况, 当前递归结束,调用栈回到上一层的递归流程,会回去执行前面一行里剩余的情况
if (isValidPosition(row, i, solution)) {
solution.set(row, i);
solveNQueensRec(n, solution, row + 1, results);
}
}
}
当有条路走不通时,调用栈里当前递归就执行结束了,它会回到上一个递归的调用逻辑里,也就实现了我们的回溯
。我们的目的很简单,这一行走到最后没路走了,就继续回到前一行继续往后走,直到所有的路都尝试过。
最后执行一下我们的递归函数就好啦:
static int solveNQueens(int n, List<List<Integer>> results) {
List<Integer> solution = new ArrayList<Integer>(n);
for (int i = 0; i < n; ++i) {
solution.add(-1);
}
solveNQueensRec(n, solution, 0, results);
return results.size();
}
这边相当于从N×N的数组里,选出N个数,时间复杂度是O(n^n)
,而空间复杂度是O(n!)
。
上面我们搜索的过程中,一行一行上升去寻找合适的位置,然后在某个条件下又回到前一行,有点像栈的入栈出栈操作,其实我们也是可以用栈来实现整个回溯过程的。我们在某一行里找到一个合适的位置时就把它的列push
到栈中,回溯到前一行时再把它pop
出来。
// 这边栈里我们只存放列的值
static int solveNQueens(int n, List<List<Integer>> results) {
List<Integer> solution = new ArrayList<Integer>(n);
Stack<Integer> solStack = new Stack<Integer>();
for (int i = 0; i < n; ++i) {
solution.add(-1);
}
int row = 0;
int col = 0;
while(row < n){
while(col < n){
// 当前可以放置皇后,继续下一行的寻找
if(isValidPosition(row, col, solution)){
solStack.push(col);
solution.set(row, col);
row++;
col = 0;
break;
}
// 当前位置不行,尝试在下一列放置皇后
col++;
}
// 找到了当前行的最后一列
if(col == n){
// 说明前面一行还没到最后一列,执行pop操作回到前一行寻找过程
if(!solStack.empty()){
col = solStack.peek() + 1;
solStack.pop();
row--;
}
else{
// 只有第一行也走到了最后一列,并且所有路径都尝试过了,此时由于上面if里的逻辑栈空了,说明我们的寻找过程该结束了
break;
}
}
if(row == n){
// 我们找到一种符合条件的摆放位置
results.add(new ArrayList<Integer>(solution));
// 回溯到前一行
row--;
col = solStack.peek() + 1;
solStack.pop();
}
}
return results.size();
}
时间复杂度是O(n^n)
,空间复杂度是O(n!)
。这边整个逻辑还是比较直接的,我们依旧需要isValidPosition
这个辅助方法来判断某个位置能不能放置皇后,然后对每个位置逐一判断,用栈来配合寻找过程中的回溯操作,核心思想还是不变的。
我们两种办法里都把所有的符合规则的摆放记录下来了,如果我们只需要最后求得有多少种可能性,那我们其实可以把数组换成一个变量来计数,这样我们的空间复杂度可以优化成O(n)
。
好啦,相信大家这会儿对回溯算法
有了一个感性的认识,也能明白回溯
只是我们面对问题时常规的思路,并不是什么高大上的概念,我们不用去畏惧它~