题目
在一张N∗N的国际象棋棋盘上，放置N个皇后，使得所有皇后都无法互相直接攻击得到，（皇后可以直接攻击到她所在的横行，竖列，斜方向上的棋子），现在输入一个整数N，表示在N∗N的棋盘上放N个皇后，请输出共有多少种使得所有皇后都无法互相直接攻击得到的方案数。 例如下面这样的摆法，是4皇后的一个解 （1代表有皇后，0代表没有）
0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0
分析
题目的意思是如何在一个N*N的网格中摆上N个棋子，规则是任意两个棋子之间不能同行、同列或者同斜线。
代码
基本实现
def nQueen(n): res = 0 if n >= 4: record = [0 for i in range(n)] res += process(0, record, n) return res ## 递归求解 def process(i, record, n): if i == n: return 1 res = 0 for j in range(n): if single(record, i, j): record[i] = j res += process(i + 1, record, n) return res ## 判断该位置是否符合条件 def single(record, i, j): for k in range(i): if record[k] == j or abs(record[k] - j) == abs(k - i): return False return True
位运算优化
def nQueen2(n): res = 0 if n >= 4: limit = -1 if n == 32 else (1 << n) - 1 res += process1(limit, 0, 0, 0) return res def process1(limit, col, left, right): if col == limit: return 1 a = limit & ~(col | left | right) most = 0 res = 0 while a != 0: most = a & (~a + 1) a = a - most res += process1(limit, col | most, (left | most) << 1, (right | most) >> 1) return res
