苏州公司建设网站制作,生成短链接的网站,网站开发周期安排,聚美优品网站建设主题转载自matrix67 位运算简介及实用技巧#xff08;三#xff09;#xff1a;进阶篇(2)
n皇后问题位运算版 n皇后问题是啥我就不说了吧#xff0c;学编程的肯定都见过。下面的十多行代码是n皇后问题的一个高效位运算程序#xff0c;看到过的人都夸它牛。初始时#…转载自matrix67 位运算简介及实用技巧三进阶篇(2)
n皇后问题位运算版 n皇后问题是啥我就不说了吧学编程的肯定都见过。下面的十多行代码是n皇后问题的一个高效位运算程序看到过的人都夸它牛。初始时upperlim:(1 shl n)-1。主程序调用test(0,0,0)后sum的值就是n皇后总的解数。拿这个去交USACO0.3s暴爽。 procedure test(row,ld,rd:longint); var pos,p:longint; begin { 1} if rowupperlim then { 2} begin { 3} pos:upperlim and not (row or ld or rd); { 4} while pos0 do { 5} begin { 6} p:pos and -pos; { 7} pos:pos-p; { 8} test(rowp,(ldp)shl 1,(rdp)shr 1); { 9} end; {10} end {11} else inc(sum); end; 乍一看似乎完全摸不着头脑实际上整个程序是非常容易理解的。这里还是建议大家自己单步运行一探究竟实在没研究出来再看下面的解说。 和普通算法一样这是一个递归过程程序一行一行地寻找可以放皇后的地方。过程带三个参数row、ld和rd分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。我们以6×6的棋盘为例看看程序是怎么工作的。假设现在已经递归到第四层前三层放的子已经标在左图上了。红色、蓝色和绿色的线分别表示三个方向上有冲突的位置位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来得到该行所有的禁位取反后就得到所有可以放的位置用pos来表示。前面说过-a相当于not a 1这里的代码第6行就相当于pos and (not pos 1)其结果是取出最右边的那个1。这样p就表示该行的某个可以放子的位置把它从pos中移除并递归调用test过程。注意递归调用时三个参数的变化每个参数都加上了一个禁位但两个对角线方向的禁位对下一行的影响需要平移一位。最后如果递归到某个时候发现row111111了说明六个皇后全放进去了此时程序从第1行跳到第11行找到的解的个数加一。
