girl-1162060_1920.jpg

LeetCode 51. N-Queens

Description

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

8-queens.png

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:

Input: 4
Output: [
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

描述

n-queens难题是将n个皇后放置在n×n棋盘上的问题，使得没有两个皇后互相攻击。

给定整数n，返回n-queens拼图的所有不同解。

每个解决方案都包含n-queens位置的独特拼图位置，其中"Q"和"." 两者分别表示女王和空白.

解题

题意理解

n皇后问题，即要求将n个皇后放置在n*n的棋盘（以下称矩阵）中，使得任意一个皇后都不能攻击其她皇后，皇后能够攻击的位置是皇后所在的一整行，所在的一整列，所在的两条对角线。要求皇后不能互相攻击，即是要求任意一个皇后，她所在位置的行，列，两条对角线没有其他皇后.

思路

• 此题目需要用到递归
• n皇后问题，关键是要确定哪些位置可以放置，哪些位置不能放置.
• 根据题意，矩阵的每一行只能有一个皇后，每一列也只能一个皇后.
• 我们每一行每一行的寻找，看一行的哪个位置可以放置，为了确定这个位置是否可以放置皇后.
• 我们需要检查:

1. 这个位置所在的列是否有皇后.
2. 这个位置所在的左对角线是否有皇后.
3. 这个位置所在的右对角线是否有皇后.
4. 可以不用检查行，因为我们是按行从每一个位置开始检查的，该行一定没有其他皇后.

nqueens.png

• 如上图（以八皇后为例）。
• 为此为了确定当前的列是否有皇后，我们维护一个数组表示当前的列是否被占用。
• 对于左对角线和右对角线：对于正矩阵，如果有n条边，则有2*n-1条左对角线，2*n-1条有对角线（每列一条对角线，每行一条对角线，中间的对角线重叠）.
• 并且对于坐标为(row,col)的位置，其左对角线上的点满足row+col为定值（如下图），其右对角线上的点满足row+n-(col+1)为定值.
• 可以这样理解：对于该点的左对角线，该对角线满足线上所有点到第一行的举例与到第一列的举例（不包括本身）之和[row+col]为定值；该点的右对角线满足对角线上所有点到一行的举例与最后一列的距离之和[row+n-(col+1)]为定值.
• 于是我们用两个数组来表示对角线是否能放置皇后.
• 可以参照维基百科的八皇后问题为例来理解皇后问题.
• 皇后问题的解的个数是增加的非常快的，如下表格：

有了以上分析，代码实现思路如下

• 检查一行的元素是否能够放置皇后
• 如果找到了一行的某个位置能够放置皇后，检查下一行
• 找到最后一行截止

class Solution:
    # 把变量设置为对象的属性，可以方便递归函数的直接调用，使代码更加简洁
    def __init__(self):
        # 记录列的情况，表示是否被占用,Ture表示被占用，False表示没有被占用
        self.coloccupied = []
        # 记录左对角线的情况，表示左对角线是否被占用，Ture表示被占用，False表示没有被占用
        self.Left_diag = []
        # 记录又对角线的情况，表示右边的对角线是否被占用，Ture表示被占用，False表示没有被占用
        self.right_diag = []
        # 皇后的面板，所有的位置都初始化为'.'
        self.board = []
        # 矩阵维度，也就是棋盘的行列数
        self.rank = 0
        # 结果数组
        self.res = []

    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        # 初始化变量
        # 矩阵维度
        self.rank = n
        # 所有列的占用情况初始化为False，即没有被占用
        self.coloccupied = [False]*self.rank
        # 所有左对角线初始化为没有被占用
        self.Left_diag = [False]*(2*self.rank-1)
        # 所有有对角线初始化为没有被占用
        self.right_diag = [False]*(2*self.rank-1)
        # 皇后的位置矩阵是二维矩阵，初始化为"."表示没有被占用
        for _ in range(self.rank):
            self.board.append(['.']*self.rank)
        # 从第一行开始检查
        self.nQueen(0)
        for i in range(len(self.res)):
            self.res[i] = [''.join(subitem) for subitem in self.res[i]]
        return self.res

    # 检查当前位置是否被占用，被占用返回Ture，没有被占用返回False
    def isOccupied(self, row, col):
        # 当前位置所在的列，左对角线，右对角线只要有一个被占用，则该位置就被占用
        return self.coloccupied[col] or self.Left_diag[row+col] or self.right_diag[row+self.rank-col-1]

    def put(self, row, col, isput):
        # 该列是否被占用
        self.coloccupied[col] = isput
        # 该位置左对角线是否被占用
        self.Left_diag[row+col] = isput
        # 该位置右对角线是否被占用
        self.right_diag[row+self.rank-col-1] = isput
        # 如果是放置，则放入"Q"，清空，放置"."
        self.board[row][col] = "Q" if isput else "."

    def nQueen(self, row):
        if row == self.rank:
            # 注意，这里需要用深拷贝
            self.res.append(copy.deepcopy(self.board))
            return
        for col in range(self.rank):
            # 如果被占用，进入下一个循环
            if self.isOccupied(row, col):
                continue
            # 在当前位置放置皇后
            self.put(row, col, True)
            # 进入下一层寻找
            self.nQueen(row+1)
            # 下一层寻找完成之后，释放当前位置，检查当前位置的下一个位置
            self.put(row, col, False)

源代码文件在这里
©本文首发于何睿的博客，欢迎转载，转载需保留文章来源，作者信息和本声明.