蓝桥杯基础练习VIP-2n皇后问题-题解（Python代码）

解题思路:
这道题在递归问题上是十分经典的，而在学习写这道题之前，非常有必要了解8皇后问题
注意事项:
代码已贴出可能有疑惑的自我理解

8皇后与2n皇后解题思路基本一致，仅个别有所出处
参考代码:

八皇后问题（英文：Eight queens），是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。

问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。

```python
def queen(A, cur=0):  # cur表示当前行数下标，A储存每行有皇后的列的下标
   global count
   if cur == len(A):  # 溢出棋盘边界，跳出递归判断
       print(A)  # 打印位置
       count += 1  # 可能+1
       return 0  # 跳出本次递归
   for col in range(len(A)):  # col表示当前列下标，从第一行到最后一行遍历
       A[cur], flag = col, True  # 存储当前列下标，暂时判定可以放置皇后
       for row in range(cur):  # 遍历前cur行
           if A[row] == col or abs(col - A[row]) == cur - row:  # 判断放置皇后条件，不可放置if语句生效。A[row]==col表示之前已有皇后不可在此列放置，
                                                                   abs(col-A[row])==cur-row对当前行相对于第cur+1行（cur表示下标所以+1）已有皇后
                                                                   的两斜向位置是否可以放置
               flag = False  # 不可以放置皇后
               break  # 跳出for循环
       if flag:  # 判断是否可以放置皇后
           queen(A, cur+1)  # 可以放置皇后进行下一行皇后的判断
count = 0  # 初始化可能数
queen([None]*8)  # 调用递归函数并赋值棋盘最大行
print(count)  # 打印总的可能个数

```


```python
def black_queen(k):  # 定义黑皇后递归函数，k为行下标
   global count  # 定义全局变量
   for q in range(k - 1):  # 循环遍历前k-1列，判断是否可以放置黑皇后
       judge = b_queen[q] - b_queen[k - 1]  # 第q+1行与第k行列下标差值
       if judge == 0 or k - 1 - q == abs(judge):  # judge == 0重复放置同一列，k - 1 - q == abs(judge)黑皇后位置在同一斜线上
           return  # 此可能性不成立跳出递归
   if k == n:  # 溢出棋盘边界
       count += 1  # 放置皇后可能性+1
       return  # 跳出递归
   for q in range(n):  # 从第一列遍历到最后一列
       if q != w_queen[k] and chessboard[k][q] == 1:  # q != w_queen[k]与白皇后第k+1行列下标相同不可再放置黑皇后，
                                                       # chessboard[k][q] == 1棋盘位置条件位置为1可以放置皇后
           b_queen[k] = q  # 存储当前黑皇后列下标
           black_queen(k + 1)  # 进行下一行皇后的判断递归


def white_queen(k):  # 定义白皇后递归函数，k为行下标
   for p in range(k - 1):  # 循环遍历前k-1列，判断是否可以放置白皇后
       judge = w_queen[p] - w_queen[k - 1]  # 第q+1行与第k行列下标差值
       if judge == 0 or k - 1 - p == abs(judge):  # judge == 0重复放置同一列，k - 1 - q == abs(judge)白皇后位置在同一斜线上
           return  # 此可能性不成立跳出递归
   if k == n:  # 溢出棋盘
       black_queen(0)  # 白皇后放置完成，进行黑皇后放置递归
       return  # 跳出递归
   for p in range(n):  # 从第一列遍历到最后一列
       if chessboard[k][p] == 1:  # chessboard[k][q] == 1棋盘位置条件位置为1可以放置皇后
           w_queen[k] = p  # 存储当前白皇后列下标
           white_queen(k + 1)  # 进行下一行皇后的判断递归
```
```python
n = int(input())  # 输入n表示棋盘大小
count = 0  # 放置皇后可能性
chessboard = [[] for _ in range(n)]  # 棋盘
for i in range(n):  # 循环得到棋盘位置是否可以放置皇后的条件
   arr = input().split()  # 能否放置皇后
   for j in range(n):  # 循环设置棋盘
       chessboard[i].append(int(arr[j]))  # 对棋盘设置1/0
w_queen = [0 for _ in range(n)]  # 初始化白皇后位置列下标
b_queen = [0 for _ in range(n)]  # 初始化黑皇后位置列下标
white_queen(0)  # 以白皇后为起始进行递归，0为行下标
print(count)  # 打印所有放置皇后的可能数值

```