注: 本文参考了rust-n-queens的解决方法, 修整了rust版本升级带来的不兼容问题, 因目的为说明原理, 故不复述多线程具体代码, 只考虑单线程的问题。 关于八皇后的多种解法, 请看用位运算速解n皇后问题, 下文采用的方法即是位运算最快的一种。


0.前言

八皇后问题是回溯算法的经典事例, 即在8×8的国际棋盘上放置八个皇后, 使之不会出现有一个皇后可以直接攻击其他皇后, 换句话说, 就是不会出现两个皇后同时出现在同一行、 同一列、 同一对角线。

一般的暴力解法就是逐个尝试摆放。 以先放置行为例, 在从上到下放置行时, 逐个尝试这一行中的每一列是否满足要求, 判断的方法就是与该行以上(已放置)的皇后位置进行比对, 满足则继续下一行, 不满足则尝试该行下一列。 对这个基本函数进行迭代, 累加解法次数即可。

但因为没有利用每次迭代时尝试的结果, 每次列检验需要从第一列检查, 就造成了大量计算浪费。 要想利用之前尝试失败的经验, 可以设置三个数组, 分别储存列、 左对角线、 右对角线的可用与否, 这是典型的用空间换时间的优化。

不过, 上述所说的三个数组中, 每一项只会表示可用或不可用的二元, 而布尔值用整型来储存就太浪费了, 所以考虑到用二进制位来表示数组的每一项。 这样一来, 三个数组就可以用三个整型数来表示, 但缺点是只能运算小于32个皇后问题。

下文就分析关于使用Rust的位运算解决n皇后问题的程序。


1.Rust程序源码

use std::io;

fn n_queens_helper(all_ones: i32, left_diags: i32, columns: i32, right_diags: i32) -> u32 {
    let mut solutions = 0;
    let mut valid_spots = !(left_diags | columns | right_diags) & all_ones;

    while valid_spots != 0 {
        let spot = -valid_spots & valid_spots;
        valid_spots = valid_spots ^ spot;

        solutions += n_queens_helper(
            all_ones,
            (left_diags | spot) << 1,
            columns | spot,
            (right_diags | spot) >> 1);
    }

    return solutions + ((columns == all_ones) as u32)
}

fn n_queens(n: i32) -> u32 {
    return n_queens_helper((1 << n as u32) -1, 0, 0, 0);
}

fn main() {
    let mut n = String::new();
    io::stdin().read_line(&mut n).expect("Failed to read the number.");
    let answer = n_queens(n.trim().parse().unwrap());
    println!("The {}-queens question\'s answer is: {}.", n, answer);
}

输入想要求解的皇后数n后, 可以得到总共的解法。


2.具体分析

下面就逐行进行解释。

1>第3行

这一行主要解释传入四个参数的意义。 n_queens_helper为主要的迭代函数, 因为本方法基于位运算, 将32位的整型看作一个记录可用性的数组, all_ones是一个右侧有n个1, 左侧全部为0的整型数, 构造这个数是为了在取与时将整型数代表的数组有意义的位控制在低n位, 避免高位的影响。

left_diags和right_diags代表了左对角线(右上至左下)和右对角线(左上至右下)的可用性, columns代表了每一列的可用性, 这三个数的位为1时代表不可用, 这样做可简化计算步骤。 有一点需要解释清楚, 左右对角线的条数实际上分别是2n-1条, 但是left_diags和right_diags的有效位为n, 这时因为它讨论的是具体一行中的可能性, 故一行中的检测只与8条对角线有关, 其他的实际上是不通过该行的。

2>第4行

solution代表解法总数, 随着迭代逐渐相加。

3>第5行

valid_spots这个数的每一位代表了可用的列有哪些。 等号后方首先是三个数取或, 将不可用的列数用1综合起来, 取反后则是1代表可用列数, 最后与all_ones取与后得到低n位的可用列数, 其他位均为0。

4>第7~9行

当存在可用列数时, 进行循环。

spot的意义是该行皇后所尝试的列数, 如00001000代表尝试第四列。 它的取得使用了一个二进制技巧, 一个数的相反数与自身取与, 得到的是自身最低位的1。 一个数取相反数, 就是该数按位取反后加一, 这涉及到补码的知识。 因为之前低位是0的位经取反后变为1, 加一后全部进位, 自然都会加到自身开始为0的那一位上, 该位和右侧的位与本身是一样的, 取与后自然不变, 左侧全部相反, 故全部为0, 最后得到的就是最左侧的那一个1了。

第7行就进行取异或操作, 将该位置从可用位清除掉, 代表已经尝试过了。

5>第11~16行

对n_queens_helper函数进行迭代。

它的参数变了, 我们分别来看。 先看第三个参数columns, 它与spot取或, 就是将spot加入不可用的列数中, 因为spot就是我们这一次尝试的列数。 第二个参数同样如此, 但是向左移1位是因为左对角线在这一行的限制, 到了下一行会向左移一位, 右侧同理。 移进的位用0补齐即可, 因为新移进来的位对下一行并不会有影响。

6>第18行

当行数因为冲突全部不能用(即与all_ones的置1位相等)时, 代表这个方法可行, 计入solutions进行统计。

7>第22行

初始状态都可以用, 所以后三个参数每一位都为0。 第一个参数就是用来构造低n位为1的数的表达式。


3.The End

这种位算法的计算速度很快, 逻辑感极强, 博主花了一下午时间才完全理清, 建议时常拿来锻炼逻辑感(手动滑稽)。

发表评论

电子邮件地址不会被公开。 必填项已用*标注