非常经典的 N 皇后问题。我自己写了个能用的版本,但是没有 LeetCode 论坛上这个人的解法简洁明了。思路倒是一样的。
我一开始尝试优化,进行剪枝减少每次需要搜索的格子,比如正解中的后与后之间一定是一个 “马步”,因此只考虑在一个后被放置之后其他的“马步”位置。 然而这样会漏掉一些解,因为一个正解中不是所有后之间都是 “马步” 联系起来的,而更像在 graph 中多个 strongly connected components 的状态,如图
因此不能单凭“马步”去保证下一个正确的皇后位置,还是要老老实实遍历搜索。
在每步遍历搜索中, 都要 call 一次 isValid() 函数来判断当前格子是否有效,在 dfs + backtracking 的结构不变的情况下,isValid()函数的性能就会成为程序的瓶颈。
一个比较简单直接的办法是,维护一个 list 代表当前的皇后位置(每一个位置都是valid)在考虑增加新一个王后时,和 list 里已有的每一个皇后比较是否 valid. 问题在于这个 list 的大小是和我们的棋盘大小 n 成正比的,假设一个 list 从0个皇后一直增加到n个皇后,在这个过程中要进行 1 + 2 + 3... + n = O ( n 2 ) 1 + 2 + 3 ... + n = O(n^2) 1 + 2 + 3... + n = O ( n 2 ) 次 isValid 操作。
所以一个更取巧的方式是,利用一个皇后会占用这个格子的所有行,列以及对角线的特点,维护所有“行,列,45度对角线,135度对角线” 的 boolean array,这样在每次考虑一个新位置的时候,只需要 O ( 1 ) O(1) O ( 1 ) 的时间进行一次操作就可以了。
boolean[] 完全可以,Java 的 BitSet 也不错,不过我实际跑的结果来看,BitSet 在用时上会慢一些,原因在这个帖子:
Boolean-vs-bitset-which-is-more-efficient
boolean[] 一个 boolean 占用大约 1 byte 空间(JVM dependent),BitSet 平均占用 1 bit. boolean[] 的优点是更 CPU efficient, 只有在数组非常大(1000w以上)二者的速度持平。BitSet 内部实现是建立 long[] ,用 64-bit 的块去分配 BitSet 的字节。
45度对角线(左上到右下)的 row + column 值是恒等的(一加一减),并且每条对角线的 row + column 值唯一, 在 [ 0 , 1 , 2...2 n − 2 ] [0,1,2 ... 2n - 2] [ 0 , 1 , 2...2 n − 2 ] 区间
135度对角线(左下到右上)的 row - column 值是恒等的(同加同减),并且每条对角线的 row - column 值唯一,在 [ − ( n − 1 ) . . . − 2 , − 1 , 0 , 1 , 2... n − 1 ] [-(n-1) ... -2,-1,0, 1, 2 ... n - 1 ] [ − ( n − 1 ) ... − 2 , − 1 , 0 , 1 , 2... n − 1 ] 区间
边长为 n n n 的棋盘,有 2 n − 1 2n - 1 2 n − 1 条对角线,并且中间值 ( 0 , 0 ) (0,0) ( 0 , 0 ) 的 i n d e x index in d e x 为 n − 1 n - 1 n − 1
Copy public class Solution {
public List < List < String >> solveNQueens ( int n) {
boolean []
//ocp0 = new boolean[n],
ocp90 = new boolean [n] ,
// 总共 2n - 1 种可能性,(0,0) 的 index 是 n - 1
ocp45 = new boolean [ 2 * n - 1 ] ,
ocp135 = new boolean [ 2 * n - 1 ];
List < List < String >> ans = new ArrayList < List < String >>();
char [][] map = new char [n][n];
for ( char [] tmp : map) Arrays . fill (tmp , '.' ); //init
solve( 0 , n , map , ans , ocp45 , ocp90 , ocp135) ;
return ans;
}
private void solve ( int depth , int n , char [][] map , List < List < String >> ans ,
boolean [] ocp45 , boolean [] ocp90 , boolean [] ocp135) {
if (depth == n) {
addSolution(ans , map) ;
return ;
}
for ( int j = 0 ; j < n; j ++ )
// 每次都进行新的一行,所以行不用检查
// 90度代表棋盘的列
// 45度对角线(从左上到右下)同一条线上 row + col 是相等的,因此可用作 index
// 135度对角线(从左下到右上)可从 (0,0) 即 index (n - 1) 为起点
// 因为同一条对角线 row - col 值恒定,可用作 offset 表示对角线的 index.
if ( ! ocp90[j] && ! ocp45[depth + j] && ! ocp135[j - depth + n - 1 ]) {
ocp90[j] = true ;
ocp45[depth + j] = true ;
ocp135[j - depth + n - 1 ] = true ;
map[depth][j] = 'Q' ;
solve(depth + 1 , n , map , ans , ocp45 , ocp90 , ocp135) ;
ocp90[j] = false ;
ocp45[depth + j] = false ;
ocp135[j - depth + n - 1 ] = false ;
map[depth][j] = '.' ;
}
}
private void addSolution ( List < List < String >> ans , char [][] map) {
List < String > cur = new ArrayList < String >();
for ( char [] i : map) cur . add ( String . valueOf (i));
ans . add (cur);
}
}
很可惜,这题解与解之间不存在 optimal substructure 可以有效利用记忆化搜索。老老实实的 DFS + backtracking 还是必要的。有一些比较妖孽的解法比如 Kunth's 的 Dancing Links ,刷题面试的时候,这种大招还是没必要去开了。
既然不需要输出最终解,也就省去了传递 rst 和把棋盘转成 String 的过程。一个问题是,如何在这种dfs + backtracking中维护一个 primitive type 变量,比如有效解的总数?
Java 中默认 primitive type 是 pass by value,而且 Integer type 虽然作为一个 object 存在但是是 immutable, 不能用来作为全局参数多个函数共同更新。
直接建全局变量太蠢了,也不好看。
只求解的数量时,可以让 dfs 函数直接返回 int,每次迭代的时候把其他迭代的返回结果加起来就好了。
Copy public class Solution {
public int totalNQueens ( int n) {
return dfs( 0 , n , new boolean [n] , new boolean [ 2 * n - 1 ] , new boolean [ 2 * n - 1 ]) ;
}
private int dfs ( int row , int n , boolean [] cols , boolean [] diag45 , boolean [] diag135){
if (row == n){
return 1 ;
}
int solutionCount = 0 ;
for ( int col = 0 ; col < n; col ++ ){
if ( ! cols[col] && ! diag45[row + col] && ! diag135[row - col + n - 1 ]){
cols[col] = true ;
diag45[row + col] = true ;
diag135[row - col + n - 1 ] = true ;
solutionCount += dfs(row + 1 , n , cols , diag45 , diag135) ;
cols[col] = false ;
diag45[row + col] = false ;
diag135[row - col + n - 1 ] = false ;
}
}
return solutionCount;
}
}