蓝桥杯基础练习VIP-2n皇后问题（Python语言）

解题思路:
先放置黑皇后，黑皇后放置完毕后，在黑皇后已占位的基础上开始放置白皇后，一个回合实际上既包括放置黑皇后也包括放置白皇后，待黑白皇后都放置完毕后，再恢复现场，进入下一轮

参考代码:

from collections import defaultdict
#defaultdict作用与字典相同，但是在字典中没有对应键的时候可以赋予规定的初始值，不会报错，这里填入参数为bool表示初始值为False
def dfs1(index):
    #先放黑皇后
    if n<=0:
        return 0
    if index==n:
        dfs2(0)
        #黑皇后放置完毕，在此基础上，放置白皇后
        return
    for i in range(n):
        if not col1[i] and not dia_10[index+i] and not dia_11[index-i] and board[index][i]=='1':
            #绘图可得，同一主对角线的元素横纵坐标和相同
            #同一副对角线的元素横纵坐标差相同
            col1[i]=True
            dia_10[index+i]=True
            dia_11[index-i]=True
            board[index][i]='0'
            dfs1(index+1)
            #恢复现场，确保寻找下一个正确方案时的初始现场正常
            col1[i]=False
            dia_10[index+i]=False
            dia_11[index-i]=False
            board[index][i]='1'
    return
def dfs2(index):
    #再放白皇后
    global nums
    if index==n:
        nums+=1
        #白黑皇后均可以妥善放置，才能算作一次正确方案
        return
    for i in range(n):
        if not col2[i] and not dia_20[index+i] and not dia_21[index-i] and board[index][i]=='1':
            col2[i]=True
            dia_20[index+i]=True
            dia_21[index-i]=True
            board[index][i]='0'
            dfs2(index+1)
            col2[i]=False
            dia_20[index+i]=False
            dia_21[index-i]=False
            board[index][i]='1'
    return
while True:
    try:
        n=int(input())
        board=[]
        for i in range(n):
            board.append(input().split())
        col1=defaultdict(bool)#黑皇后列
        dia_10=defaultdict(bool)#黑皇后主对角线
        dia_11=defaultdict(bool)#黑皇后副对角线
        col2=defaultdict(bool)#白皇后列
        dia_20=defaultdict(bool)#白皇后主对角线
        dia_21=defaultdict(bool)#白皇后副对角线
        nums=0
        dfs1(0)#从第0行开始放置黑皇后
        print(nums)
    except:
        break