N 皇后问题之位运算解法

​上一篇写了N皇后问题的解法，文末有提到运用位运算的方式来解会更高效，使用位运算有剪枝的效果，不需要再判断位置的合法性。这篇就接上期文章，来填一下位运算解法的坑。



开始分析解法之前，先把几个要用到的重要的位运算的概念提出来，再来看位运算的解法就会清楚很多。



基本的位运算操作，与、或、非、左移、右移，就不详细说了，这几个基本操作在解法中都有用到。



重点介绍两个位运算的应用，就此题，我们要针对的数都是正整数，这样理解起来更简单一些。一个是取一个数右边第一个非0位，也就是提到这个数最右边的1所在位表示的数。我们先给出公式，再详细说一下是为什么，公式如下：

rightmost = num & -num



通过举例来说明这个计算过程，比如7，图示如下：





上图的过程说明，7的二进制表示是0……0111；最左一位是符号位，其负数的表示在计算机中是用补码表示，补码等于反码加1，最后得到的结果就是0……0001，得到的数就是其最右非0位表示的数值，这里得到1。



同样，例如8，根据上述过程得到的结果还是8，最右非0位在右边数第4位，表示的数是2的3次方。



对于补码就是反码加1这个描述可能并非很严谨，但我们知道利用这个原理可以得到num & -num是得到最右非0位表示的数就好。



另一个位运算的应用是将一个数的最右非0位变0，也就是让其二进制表示的最右边的1变为0。还是先给出公式：

dropRightmost = num & (num - 1)



num - 1从位运算来讲就是将其右边开始到第一个非0位都求反。继续通过举例说明，比如7，图示如下：





7的二进制表示是0……0111，那么7 - 1的二进制表示就是0……0110，与之后得到0……0110，即将最右的非0位变为0。



同样，例如8，8的二进制表示是0……1000，那么8 - 1的二进制是0……0111，与之后得到0……0000，唯一的1变为0。



这两个计算方式将用来确定当前行最右边的合法穴位，以及是否还有合法的穴位，是在列遍历过程中剪枝和结束的关键条件。



两个关键的位运算解释过了，现在就进入正题，N皇后的位运算解法。我们用位运算主要是替代之前的位置合法性判断，而解法本质并没有变化，所以框架仍然是深度优先搜索，即DFS。接下来我们用图来表示一下位运算在解题上的应用原理，关键就在于将棋盘二进制化，将有皇后的位置用1表示，空位用0表示。



引入变量：同之前的解法类似，我们需要定义几个参数来表示当前棋盘搜索到某一行时被占用的情况，而占用情况使用列、斜边、反斜边三个整形变量来表示。再加上要打印结果，所以需要一个存储合法列的有序结构。变量命名为 col，slash，backslash，cols。分析过程如下：





主要的计算步骤解释后，给出代码，代码框架与上一篇是几乎相同的，可以在文末链接阅读上篇。这里给出位运算的实现如下：

public void solveNQueens(int n) {
    dfs(n, 0, 0, 0, new ArrayList<>());
}
private void dfs(int n, int col, int slash, int backslash, List<Integer> cols) {
    if (cols.size() >= n) {
        printOneBitSolver(cols);
        return;
    }
    int currentState = (~(col | slash | backslash)) & ((1 << n) - 1);
    while (currentState > 0) {
        int currentCol = currentState & -currentState;
        cols.add(currentCol);
        dfs(n, col | currentCol,
                (slash | currentCol) << 1, (backslash | currentCol) >> 1, cols);
        //这里实际上每次都是移除最后一个元素，所以也可以用
        //cols.remove(cols.size() -1) 实现
        cols.remove(Integer.valueOf(currentCol));
        currentState &= currentState - 1;
    }
}
private void printOneBitSolver(List<Integer> cols) {
    for (int col : cols) {
        String line = "";
        for (int i = cols.size(); i > 0; i--) {
            line += ((1 << (i - 1)) & col) > 0 ? "Q " : ". ";
        }
        System.out.println(line);
    }
    System.out.println();
}



这里看到我们打印结果的函数与上一篇有些不一样，因为这里存入cols的列值实际是用二进制来表示“Q”在某行的放置情况，因此打印也逐位判断，是1的就为“Q”，0的就为“.”。



当然如果不使用位运算，想转换为实际表示该行皇后放置的列序号，可以用如下方法转换后，再使用原来的打印函数进行打印，转换如下：

private List<Integer> convertBitColsToIntCols(List<Integer> cols) {
    List<Integer> res = new ArrayList<>();
    int n = cols.size();
    for (Integer col : cols) {
        res.add(n - 1 - (int) (Math.log(col) / Math.log(2)));
    }
    return res;
}



其中

Math.log(col) / Math.log(2)



正是通过转换成求以2为底的对数来得到真实的列值。



到这里用位运算的解法就实现出来了。从分析的过程中可以看到，通过位运算来计算每行的占用情况，可以直接把不符合条件的位置剔除，从而大大减少了要遍历的次数，效率上要较上篇的方法快不少。



相关主题：

N皇后问题

两边夹的应用三

两边夹的应用二

两边夹的应用