【讲座总结】Maigo大神讲八皇后最快解



  • 作者:王赟 Maigo
    链接:https://zhuanlan.zhihu.com/p/22846106
    来源:知乎
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    这是上周 BitTiger 算法讲座「八皇后 + 位运算」的文字整理稿。在讲座中,我讲解了 n 皇后问题的 5 种解法,一种比一种快;从解法三起引入了位运算。讲座的 PPT 和当场使用的 Java 程序已经上传到我的 GitHub:github.com/MaigoAkisame

    当然啦,如果我在这儿写的东西跟讲座里是一模一样的,那就没意思了对吧?所以,本篇专栏我将使用 Python 语言编程。由于 Python 本身比 Java 慢,所以我就用 13 皇后而不是 15 皇后来比较 5 种解法的效率啦。

    简要复述一下 n 皇后问题:在一个 n * n 的棋盘上放置 n 个皇后,要求不能有两个皇后位于同一行、同一列,或同一条 45 度斜线上。问共有多少种放法?(为节省篇幅,本文就不输出每一种放法了)

    解法一:步步回眸

    这是最基本的深度优先搜索(depth first search, DFS)解法,也称为回溯法。用一个数组 sol 记录每一行的皇后放在哪一列,例如 sol[2] = 5 代表第 2 行的皇后放在第 5 列。注意行号和列号都从 0 开始。从上往下依次试探每行的皇后可以放在哪些列;试探一个位置时,要与上方所有已经放好的皇后检查是否冲突。设当前试探的位置为 (row, col),而第 i 行已经有一个皇后放置在 (i, sol[i])。这两个皇后有三种冲突的可能:

    位于同一列(下文也称「竖」):col == sol[i]
    位于同一条从右上到左下的斜线(下文简称「撇」)上:col - sol[i] == row - i
    位于同一条从左上到右下的斜线(下文简称「捺」)上:col - sol[i] == i - row
      此解法的完整 Python 程序如下:

    import time
    
    n = 13                          # 棋盘大小
    sol = [0] * n                   # 已放置的皇后的列号 
    count = 0                       # 解法总数
    
    def DFS(row):                   # 递归函数,试探第 row 行皇后的位置
    global count
    for col in range(n):        # 依次试探每一列
        # 检查冲突
        ok = True
        for i in range(row):
            if col == sol[i] or col - sol[i] == row - i or col - sol[i] == i - row:
               ok = False
               break
        if not ok:
            continue
        # 检查冲突结束
        if row == n - 1:        # 已放到最后一行
            count += 1          # 找到一组解
        else:
            sol[row] = col      # 记录当前行皇后的位置
            DFS(row + 1)        # 继续试探下一行
    

    主程序

    tic = time.time()
    DFS(0)                          # 从第 0 行开始试探
    toc = time.time()
    print "Total solutions: %d" % count
    print "Elapsed time: %f seconds" % (toc - tic)
    

    「检查冲突」那一段也可以写成下面这样:

    if any(col == sol[i] or
       col - sol[i] == row - i or
       col - sol[i] == i - row for i in range(row)): continue
    

    这么写其实是更符合 Python 风格的。但实测这么写跑得比较慢,即使把 range 换成 xrange 也是一样。

    解法一跑得特别慢,解 13 皇后需要 89 秒!为什么会这么慢呢?原因在于,检查冲突时要依次检查上面的每一行,而大部分时间我们会处于搜索树的深处,每次检查冲突的复杂度就是 O(n) 了。能不能在递归的过程中做一些标记,让检查冲突的复杂度降为 O(1) 呢?能!这就是下面的解法二。

    解法二:雁过留痕

    注意到皇后位置的限制条件的本质,其实就是说每一「竖」、每一「撇」、每一「捺」上只能有一个皇后。当试探一个位置时,如果能够立即知道它所在的「竖」、「撇」、「捺」是否已被占用,就可以在 O(1) 的时间内检查冲突了。为此,需要在递归调用 DFS(row + 1) 之前,将刚刚放置的皇后所在的竖、撇、捺标记为已占用,并在调用返回之后清除标记。

    为了明确地指代每一条竖、撇、捺,需要给它们编号。一种编号方式如下图所示。竖一共有 n 条,编号为 0 至 n-1,跟列号相同;撇、捺各有 2n-1 条,编号为 0 至 2n-2。由行列坐标 (row, col) 求撇、捺编号的公式为:

    撇编号:row + col
    捺编号:n - 1 - row + col
      Python 程序如下。为节省篇幅,开头、结尾处次要的语句都省略了,完整程序可参见 GitHub。

    n = 13
    shu = [False] * n               # 每一竖是否被占用
    pie = [False] * (2 * n - 1)     # 每一撇是否被占用
    na = [False] * (2 * n - 1)      # 每一捺是否被占用
    count = 0
    
    def DFS(row):
     global count
     for col in range(n):
        j = row + col; k = n - 1 - row + col    # 当前位置所在的撇、捺编号
        if shu[col] or pie[j] or na[k]:         # 检查冲突
            continue
        if row == n - 1:
            count += 1
        else:
            shu[col] = pie[j] = na[k] = True    # 标记当前竖、撇、捺已被占用
            DFS(row + 1)
            shu[col] = pie[j] = na[k] = False   # 清除标记
    
    DFS(0)
    

    这个程序解 13 皇后只需要 14 秒,比解法一快了很多!

    解法三:以一当百

    解法二使用了三个布尔数组(boolean array),以记录每一条竖、撇、捺是否被占用。这很费空间:每一个布尔变量只携带 1 比特的信息,但一般的编程语言中都会用至少 1 个字节来存储一个布尔变量,有的语言中甚至会使用 4 个字节。能不能真正让一个布尔变量只占用 1 个二进制位呢?这就要用到位运算了。

    位运算是定义在整数上的运算。但在做位运算的时候,并不把整数看作整数,而是把它们看成一系列二进制位,逐位进行运算。位运算有 6 种,它们的名称、运算符及运算规则如下:

    与 (and): 5 & 6 = 4 (101 & 110 = 100)
    或 (or): 5 | 6 = 7 (101 | 110 = 111)
    异或 (xor): 5 ^ 6 = 3 (101 ^ 110 = 011)
    取反 (not / complement): ~5 = -6 (~00000101 = 11111010)
    左移 (shift left): 5 << 2 = 20 (101 << 2 = 10100)
    右移 (shift right): 5 >> 2 = 1 (101 >> 2 = 1)

    略作说明:

    与、或、异或都是二元运算符,逐位进行逻辑运算。
    取反是一元运算符,它把一个整数的所有二进制位都取反。负数在计算中用补码表示,求一个数的相反数的操作是「取反加一」,于是取反本身的效果就是将 x 变成 -1 - x,无论 x 本身的符号如何。
    左移时右侧添零顶位,在左侧不溢出的情况下,左移 k 位相当于乘以 2^k(对正数、负数均适用);
    右移时右侧移出的位均舍弃,左侧则有两种选择。若一律添零顶位,则称为「逻辑右移」;若重复原数的符号位,则称为「算术右移」。算术右移 k 位等价于除以 2^k 再向下取整(对正数、负数均适用)。在有些语言中,逻辑右移和算术右移有不同的运算符;另外一些语言则只有「>>」一个运算符,可以是逻辑右移,也可能是算术右移。
    除取反运算符外,其它运算符(均为二元运算符)可以与赋值运算符「=」构成复合运算符,例如 a &= b 代表 a = a & b。
      有了位运算之后,就可以把一个 32 位整数当作一个长度为 32 的布尔数组来使用了。这也是解法三的名称「以一当百」的来源——当然,「百」字在这里算是夸张。这种用一个整数来代替的布尔数组,一般称为 bit array 或 bit vector。对于 n 皇后问题来说,使用 32 位的 bit array 意味着 n 可以达到 16(此时撇、捺各有 31 条)。如果 n 再大怎么办呢?不怕,我们还有 64 位整型嘛!

    数组的基本操作,就是「写」和「读」嘛。下面我们看一下如何在一个名为 a 的 bit array 中读写特定的位。注意,位的编号是从低位开始数的,且从 0 开始,即最低位为第 0 位。

    把第 i 位置 1:a |= (1 << i)
    把第 i 位置 0:a &= ~(1 << i)
    把第 i 位取反:a ^= (1 << i)
    读取第 i 位的值:(a >> i) & 1

    1 << i 是一个仅有第 i 位为 1、其它位均为 0 的 bit array。它与 a 进行或运算,就可以将 a 的第 i 位置成 1;与 a 进行异或运算,就可以将 a 的第 i 位取反。把 1 << i 取反,就得到一个仅有第 i 位为 0、其它位均为 1 的 bit array;它与 a 进行与运算,就可以将 a 的第 i 位清零,而不影响其它位。读取第 i 位的值更自然的写法是 (a & (1 << i)) >> i —— 用 1 << i 与 a 进行与运算,可以仅保留 a 的第 i 位,然后再把它移到最低位来。容易证明,(a >> i) & 1 这种写法与它等价,但更简洁。

    将解法二中所有与布尔数组有关的操作都改成用位运算来实现,就可以得到解法三:

    n = 13
    shu = pie = na = 0
    count = 0
    
    def DFS(row):
     global count, shu, pie, na
     for col in range(n):
        j = row + col; k = n - 1 - row + col
        if ((shu >> col) | (pie >> j) | (na >> k)) & 1:         # 检查冲突
            continue
        if row == n - 1:
            count += 1
        else:
            shu ^= (1 << col); pie ^= (1 << j); na ^= (1 << k)  # 标记占用
            DFS(row + 1)
            shu ^= (1 << col); pie ^= (1 << j); na ^= (1 << k)  # 清除标记
    
    DFS(0)
    

    注意「检查冲突」的那一行 —— 我们要检查的是 shu 的第 col 位、pie 的第 j 位、na 的第 k 位是否有任意一者为 1,于是我们就把它们统统右移至最低位再或起来。再看「标记占用」和「清除标记」那两行,它们用的都是相同的异或运算,这是因为我们知道在标记占用时对应的位本来为 0,而清除标记时对应的位本来为 1。

    这个程序解 13 皇后用了 24 秒,反倒比解法二慢了。咦?不是听说位运算快吗?其实是这样:解法三虽然使用了位运算,但只使用了 bit array 的基本读写操作,每次只操作 1 位,所以发挥不出位运算的高效。不过,位运算为我们打通了进一步提速的道路,高潮即将到来!

    解法四:弹无虚发

    从解法一到解法三,一直都有同一个限制效率的因素:在搜索树的深处,能够放皇后的位置其实很少了,但我们一直都要试探每一列。能不能直接得知每一行上还有哪些列能够放置皇后,免去这个枚举的过程呢?位运算恰恰提供了这个可能!

    我们来看这个表达式:a & -a。它称为 lowbit 操作,可以提取出 a 中最右边一个 1 的位置。原理如下:

     a = 00110100
    ~a = 11001011
    -a = 11001100
    a & -a = 00000100
    

    「-a」其实是个算术运算,上文中说过,它等于把 a 取反再加 1。观察上面的例子,~a 的各位均与 1 相反,给它加上 1,会导致一系列进位,使得从最低位开始的一串 1 变成 0,而这一串 1 前面的 0 变成 1。比较 a 与 -a 可以发现,它们有且仅有一位同时为 1,而这个 1 恰好是 a 中最右边一个 1 的位置,于是 a & -a 就可以把这个 1 提取出来了。

    lowbit 操作可以用来枚举一个 bit array 中的所有 1:

    while a != 0:
      p = a & -a
      a ^= p
      Do something with p
    

    注意,每枚举一个 1,就要把它从 a 中清除掉,所以这个枚举过程是破坏性的。

    回到 n 皇后问题。当试探到第 row 行时,如果能用一个 bit array 表示出这一行上能放置皇后的位置,就可以用上述循环直接枚举它们,跳过那些已经不能放置皇后的位置了。显然,shu 这个 bit array 中值为 1 的那些位是不能放的。那么 pie 和 na 这两个 bit array 对当前行有什么影响呢?注意到第 row 行的各列对应的撇编号为 row 至 row + n - 1,捺编号为 n - 1 - row 至 2n - 2 - row。如果把 pie 右移 row 位,把 na 右移 n - 1 - row 位,那么它们的最右 n 位中值为 1 的那些位就也不能放置皇后了。把三者或起来再取反:~(shu | (pie >> row) | (na >> (n - 1 - row))),得到的结果中的最右 n 位就代表了能够放置皇后的位置。注意这个结果中,除了最右 n 位以外,左边的位中也会有一些 1,这些 1 是多余的,应当去掉。怎么去掉呢?可以用一个最右 n 位为 1、其它位为 0 的 bit array 与上述结果进行与运算,而这个 bit array 可以用 (1 << n) - 1 这个表达式制造出来。

    于是得到解法四:

    n = 13
    shu = pie = na = 0
    count = 0
    
    def DFS(row):
     global count, shu, pie, na
     available = ((1 << n) - 1) & ~(shu | (pie >> row) | (na >> (n - 1 - row)))
        # 当前行还能放置皇后的列
    while available:    # 枚举可用的列
        p = available & -available
        available ^= p
        if row == n - 1:
            count += 1
        else:
            shu ^= p; pie ^= (p << row); na ^= (p << (n - 1 - row)) # 设置标记
            DFS(row + 1)
            shu ^= p; pie ^= (p << row); na ^= (p << (n - 1 - row)) # 清除标记
    
    DFS(0)
    

    注意「枚举可用的列」的循环代替了原先「枚举每一列」的循环。这种「弹无虚发」的枚举能够大大提高程序的效率。解法四解 13 皇后用时 6.4 秒。而讲座中使用 Java 语言时提速幅度更大,解法三用时 21 秒,解法四则仅用 3 秒!

    从数据结构的视角来看,解法四中的 bit array 是一个集合,它可以在 O(1) 时间内完成下列操作:

    添加、删除元素;
    将所有元素都增大或减小同一个值;
    求集合中的最小元素。
      需要注意的是,O(1) 的时间复杂度是依赖于计算机指令集,或者说依赖于 CPU 的结构的;这种依赖带来的代价,就是集合的内容只能是 0 ~ 31 或 0 ~ 63 的整数。

    解法五:精益求精

    既然走上了追求效率的道路,我们就来榨干最后一滴水。解法四的程序中,仍然有一些浪费运算次数的地方:

    计算当前行可用列的表达式太长;
    清除标记的步骤需要使用两次移位运算和三次异或运算。
      这两个问题可以这么解决:

    把 shu、pie、na 这三个 bit array 由全局变量改成 DFS 函数的形参,就不再需要清除标记了;
    把 pie 和 na 的含义改为「当前行有哪些列所在的撇或捺已被占用」,这样在计算当前行可用列时就不再需要移位运算了。在递归至下一行时,pie 需要右移 1 位 —— 当前行第 3 列所在的撇,是下一行第 2 列所在的撇;同理,na 则需要左移 1 位。

    于是得到解法五的程序。注意主程序调用 DFS 时要提供 shu、pie、na 的初值(全为 0)。

    n = 13
    count = 0
    
    def DFS(row, shu, pie, na):
     global count
     available = ((1 << n) - 1) & ~(shu | pie | na)  # 当前行还能放置皇后的列
     while available:                                # 枚举可用的列
        p = available & -available
        available ^= p
        if row == n - 1:
            count += 1
        else:
            DFS(row + 1, shu | p, (pie | p) >> 1, (na | p) << 1) # 设置标记并移位
    
    DFS(0, 0, 0, 0)
    

    解法五解 13 皇后只需要 3.4 秒钟!

    总结

    从解法一到解法五,我们总共实现了 20 倍以上的提速。提速来自于下面三个步骤:

    解法一(步步回眸)到解法二(雁过留痕):通过设置标记,尽量减少在搜索树深处的工作量;
    解法三(以一当百)到解法四(弹无虚发):跳过不能放置皇后的位置,只枚举可用的位置;
    解法四(弹无虚发)到解法五(精益求精):减少位运算次数。
      在讲座使用的 Java 语言中,提速主要来自于第二项;在本文使用的 Python 语言中,提速主要来自于第一项。另外,从解法二(雁过留痕)到解法三(以一当百),虽然没有提速,但是节省了不少空间。

    除了提高效率以外,位运算还能缩短程序的长度。讲座中使用的 5 个 Java 程序,是一个比一个短的;本文中的 5 个 Python 程序也呈现这一趋势。我在知乎 Matlab 话题下的签名是「更短、更快、更好」,这可以算是我在编程时的座右铭。位运算在 n 皇后问题中的应用,体现了前两条。

    n 皇后问题的优化方法,并不止于位运算。另一个重要的优化方法是利用对称性进行剪枝。比如,由于棋盘是左右对称的,当 n 为偶数时,第一行可以只试探前 n/2 个位置,最后把解法数乘以 2;当 n 为奇数时,也可以先试探前 (n-1)/2 个位置,把解法数乘以 2,再试探第一行中间的位置。这又可以把效率提高一倍。

    关于位运算,我还有几句要说的话:

    位运算的简洁与高效带来的一个代价,就是程序晦涩难读。因此,实际中位运算往往只用在比较底层、极端追求效率的场合,一般场合不要滥用。
    为了解决位运算晦涩难读的问题,有人把本文中介绍的运算包装成了 BitArray 类,读、写、lowbit 等操作作为该类的方法。但这种包装在一定程度上与位运算的初衷南辕北辙 —— 类操作带来的额外开销,足以抵消位运算带来的效率提升。
    位运算符与其它运算符的优先级在不同的编程语言中可能不同,甚至可能出现 == 的优先级比位运算高的情况。为避免麻烦,建议在书写位运算表达式时,不厌其烦地加括号。
      本文的解法五,源自 Matrix67 的博客:位运算简介及实用技巧(三):进阶篇(2),本文相当于详细解说了这种解法想出来的过程。Matrix67 的这一系列博客共有四篇,其中介绍了许多位运算技巧,值得一读。可惜的是,在博客改版的过程中,有一些文章被截断,只剩一半了。

    「^_^」

    讲座视频链接:N皇后速解
    更多精彩内容,欢迎访问官网 BitTiger.io 或关注 “论码农的自我修养” 微信公众号:bit_tiger

    BitTiger太阁最新试听:

    1. 成为全栈工程师,需要具备哪些技能?试听地址

    2. 深入探寻MachineLearning,走上数据科学家之路。试听地址


登录后回复
 

与 BitTiger Community 的连接断开,我们正在尝试重连,请耐心等待