本文主要是介绍[算法入土之路]n皇后问题(位运算加速)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
n皇后问题的算法规模为 O(n^n) 无法改变, 但是我们可以在常数上做优化(通过位运算)
def NQueens(n):'''利用位运算提高运算速率:param n: 几个皇后:return:'''n = (1 << n) - 1 # 生成二进制为 n 个 1 的数字def inner(n_, col, left, right):''':param n_: 总行: 例: 八皇后 n_ = 0」11111111:param col: 列限制:param left: 左斜线限制:param right: 右斜线限制:return: 当前获得解的个数'''if col == n_: # 当绘制完最后一行 得到一个解return 1pos = n_ & (~(col | left | right))'''n」 表示前面无限为都是ncol | left | right -> 0」 0 代表可以放皇后的位置, 1 代表不可以放皇后的位置~ -> 1」 1 代表可以放皇后的位置 0 代表不可以放皇后的位置n_ & -> 0」1 代表可以放皇后的位置 0 代表不可以放皇后的位置'''res = 0 # 解的个数while pos: # 如果还有皇后可以放置的位置cur_loc = pos & (~pos + 1) # 获得最右面的一个1 即从右往左找皇后可以放置的位置pos -= cur_loc # 使当前可以放置皇后的位置变为不可以放置皇后的位置res += inner(n_, col | cur_loc, (left | cur_loc) << 1, (right | cur_loc) >> 1)'''例子: 八皇后最外层第一次循环 八皇后第二层 第一次循环pri_seq 1 1 1 1 1 1 1 1 pri_seq 1 1 1 1 1 1 1 1 # 原始序列 pos 1 1 1 1 1 1 1 1 pos 1 1 1 1 1 1 0 0 # 当前可以放置皇后的位置left 0 0 0 0 0 0 0 0 left 0 0 0 0 0 0 1 0 # 左限制right 0 0 0 0 0 0 0 0 right 0 0 0 0 0 0 0 0 # 右限制cur_loc 0 0 0 0 0 0 0 1 cur_loc 0 0 0 0 0 1 0 0 # 当前获得的可以放置皇后的位置left|cur 0 0 0 0 0 0 0 1 left|cur 0 0 0 0 0 1 1 0 # 左限制与当前皇后位置作 或操作↑ << 1 0 0 0 0 0 0 1 0 ↑ << 1 0 0 0 0 1 1 0 0 # 向左移一位 代表下一行的左限制right|cur 0 0 0 0 0 0 0 1 right|cur 0 0 0 0 0 0 1 0 # 右限制与当前皇后位置作 或操作 ↑ >> 1 0 0 0 0 0 0 0 0 ↑ >> 1 0 0 0 0 0 0 0 1 # 向右移一位 代表下一行的右限制'''return resreturn inner(n, 0, 0, 0)print(NQueens(4))
这篇关于[算法入土之路]n皇后问题(位运算加速)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
