题目

在一张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