蓝桥杯基础练习 - 2n皇后问题解析

蓝桥杯基础练习 - 2n皇后问题解析

问题描述

        给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

---

解题思路：         本题有两个主要难点：（一）判断某个棋盘位置能否放置皇后。思路是通过对某一个位置的行标列标的增减，来访问它所在行所在列所在对角线的其它位置的元素，如果其它位置存在不为1的元素。则不能放置皇后；（二）模拟所有可能的放法，并找到成功放完所有皇后的放法，解决这一点需要用到递归函数（详细见代码）。

        本文定义了两个函数解决上述两个难点。

完整代码如下

---

# 2022.1.6
# 蓝桥杯基础练习
# 试题名称：2n皇后问题
# 问题描述：给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。
# 现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后
# 都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在
# 同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

# board是棋盘，row是二维列表的行标，col是列标，flag 是皇后的类型，2代表黑皇后，3代表白皇后
def able(board, row, col, flag):   # 此函数判断某位置是否能放置皇后
    a = row
    b = col
    for x in range(len(board)):    # 检查对应列
        if(board[x][col] == flag):
            return False
    while((a>=0) & (b>=0)):        # 检查左上角
        if(board[a][b] == flag):
            return False
        a -= 1
        b -= 1   
    a = row
    b = col
    while((a>=0) & (b<=len(board)-1)): # 检查右上角
        if(board[a][b] == flag):
            return False
        a -= 1
        b += 1 
    return True

def xiaqi(board, n, row, flag): # 递归函数：模拟所有放法。n是棋盘的行数
    global count
    if row == n:                # 当row=n时，说明放了一遍黑（白）皇后，要注意不一定能放完
        if flag == 2:
            xiaqi(board, n, 0, flag+1)
        if flag == 3:               # 放完黑皇后，再放白皇后
            #for x in range(n):
                #print(board[x])    # 打印输出放置成功的棋盘（题目不要求）
            #print()
            count += 1               
    for i in range(n):
        if row == n:
            continue
        if board[row][i] != 1:
            continue
        if board[row][i] == flag:
            continue
        if( able(board, row, i, flag) ):
            board[row][i] = flag         # 放皇后，并做标记，2代表黑皇后，3代表白皇后
            xiaqi(board, n, row+1, flag) # 在该递归分支中，放置下一行的皇后
            board[row][i] = 1            # 回溯

count = 0                 # 放置成功数
n = int(input())
board = [list(map(int, input().split())) for i in range(n)]     # 获取棋盘
xiaqi(board, n, 0, 2)
print(count)

---

运行结果图：

打印输出放置成功的棋盘：

注：2代表黑皇后，3代表白皇后。

---

关于本题时间复杂度的问题：

        在一开始，我定义了多个函数来判断棋盘位置是否能放置皇后，导致提交的代码因为超时不能得到100分，只有80多分，后来我将这多个函数写在一起变成一个函数后，问题成功解决了，代码不再超时，且得到了100分。

        降低时间复杂度的一些方法：

                1. 在不影响功能的前提下，尽可能地降低函数数量，因为调用函数需要花费时间。

                2. 尽可能地减少循环的使用。

                3. 学习更多的算法，减少使用暴力解题法