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

        这题是八皇后问题的变形、八皇后是放一个皇后、本题2n皇后是放两个皇后。

解题思路:

        我们可以先放好一个皇后后再放另一个皇后。在图里可以放皇后的格子为1，所以我们可以将不同皇后设置不同的数字来代表，比如2代表黑皇后，3代表白皇后。我们每放一个皇后时先检查他所在列，和两边的对角线有没有放皇后或者说是不能放皇后，判断条件是格子的数是否为一，不为一则是放了皇后或者是不能放皇后。放完最后一行后、我们在dfs函数里判断当前放的皇后是否是将所有的皇后放完了，我们可以用一个数字s代表当前放的棋子，判断条件是s是否等于最后要放的棋子，如果是则放完了计数器count加一，否则继续放棋子，从第一行开始，传下一个代表棋子的数字参数。看到这再看代码相信就明白了。


参考代码:

n = int(input())
mapL = [list(map(int,input().split())) for _ in range(n)]   #模拟棋盘
count = 0   #计数器
def dfs(row,n,s,mapL):
    global count
    if row == n:    #判断是否是放完了最后一行，注意我的行数是从0开始，0代表第一行
        if s == 2:  #2代表黑皇后，3代表白皇后
            dfs(0,n,3,mapL) #黑皇后放完，开始放白皇后
        if s == 3:  #全部放完
            count += 1
        return
    for i in range(n):
        if mapL[row][i] != 1:   #不为1、说明放了皇后，或者不能皇后
            continue
        if check(row,i,s,mapL):
            mapL[row][i] = s    #可以放，将格子的数字变为放置对应皇后的数字
            dfs(row+1,n,s,mapL)
            mapL[row][i] = 1    #回溯

def check(row,j,s,mapL):
    r = row - 1
    k = j - 1
    for i in range(row-1,-1,-1):    #检查对应列
        if mapL[i][j] == s:
            return False
    while r>=0 and k>=0:    #检查对应左上角
        if mapL[r][k] == s:
            return False
        r -= 1
        k -= 1
    r = row -1
    k = j + 1
    while r>=0 and k<n: #检查对应右上角
        if mapL[r][k] == s:
            return False
        r -= 1
        k += 1
    return True
dfs(0,n,2,mapL)
print(count)