LeetCode 51 [N-Queens]

原题

n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击。
给定一个整数n，返回所有不同的n皇后问题的解决方案。
每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。

样例
对于4皇后问题存在两种解决的方案：
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]

n-queen puzzle

解题思路

Paste_Image.png

• 本题需要三个helper函数来辅助，使得代码更加清晰，第一需要DFS函数，过程如上图所示。一行一行的放置queen，当出现非法的情况时，直接返回上一级 - backtracking的思路

# backtracking
cols.append(col) # 加
self.dfs(cols)
cols.pop() # 减
# 等效于
self.dfs(cols + [col])

• 第二个函数就是判断某一点放queen是否合法
• 因为是一行一行放，所以可以保证不在一行上
• 全局变量cols记录了那一列已经放置了queen，通过检查当前列是否在其中，即可判断是不是同一列有两个queen。同时cols的长度也表示已经有多少行放置好了queen，当len(cols) == n的时候可以drawboard并加入result中
• 同时还有检查对角线，左上右下和左下右上
• 第三个函数是根据cols数组画出board，相对简单。比如[2, 4, 1, 3]表示第一行queen在第二列，第二行queen在第四列，第三行queen在第一列，第四行queen在第三列

完整代码

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        result = []
        if n <= 0:
            return result

        cols = []
        self.search(n, cols, result);
        return result
        
    def search(self, n, cols, result):
        if len(cols) == n:
            result.append(self.drawBoard(cols))
            return
        
        for col in range(n):
            if not self.isValid(cols, col):
                continue
            self.search(n, cols + [col], result)
            
    def isValid(self, cols, col):
        currentRowNumber = len(cols)
        for i in range(currentRowNumber):
            # same column
            if cols[i] == col:
                return False
            # left-top to right-bottom
            if i - cols[i] == currentRowNumber - col:
                return False
            # right-top to left-bottom
            if i + cols[i] == currentRowNumber + col:
                return False
        return True
        
    def drawBoard(self, cols):
        board = []
        for i in range(len(cols)):
            line = ""
            for j in range(len(cols)):
                if j == cols[i]:
                    line += "Q"
                else:
                    line += "."
            board.append(line)
        return board