N 皇后及其 Index Trick


N-Queens I

非常经典的 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)$$ 次 isValid 操作。

所以一个更取巧的方式是,利用一个皇后会占用这个格子的所有行,列以及对角线的特点,维护所有“行,列,45度对角线,135度对角线” 的 boolean array,这样在每次考虑一个新位置的时候,只需要 $$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 ... 2n - 2]$$ 区间

  • 135度对角线(左下到右上)的 row - column 值是恒等的(同加同减),并且每条对角线的 row - column 值唯一,在$$[-(n-1) ... -2,-1,0, 1, 2 ... n - 1 ]$$ 区间

  • 边长为 $$n$$ 的棋盘,有 $$2n - 1$$ 条对角线,并且中间值 $$(0,0)$$ 的 $$index$$ 为 $$n - 1$$

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);
    }
}

N-Queens II

很可惜,这题解与解之间不存在 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,每次迭代的时候把其他迭代的返回结果加起来就好了。

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;
    }
}

results matching ""

    No results matching ""